Smallest gap among random points on a circle, Geometric Probability

Problem 17.1

Let $P_1, \ldots, P_n$ be $n$ independent uniform random points on a circle of circumference $1$ . What is the expected value of the smallest gap between consecutive points (measured along the circle)?

Solution. Anchor the cyclic order at one labelled point, and let $G_1, \ldots, G_n$ be the clockwise gaps from that point onward. Rotating the anchor to $0$ leaves $n-1$ independent uniform positions; their $n$ spacings have the uniform Dirichlet $(1,\ldots,1)$ distribution. By exchangeability, each $G_i$ has the same marginal distribution and $\sum G_i = 1$ , so $\mathbb{E}[G_i] = 1/n$ .

To find $\mathbb{E}[\min G_i]$ , start from the classical identity $\mathbb{P}(\min_i G_i > c) \;=\; (1 - n c)^{n - 1}, \qquad 0 \leq c \leq 1/n.$ Why: the event “every gap exceeds $c$ ” means every gap has an initial length- $c$ “buffer.” Subtracting these $n$ buffers leaves a total free length of $1 - nc$ , distributed as $n$ uniform spacings on a circle of circumference $1 - nc$ . By scale invariance this has density proportional to a Dirichlet(1,…,1), whose joint density is $(n-1)!$ , and integration over the simplex gives the factor $(1-nc)^{n-1}$ .

Compute the expectation by integrating the tail: $\mathbb{E}[\min G_i] = \int_0^{1/n} \mathbb{P}(\min > c) \, dc = \int_0^{1/n} (1 - n c)^{n-1} dc.$ Substitute $u = 1 - n c$ , $du = -n \, dc$ : $= \int_0^1 u^{n-1} \cdot \frac{du}{n} = \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}.$ Hence $\boxed{\mathbb{E}\!\left[ \min_{1 \leq i \leq n} G_i \right] = \frac{1}{n^2}.} \qedhere$

Six iid uniform random points on the unit circle. The copper arc is the minimum gap between consecutive points (here, between P_4 and P_5 , of angular size 0.046 radians, or length 0.046/(2\pi) \approx 0.00732 on a circle of circumference 1 ). For n = 6 , the expected minimum gap is 1/n^2 = 1/36 \ap — Six iid uniform random points on the unit circle. The copper arc is the *minimum gap* between consecutive points (here, between $P_4$ and $P_5$ , of angular size $0.046$ radians, or length $0.046/(2\pi) \approx 0.00732$ on a circle of circumference $1$ ). For $n = 6$ , the expected minimum gap is $1/n^2 = 1/36 \approx 0.028$ .

For $n = 3$ the expected minimum gap is $1/9$ ; for $n = 10$ it is $1/100$ . Asymptotically, the smallest gap is of order $1/n^2$ , far below the average gap $1/n$ — a reflection of the “bunching” property of uniform random points. This is the content of the classical small-spacing heuristic that underlies the probabilistic theory of matching and birthday-type problems.

import numpy as np
for n in [3, 5, 10]:
    pts = np.sort(np.random.rand(n, 10**6), axis=0)
    gaps = np.diff(pts, axis=0)
    wrap = pts[0] + 1 - pts[-1]
    all_gaps = np.vstack([gaps, wrap[None, :]])
    print(f"n={n}: sim={all_gaps.min(axis=0).mean():.5f}  exact={1/n**2:.5f}")
# n=3:  sim=0.11112   exact=0.11111
# n=5:  sim=0.04000   exact=0.04000
# n=10: sim=0.01000   exact=0.01000