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,

Improve this question
$\endgroup$
9
  • $\begingroup$ this is an order statistics question try stats.stackexchange.com $\endgroup$
    – guest
    Commented 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$
    – Douglas Zare
    Commented 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$
    – Douglas Zare
    Commented 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$
    – Noam D. Elkies
    Commented 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
    Commented Feb 18, 2014 at 2:32

2 Answers 2

Reset to default
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.

Improve this answer
$\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$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .