What Comes After 840? The Answer May Surprise You

If $N$ points are generated at random places on the perimeter of a circle, what is the probability that you can pick a diameter such that all of those points lie on only one side of the newly halved circle?

The Riddler, FiveThirtyEight(original post)

Solution

All $N$ points lie within some half of the circle exactly when there is an empty semicircle, equivalently when one of the points can serve as the clockwise “leader” with every other point inside the half-circle that starts at it and runs clockwise.

Fix one point and ask whether the other $N-1$ all fall in the semicircle clockwise from it. Each of them lands there independently with probability $\tfrac12$, so this happens with probability $(\tfrac12)^{N-1}$. There can be at most one such leader, because two different leaders would need each other inside their own forward semicircles, which is impossible. So the $N$ leader events are disjoint, and the probability that some point leads is their sum: $$\Pr(\text{all in a half}) = N \cdot \frac{1}{2^{\,N-1}} = \boxed{\dfrac{N}{2^{\,N-1}}}.$$ For $N=2$ this is $1$ (two points always share a semicircle); for $N=10$ it is $10/512 = 5/256 \approx 2\%$.

The computation

Drop $N$ points at random angles and sort them. They fit in a half-circle exactly when some gap between neighbouring points (around the loop) is at least $\pi$. Measuring the frequency for several $N$ matches $N/2^{N-1}$.

import numpy as np
rng = np.random.default_rng(0)
runs = 400_000
for N in range(2, 11):
    hit = 0
    for _ in range(runs):
        a = np.sort(rng.uniform(0, 2*np.pi, N))
        gaps = np.diff(a, append=a[0] + 2*np.pi)     # gaps around the circle
        hit += gaps.max() >= np.pi                    # an empty half-circle
    print(N, hit / runs, N / 2**(N - 1))              # estimate vs N/2^(N-1)