6
$\begingroup$

We pick $n\ge 2$ points in $[0,1]$ with uniform distribution. What is the expected value of the largest distance of $2$ adjacent points?

$\endgroup$
  • 1
    $\begingroup$ Isn't this closely related to the expected value of the biggest of $n$ numbers picked uniformly from $[0,1]$? $\endgroup$ – quarague Jul 3 at 7:42
15
$\begingroup$

The expected value is asymptotic to $(\log n)/n$ as $n$ tends to infinity (By "asymptotic" I mean that the ratio tends to 1). One way to see this is to use the representation of order statistics of uniform points as the first $n$ points of a Poisson process, normalized by the $n+1$ Point. Since the sum of $n+1$ exponential variables is concentrated, the question reduces to the distribution of the maximum of $n-1$ Exponential variables.

Usually one considers the maximum $M_n$ of the $n+1$ gaps including the gap between zero and the first point and between 1 and the last point, but that does not change the asymptotics. The known properties of $M_n$ are surveyed in the introduction of Devroye's paper that Brendan McKay mentioned: https://projecteuclid.org/download/pdf_1/euclid.aop/1176994313

In particular the fact about Poisson processes I noted above is Lemma 2.1 there, and lemmas 2.4, 2.5 and 2.6 describe more precise asymptotics for the maximal gap.

$\endgroup$
  • 1
    $\begingroup$ Isn't there also a constant (namely Euler's constant)? See Lemma 2.6 of jstor.org/stable/pdf/… $\endgroup$ – Brendan McKay Jul 3 at 9:27
  • 1
    $\begingroup$ Brendan, that constant only appears in the second order term. $\endgroup$ – Yuval Peres Jul 3 at 10:22
  • $\begingroup$ Oops, yes indeed. $\endgroup$ – Brendan McKay Jul 3 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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