I am currently doing a little self-study of A Probability Path by Sidney Resnick, and am having trouble with the following problem:

Points are chosen at random on the circumference of the unit circle. $Y_n$ is the arc length of the largest arc not containing any points when $n$ points are chosen. Show $Y_n \to 0$ almost surely.

So far my strategy is the following:

Since $\{Y_n\}$ is a monotone (decreasing) sequence, convergence almost surely is equivalent to convergence in probability, so it suffices to show that the expected value $E(Y_n) \to 0$.

A naive guess is that $E(Y_n) = \frac{2\pi}{n}$.

We can write \begin{equation} E(Y_n) = \int_0^{2\pi}P(Y_n > l)\,d l. \end{equation} and \begin{equation} P(Y_n > l) = \begin{cases} 1, & \text{if } l < \frac{2\pi}{n},\\ \text{??} & \text{otherwise}. \end{cases} \end{equation}

How do we determine $P(Y_n > l)$? Or is there another way to proceed?

  • $\begingroup$ $P(Y_n \gt l)$ is relatively easy to calculate if $l \ge \pi$ but harder for smaller $l$. $\endgroup$ – Henry Jul 11 '15 at 22:00
  • 2
    $\begingroup$ After the first point is chosen you can work in the interval, no? $\endgroup$ – Mariano Suárez-Álvarez Jul 11 '15 at 22:12
  • $\begingroup$ Perhaps you only need some upper bound on this probability. If the upper bound goes to $0$ as $n\to\infty$, that should do it. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jul 11 '15 at 23:40
  • 1
    $\begingroup$ I think what Resnick has in mind here is that you apply Theorem 6.4.1 (quantile estimation). For the uniform distribution it implies that if you fix $n$ and then choose $N\to\infty$ points and put them in order so that $X^{N}_1\le X^{N}_{2}\cdots X^{N}_{N}$, then $X^{N}_{kN/n}$ approach $k/n$. This means the points are roughly uniformly distributed and implies the result you want. $\endgroup$ – Jeremy Teitelbaum Sep 10 '16 at 20:04

If the length of the longest such arc does not approach $0$ almost surely, then with probability $>0$ there is some arc that remains empty for all $n$. Pick any arc of positive length. The probability that it is empty after $n$ points are chosen is $$ \left( \frac{\text{length of the particular arc}}{\text{whole circumference}} \right)^n \to 0 \text{ as }n\to\infty. $$

  • 1
    $\begingroup$ I think you may need more than this as I would have thought as you need to show it for every arc of the same length simultaneously or at least for the $\frac{c}{l}$ arcs making up the circle. That would not be difficult if the point/pointless status of each arc was independent as you would have the probability $1 - \left(1 - \left(\frac{l}{c}\right)^n\right) ^ {c/l} \to 0$ as $n$ increases, but they are not quite independent. $\endgroup$ – Henry Jul 12 '15 at 8:46

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.