4
$\begingroup$

If $N$ points on the circumference of a circle are chosen at random, what is the probability $F(\theta)$ that the maximum gap between neighboring points is at least $\theta$? Because the gaps sum to $2\pi$, the maximum must be at least $2\pi/N$, so $F(\theta)=1 \text{ for } \theta\le\frac{2\pi}{N}.$ At the other extreme, the solution to this problem shows that $F(\theta) = N\left(1 - \frac{\theta}{2\pi}\right)^{N-1} \text{ for } \theta\ge\pi.$ Is there a closed-form solution for any other values of $\theta$?


Update: The general closed-form solution is given in the answer below. In terms of the notation in the question, it is $ F(\theta) = \sum_{k=1}^{K} (-1)^{k-1} {N\choose k} \left(1 - \frac{k \theta}{2\pi}\right)^{N-1}, $ where $K = \min(N, \lfloor{2\pi/\theta}\rfloor)$. This reduces to the limiting cases given in the question when $\theta \le 2\pi/N$ (in which case $K=N$) and when $\theta \ge \pi$ (in which case $K=1$).

  • 0
    @leonbloy: I'm not sure what the policy is about duplicating questions from MO. It might be somewhere in meta, but I don't have time to chase it down now because I have to run to class.2011-01-25

1 Answers 1

3

As Shai Covo indicates, this is given in my answer to the recent Math Overflow question "Expected Second Moment for Random Points on a Circle."

For a unit circle, the answer is $F(x) = n(1-x)^{n-1} - \binom{n}{2} (1 - 2x)^{n-1} + \cdots + (-1)^{k-1} \binom{n}{k} (1 - kx)^{n-1} + \cdots,$ where the sum continues until $kx > 1$.

For the derivation see the MO answer. It leans heavily on Section 6.4 ("Random Division of an Interval") in David and Nagaraja's Order Statistics, pages 133-137, and the corresponding exercises on pages 153-155.

The result was apparently first published by Ronald Fisher in "Tests of Significance in Harmonic Analysis," Proceedings of the Royal Society of London, Series A, 1929, pp 54-59. (My apologies that this is a JSTOR link and not one that is freely available.)