Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have encountered a seemingly simple question on distances of random points.

Place N points randomly and uniformly on the line segment [0..1]. How to derive the expectation (or the distribution) of the "maximum" distance between two consecutive points?

Just a reference would be very helpful.

Thanks,

share|improve this question
    
this is an order statistics question try stats.stackexchange.com –  guest Feb 18 at 1:05
1  
What is the connection with algebraic geometry? Also, do you include distances from $0$ and $1$ or not? If you do, then there is a useful transformation: The $n+1$ gaps are uniformly distributed on the $n$-dimensional simplex of positive numbers summing to $1$. –  Douglas Zare Feb 18 at 1:37
1  
This article computes some moments of the distribution for uniformly distributed random variables for comparison with distributions of primes: ams.org/journals/mcom/1971-25-116/S0025-5718-1971-0299567-6/… I think more was known from much earlier, though. –  Douglas Zare Feb 18 at 1:59
    
Do you mean "consecutive" in the order in which the points were chosen, or in their order in $(0,1)$? E.g., if $N=3$ and $(x_1,x_2,x_3)$ happens to be $(0.4, 0.6, 0.1)$, is the maximum distance $\left|x_2-x_3\right| = 0.5$ or $0.4 - 0.1 = 0.3$? (Or maybe $1 - x_2 = 0.4$, going by Douglas Zare's suggestion?) –  Noam D. Elkies Feb 18 at 2:19
    
Sorry for confusion. The points should be sorted. My original question is on random points placed on the circumference of length 1. But, for N->infinity, both cases are similar, I think. –  Kaz Feb 18 at 2:32

2 Answers 2

Let $S$ be the length of the longest interval and let $X$ be the largest random variable among $n=N+1$ iid exponential random variables with mean 1. We have $E[S] = E[X]/n$, where $E[X]=\sum_{i=1}^n 1/i$.

From this paper:

L. Holst. On the lengths of the pieces of a stick broken at random. Journal of Applied Probability, 17(3):623–634, 1980.

share|improve this answer

For $n$ random points on a circle, Theorem 1 of this article provides an expression for the $m$th moment of the maximum distance, namely

$$ \mathbb{E}\left[\left(d_{\max}\right)^m\right]=\frac{(n-1)!}{(n+m-1)!}\sum_{\stackrel{r_1+2r_2+\ldots+m r_m}{r_i\in\mathbb{N}_0}}{\frac{m!}{r_1!1^{r_1}r_2!2^{r_2}\cdots r_m! m^{r_m}}H_{n,1}^{r_1}H_{n,2}^{r_2}\cdots H_{n,m}^{r_m}}, $$

where $H_{n,k}=\sum_{j=1}^n{j^{-k}}$ is the $n$th harmonic number of order $k$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.