Drop $n$ points independently and uniformly on a circle of circumference $1$. They cut the circle into $n$ arcs, the gaps, whose average length is exactly $1/n$. The longest gap is much longer than that. Its expected length is

so with a thousand points the longest gap is, on average, $7.5$ times the average gap, while the shortest gap has expectation exactly $1/n^2$, a thousand times shorter than average. The derivation is one change of variables. The exact distribution of the longest gap is a finite alternating sum that Fisher wrote down in 1929 for a problem in time-series analysis. One application is consistent hashing: $n$ servers hashed to a ring each own the arc up to their next neighbor, so the busiest server carries about $\ln n$ times its fair share of the keys.

The gaps are exchangeable

Rotate the circle so that the first point sits at $0$. The other $n - 1$ points are then i.i.d. uniform on $[0, 1)$, and sorted into $U_{(1)} < U_{(2)} < \cdots < U_{(n-1)}$ they have joint density $(n-1)!$ on the region $0 < u_1 < \cdots < u_{n-1} < 1$. The gaps are

and the map from $(U_{(1)}, \ldots, U_{(n-1)})$ to $(G_1, \ldots, G_{n-1})$ is linear with determinant $1$. So the gap vector is uniformly distributed on the simplex $\{g_i \ge 0,\; g_1 + \cdots + g_n = 1\}$, the Dirichlet distribution with all parameters equal to $1$. Uniformity on the simplex is symmetric in the coordinates, so the gaps are exchangeable: every permutation of $(G_1, \ldots, G_n)$ has the same joint law. They are not independent, since they sum to $1$, but any statement about one gap is a statement about every gap. Each has the marginal

the probability that the other $n - 1$ points all avoid an arc of length $x$, with mean $1/n$. This is the same symmetry that produces the German tank estimator: there, $k$ observed serial numbers cut a range into $k+1$ exchangeable gaps, and the unobserved gap above the maximum is estimated by the average of the visible ones.

The gap that contains a fixed location on the circle, say the point diametrically opposite the origin, is not a typical gap: long gaps are more likely to contain any given location, in proportion to their length. Its mean is $\mathbb{E}[G^2]/\mathbb{E}[G] = 2/(n+1)$, about twice the average gap. This is the inspection paradox, and it is the reason that, when buses arrive at random times, the interval you land in is longer than the average interval between buses.

Gaps are normalized exponentials

The uniform distribution on the simplex has a second description that makes order statistics easy. Let $E_1, \ldots, E_n$ be i.i.d. exponential random variables with mean $1$ and let $S = E_1 + \cdots + E_n$. The joint density of the $E_i$ is $e^{-(e_1 + \cdots + e_n)}$, a function of the sum alone, so conditional on $S$ the vector $(E_1, \ldots, E_n)$ is uniform on the simplex of total $S$; equivalently, $(E_1/S, \ldots, E_n/S)$ is uniform on the unit simplex and independent of $S$. The gaps have the same law as $E_i/S$.

Order statistics of exponentials follow from memorylessness. The minimum of $n$ exponentials with mean $1$ is exponential with mean $1/n$; given the minimum, the excesses of the other $n-1$ variables over it are again i.i.d. exponential with mean $1$, so the second smallest exceeds the smallest by an exponential with mean $1/(n-1)$, and so on up the order. This is Rényi’s representation (1953):

Since $G_{(k)} = E_{(k)}/S$ is independent of $S$, taking expectations gives $\mathbb{E}[E_{(k)}] = \mathbb{E}[G_{(k)}]\,\mathbb{E}[S] = n\,\mathbb{E}[G_{(k)}]$, and therefore

In units of the average gap $1/n$: the smallest gap is $1/n$ of an average gap, the median gap ($k = n/2$) is $H_n - H_{n/2} \approx \ln 2 = 0.69$ average gaps, and the largest is $H_n$ average gaps. The largest gap grows like $\ln n$ average gaps and the smallest shrinks like $1/n$ of one. The expected largest gap, in units of the average gap:

The exact distribution of the largest gap

All gaps are at most $x$ exactly when none exceeds $x$, and inclusion–exclusion over the events $\{G_i > x\}$ needs only one fact: for any $k$ specified gaps,

Subtracting $x$ from each of the $k$ gaps leaves a vector uniform on a simplex of total $1 - kx$, and the volume of that simplex relative to the full one is $(1 - kx)^{n-1}$ (the simplex has dimension $n - 1$). Hence

For $x \ge \tfrac12$ only the terms $k = 0, 1$ survive, and $\mathbb{P}(G_{\max} > \tfrac12) = n\,2^{1-n}$ is the probability that all $n$ points fit in some semicircle, a classical problem. At the other end, $\mathbb{P}(G_{\min} > x) = (1 - nx)^{n-1}$ is the single term $k = n$ (every gap exceeds $x$), so the probability that some two of the points lie within distance $x$ of each other is $1 - (1 - nx)^{n-1} \approx 1 - e^{-n^2 x}$, the continuous form of the birthday problem; in units of $1/n^2$ the smallest gap is asymptotically exponential.

