7
$\begingroup$

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,

$\endgroup$
9
  • $\begingroup$ this is an order statistics question try stats.stackexchange.com $\endgroup$
    – guest
    Feb 18, 2014 at 1:05
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 18, 2014 at 1:37
  • 1
    $\begingroup$ 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. $\endgroup$ Feb 18, 2014 at 1:59
  • $\begingroup$ 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?) $\endgroup$ Feb 18, 2014 at 2:19
  • $\begingroup$ 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. $\endgroup$
    – Kaz
    Feb 18, 2014 at 2:32

2 Answers 2

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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