8
$\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?

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

1 Answer 1

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

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

You must log in to answer this question.

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