For the largest gap, put $x = (\ln n + y)/n$. Then $\binom{n}{k} \approx n^k/k!$ and $(1 - kx)^{n-1} \approx e^{-k(\ln n + y)} = n^{-k}e^{-ky}$, so term by term the sum tends to $\sum_k (-1)^k e^{-ky}/k!$:

the Gumbel distribution, whose mean is Euler’s constant $\gamma = 0.5772$, in agreement with $H_n - \ln n \to \gamma$. The largest gap is $\ln n$ average gaps plus a Gumbel-distributed number of average gaps: its mean grows with $n$, but its fluctuations stay of the same order as a single average gap. The widget draws a sample on the left and, on the right, the exact density of $n\,G_{\max}$ from the alternating sum, with the Gumbel limit and an adjustable threshold:

Consistent hashing

Karger and coauthors (1997) proposed the following way to spread keys over servers so that adding or removing a server disturbs as little as possible. Hash each server to a point on a ring, hash each key to a point on the same ring, and assign each key to the first server clockwise from it. When a server joins or leaves, only the keys on one arc move. The share of keys a server receives is the length of the arc it owns, which is exactly one of the gaps above. So the busiest server’s share is $G_{\max}$: on average $H_n$ times the fair share $1/n$, and the imbalance grows with $n$. With $100$ servers the busiest holds $5.2$ times its share on average, and the probability that some server holds more than three times its share is $0.9992$; with $1{,}000$ servers the busiest holds $7.5$ times its share.

The remedy in the same paper is to hash each server to $v$ points instead of one, the virtual nodes of later systems. A server’s share is then the sum of $v$ of the $nv$ gaps, and by exchangeability that sum has the beta distribution with parameters $v$ and $(n-1)v$: mean $1/n$ as before, and relative standard deviation $\sqrt{(n-1)/(nv+1)} \approx 1/\sqrt{v}$. A hundred virtual nodes per server bring the typical deviation from the fair share down to about 10%, and the largest of the $n$ shares to roughly $1 + \sqrt{2\ln n / v}$ times the average (a Gaussian approximation to the beta law, with a union bound over the servers), about $1.3$ for a hundred servers with a hundred virtual nodes each. Karger and coauthors prove that $O(\log n)$ points per server suffice to bring the largest share within a constant factor of $1/n$ with high probability, and production systems such as Dynamo assign each server many positions on the ring for this reason.

Related problems

• Fisher’s test for a hidden periodicity. For a time series of Gaussian white noise, the ordinates of the periodogram are i.i.d. exponentials, and normalized by their sum they are exactly uniform spacings. Fisher’s 1929 test rejects white noise when the largest normalized ordinate is too large, and the alternating sum above is the null distribution he derived for it.
• Covering the circle with arcs. Place an arc of length $a$ clockwise from each of the $n$ points. The arcs cover the circle exactly when no gap exceeds $a$, so the coverage probability is $\mathbb{P}(G_{\max} \le a)$, the formula Stevens (1939) obtained for the covering problem.
• Poisson arrivals. Conditional on a Poisson process having $n$ arrivals in a window, the arrival times are i.i.d. uniform in the window, so the longest interval without an arrival is the largest gap, and the exponential representation is the Poisson process itself, before conditioning on the count.

The theory of spacings between order statistics is surveyed in Pyke (1965), the general distribution theory for functions of the gaps goes back to Darling (1953), and Holst (1980) derives the limit laws for the $j$-th longest piece from the exponential representation alone.

References

• Ronald A. Fisher. Tests of significance in harmonic analysis. Proceedings of the Royal Society A, 125(796):54–59, 1929. The exact distribution of the largest normalized periodogram ordinate, which is the largest-gap formula.
• W. L. Stevens. Solution to a geometrical problem in probability. Annals of Eugenics, 9(4):315–320, 1939. Covering the circle by $n$ random arcs of equal length.
• Alfréd Rényi. On the theory of order statistics. Acta Mathematica Academiae Scientiarum Hungaricae, 4:191–231, 1953. The representation of exponential order statistics as sums of independent exponentials.
• D. A. Darling. On a class of problems related to the random division of an interval. Annals of Mathematical Statistics, 24(2):239–253, 1953. The characteristic-function method for statistics built from the gaps.
• Ronald Pyke. Spacings. Journal of the Royal Statistical Society, Series B, 27(3):395–436, 1965. The survey of the subject.
• Lars Holst. On the lengths of the pieces of a stick broken at random. Journal of Applied Probability, 17(3):623–634, 1980. Limit laws for the ordered pieces from the exponential representation.
• David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, Daniel Lewin. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on the World Wide Web. Proceedings of the 29th ACM Symposium on Theory of Computing, pages 654–663, 1997. Consistent hashing and the $O(\log n)$ virtual copies.
• Giuseppe DeCandia et al. Dynamo: Amazon’s highly available key-value store. Proceedings of the 21st ACM Symposium on Operating Systems Principles, pages 205–220, 2007. Virtual nodes in a production system.