Library · Geometric Probability · Chapter 14

n random points on a circle, all in a semicircle

Revised Report an error

Problem 14.1

Let P1,…,PnP_1, \ldots, P_n be nn points chosen independently and uniformly on a circle. What is the probability that all of them lie within some semicircle?

Solution. Fix a labelling of the points. Call the event SS “there exists some semicircle containing P1,…,PnP_1, \ldots, P_n.” For each ii, let EiE_i denote the event “the semicircle whose starting endpoint is at PiP_i (measured clockwise) contains all the other PjP_j.”

Claim. The events E1,…,EnE_1, \ldots, E_n are mutually exclusive and S=E1∪⋯∪EnS = E_1 \cup \cdots \cup E_n.

Exclusive: if SS occurs, there is an arc of length π\pi containing all points. The unique minimal such arc has both endpoints equal to points of the configuration; the starting-endpoint PiP_i (in cyclic order) is determined, and only that EiE_i occurs.

Covering: if SS occurs, some EiE_i occurs by the same construction.

Probability of each EiE_i. By rotational symmetry, fix PiP_i at angle 00. The other n−1n - 1 points must all lie in the semicircle from 00 to π\pi (clockwise). Each is independently uniform on the full circle, so the probability it lies in a chosen semicircle is 12\tfrac12. Hence P(Ei)=(12)n−1.\mathbb{P}(E_i) = \left( \tfrac12 \right)^{n-1}.

Assemble. By mutual exclusivity, P(S)=∑i=1nP(Ei)=n⋅(12)n−1.\mathbb{P}(S) = \sum_{i=1}^{n} \mathbb{P}(E_i) = n \cdot \left( \tfrac12 \right)^{n-1}. So P(n random points all in a semicircle)=n2n−1.■\boxed{\mathbb{P}(n \text{ random points all in a semicircle}) = \frac{n}{2^{n-1}}.} \qedhere

Five iid uniform points on the unit circle. The sage arc is the shortest arc containing all five points and is longer than a semicircle; in this realization the five points do not all fit in any semicircle (the largest gap between consecutive points is 2.417 \pi ).
Five iid uniform points on the unit circle. The sage arc is the shortest arc containing all five points and is longer than a semicircle; in this realization the five points do not all fit in any semicircle (the largest gap between consecutive points is 2.417<π2.417 < \pi).

For n=3n = 3, this gives 34\tfrac{3}{4}. Taking the complement recovers the Wendel probability of Chapter 25: the probability that three random points on a circle form a triangle containing the centre is 1−34=141 - \tfrac34 = \tfrac14. For n=4n = 4: 48=12\tfrac{4}{8} = \tfrac12. The formula was posed as Putnam 1992 A-5 and is a favourite of problem-set compilers.

import numpy as np
for n in [3, 4, 5]:
    theta = np.sort(np.random.rand(n, 10**6) * 2*np.pi, axis=0)
    gaps = np.vstack([np.diff(theta, axis=0),
                      2*np.pi - theta[-1] + theta[0]])
    p = (gaps.max(axis=0) > np.pi).mean()
    print(f"n={n}: sim={p:.5f}   exact={n / 2**(n-1):.5f}")
# n=3: sim=0.74926   exact=0.75000
# n=4: sim=0.49987   exact=0.50000
# n=5: sim=0.31298   exact=0.31250
Report an error on this page

Reports are stored by Netlify. See the privacy note.