Arcs that cover a circle

Nobody gets their own hat used inclusion and exclusion to count the permutations that leave nobody fixed: add up the arrangements, subtract those that fix one person, add back those that fix two, and so on, and the alternating sum settles on $1/e$. A sum stopped early still says something showed that stopping that sum after any term gives a bound, too high and too low in turn. Every application so far has been about discrete objects — hats, permutations, seats at a table.

This essay applies the same sum to a continuous problem. Drop arcs onto a circle at random, each a fixed fraction of the circumference, with their starting points independent and uniform. How many are needed before the circle is completely covered? The question goes back to Stevens, a statistician working on the distribution of gaps between random points, who in 1939 found the exact chance of covering with an inclusion–exclusion over which gaps are too long. The formula is short. Its terms are enormous, they cancel almost perfectly, and what survives the cancellation is a fact about randomness that every covering problem shares: placed at random, it takes about the logarithm of the number of pieces times as many pieces as placed with care.

Covering is a statement about gaps #

The hero drops fourteen arcs, each one fifth of the circle, with their clockwise ends at random points, and draws them at staggered depths so that their overlaps show. Their total length is 2.8 times the circumference, and yet a stretch of the circle near the top is covered by none of them. Whether a placement covers depends only on the starting points: going round the circle, each arc covers from its start to a fifth of the way on, so the circle is covered exactly when every gap between consecutive starting points is at most a fifth. In the hero the starting points 0.579 and 0.930 leave a gap of 0.351, and the arc from 0.579 reaches only to 0.779.

So the question is about the gaps between $n$ random points on a circle. Cut the circle at one of the points and the other $n - 1$ points fall uniformly on the remaining length; the $n$ gaps they make are uniformly distributed over all ways of splitting the circumference into $n$ non-negative parts — a point chosen uniformly in a simplex. That uniformity gives the one fact the inclusion–exclusion needs: if $k$ particular gaps are required to exceed $a$, subtract $a$ from each of them and what is left is a uniform split of the remaining length $1 - ka$, so the chance is

$$\Pr(\text{$k$ named gaps all exceed } a) = (1 - ka)^{n-1}$$

whenever $ka < 1$, and nought otherwise. It is the continuous version of the count of permutations that fix a named set of people.

Stevens’s alternating sum #

The circle is covered when no gap exceeds $a$. Inclusion and exclusion over the set of gaps that are too long, exactly as for the hats, gives

$$\Pr(\text{covered}) = \sum_{k \ge 0} (-1)^k \binom{n}{k} (1 - ka)^{n-1},$$

the sum running over every $k$ with $ka < 1$. For the hero’s fourteen arcs of a fifth it has five terms — $k = 0$ to 4 — and comes to $0.34675$: a placement like the one drawn, with a bare stretch, is the more likely outcome, by almost two to one.

The figures compute every value of this sum exactly. With $a = p/q$ a fraction, each term is a whole number $\binom nk (q - kp)^{n-1}$ divided by $q^{n-1}$, so the sum can be added in whole-number arithmetic and divided once at the end. That is not fastidiousness. In floating point the sum cannot be computed at all once the arcs are short and numerous, because the terms are thousands of times larger than the answer and of alternating sign, and every digit of the answer is lost to the cancellation.

Terms in the thousands, an answer near nought #

The figure shows how much cancels. Sixty arcs, each a fortieth of the circle, have a total length of one and a half circumferences. The terms of the sum start at 1, then $-13.5$, then $85.8$, then $-344$, and grow to $4{,}901$ at $k = 8$ before shrinking again, every one of them far larger than a probability can be. They cancel to $2 \times 10^{-20}$. Sixty arcs of a fortieth, though they could cover the circle half again over, essentially never do: with sixty starting points the typical gap is a sixtieth, and the chance that no gap is longer than a fortieth is the chance that all sixty gaps stay within one and a half times their average, which is astronomically small.

The running totals in the figure lie alternately above and below the answer, as they must. That is the Bonferroni inequalities: stopping an inclusion–exclusion sum after a positive term gives an overestimate and after a negative term an underestimate, because each truncation leaves out a tail that has a definite sign. The first two terms give $1 - n(1 - a)^{n-1}$, a lower bound on the chance of covering that is already close to the truth once covering is likely, and the first term alone gives the trivial bound 1. The figure’s line swings wildly in the first eight terms, where the bounds are useless, and then closes in.

The curve and the experiment #

The figure computes the exact chance for every number of arcs up to 120 and three lengths, and checks it against simulation: at every tenth value of $n$, four thousand placements are drawn and the share that cover is plotted. Every dot lies on its curve within the statistical error, which is a test both of the formula and of the exact arithmetic.

The curves have the same shape at three scales. For arcs of a fifth, ten arcs cover only 8% of the time, twenty cover 72% and forty cover 99.3%. For arcs of a tenth, twenty arcs cover 0.4% of the time and forty cover 46%. For arcs of a twentieth the curve does not leave nought until about sixty arcs and is at 76% by 120. In each case the circle stays bare long after the arcs’ total length has passed its circumference — five arcs of a fifth could cover exactly, ten of a tenth, twenty of a twentieth — and covering becomes likely only at several times that number. The rise is steep: the curves switch from unlikely to near certain over a range of arcs comparable to the number needed, a threshold of the kind a room where nobody is alone found for birthdays.

The price of randomness is a logarithm #

The expected number of arcs needed to cover can be computed from the same sum: it is the total, over $n$, of the chances of not yet being covered after $n$ arcs. The figure does this for arcs of a quarter down to arcs of a sixtieth. A sixtieth of the circle needs, on average, 392.6 random arcs; placed edge to edge, sixty would do. The ratio grows with the number of arcs required, and it grows like a logarithm: the expected number is close to

$$\frac1a\left(\ln\frac1a + \ln\ln\frac1a + \gamma\right),$$

the formula Svante Janson made precise in 1986 after Leopold Flatto’s work of 1973, with $\gamma = 0.5772$ Euler’s constant. At $1/a = 60$ it gives 364.9 against the exact 392.6, and the gap is shrinking as $a$ gets smaller.

The logarithm has the same source as in the coupon collector’s problem, which how long until every one turns up solved: to see all $m$ kinds of coupon takes about $m\ln m$ draws, because the last few kinds are found slowly. Covering the circle with arcs of length $a$ is like collecting $1/a$ coupons, one for each stretch of length $a$, except that the stretches are not fixed in advance — an arc covers whatever it lands on — and that blurring of the coupons adds the $\ln\ln(1/a)$. Random covering is collecting without knowing exactly what the coupons are, and it costs the same logarithm plus a little.

The longest gap #

The covering problem has a mirror image. The circle is covered by $n$ arcs of length $a$ exactly when the longest of the $n$ gaps between the starting points is at most $a$. So the chance of covering, as a function of $a$, is the distribution of the longest gap. The figure measures it directly for 400 points, twenty thousand times. The longest gap is about $(\ln 400)/400$, and multiplied by 400, less $\ln 400$, it follows the Gumbel density $e^{-x - e^{-x}}$ closely, with mean $0.576$ against Euler’s constant $0.5772$.

The Gumbel law is the law of the largest of many independent waits, and the gaps are nearly independent waits: $n$ random points on a circle have gaps distributed like $n$ independent exponential variables divided by their sum, and the sum is close to $n$ times its average. The largest of $n$ exponential variables is $\ln n$ plus a Gumbel variable, which is the whole content of the figure, and setting $na - \ln n$ to a constant in Stevens’s sum gives the same limit: for large $n$ the sum becomes $\sum (-1)^k e^{-kx}/k!$, which is $e^{-e^{-x}}$. The alternating sum and the extreme-value law are one computation, read as a covering in one direction and as a maximum in the other.

The hats, seen again in the gaps #

The limit of Stevens’s sum is worth comparing term by term with the sum for the hats. For $n$ hats handed back at random, the chance that nobody gets their own is $\sum_k (-1)^k/k!$, which tends to $e^{-1}$, and how many get their own hat showed why: the number of people who get their own hat is nearly a Poisson variable with mean 1, and $e^{-1}$ is the Poisson chance of none. The $k$-th term counts, on average, the sets of $k$ people who all get their own hats.

For the arcs, set $na = \ln n + x$ and let $n$ grow. The $k$-th term of Stevens’s sum, $\binom nk(1 - ka)^{n-1}$, tends to $e^{-kx}/k!$, and the sum tends to $\sum_k (-1)^k e^{-kx}/k! = e^{-e^{-x}}$. That is the Poisson chance of none with mean $e^{-x}$: the number of gaps longer than $a$ is nearly a Poisson variable with mean $e^{-x}$, in exactly the way the number of fixed points of a random permutation is nearly a Poisson variable with mean 1. The $k$-th term counts, on average, the sets of $k$ gaps that are all too long, as it counted sets of $k$ people for the hats.

Both are instances of the same principle, sometimes called the Poisson paradigm: when many rare events are only weakly dependent, the number that occur is nearly Poisson, and the chance that none occur is $e^{-\mu}$ for the expected number $\mu$. Inclusion and exclusion is the exact form of that principle, valid at every size, and the Poisson limit is what its terms become when the events thin out. The arcs make the weak dependence visible: two gaps compete for the same circumference, so long gaps slightly discourage each other, and that small discouragement is exactly the difference between $(1 - ka)^{n-1}$ and $(1 - a)^{k(n-1)}$, which vanishes in the limit. The same comparison the cells a permutation must miss made for forbidden positions in a grid, where each forbidden cell is a rare event and the rook polynomial is the inclusion–exclusion that counts them, is the discrete twin of the gaps on the circle.

A circle forced, and a circle free #

There is an older theorem about covering a sphere, and the contrast is worth drawing. The theorem of Lyusternik and Schnirelmann — that if a sphere is covered by a few closed sets, one of them contains a pair of opposite points — is the tool Lovász used in the colours a circle forces to colour Kneser graphs. That theorem is about every covering; this essay is about random ones. And three gaps and no more found that points placed by turning a circle through an irrational angle leave at most three different gap lengths, so that a carefully chosen sequence of points covers a circle with arcs only a little longer than $1/n$ — no logarithm at all. The logarithm is the price of independence: deterministic points can be spread to avoid long gaps, and random points cannot avoid them, because some gap is always about $\ln n$ times the average.

That is also why the question matters outside geometry. Covering a circle is the simplest model of sampling a periodic signal at random times, of placing sensors at random positions along a ring, or of sequencing a circular genome by random reads, where Eric Lander and Michael Waterman’s model of 1988 uses exactly these gap statistics to predict how many reads leave no stretch unread. In every case the answer has the same form: random coverage needs about $\ln$ of the number of pieces times as many pieces as perfect coverage would, and Stevens’s sum says exactly how many.

Exact for arcs of one length, open for random ones #

The chances are exact rationals for each fraction $a = p/q$ and each $n$, computed in whole-number arithmetic and converted to decimals only at the end, so the cancellation of terms in the thousands to $10^{-20}$ is real and not an artefact of rounding. The simulations agree with the exact values within five standard errors at every point checked, which tests the derivation of the formula rather than the arithmetic. The expected numbers of arcs are sums of exact chances, truncated once the chance of not covering falls below $10^{-12}$; the Gumbel figure is a simulation of the gaps, not a computation from the formula, and it agrees with the limit to the precision of twenty thousand samples.

The figures treat arcs of one fixed length. Arcs of random lengths, or arcs in two dimensions — discs dropped on a sphere or a torus — are much harder: the gaps no longer form a simple simplex, and the chance of covering has no closed formula. For discs on a torus the threshold is known in the limit, with the same logarithm and a different correction, but the exact finite answer is not.

Still open: covering in more dimensions #

Janson’s theorem extends to random caps on a sphere, random balls in a torus and random translates of any fixed convex shape, and in each case gives the number needed for coverage to within a Gumbel fluctuation. What it gives is a limit. For a finite number of caps on a sphere, the exact chance of covering is not known for any interesting case — there is no inclusion–exclusion over gaps, because the uncovered regions of a sphere are not intervals and cannot be listed — and computing it even numerically requires deciding, for each random placement, whether some tiny region has escaped, which is a delicate geometric search.

The one-dimensional sum also raises its own question about extremes. The Bonferroni bounds of the second figure are good only far into the tail of the sum, and for most of the range a few terms say nothing. Better bounds that use more information — the second and third moments of the number of long gaps at once — exist, and how sharply a fixed number of moments can bound the covering probability in the regime where it is moderate is a question about the shape of distributions that has been answered only in special cases.

Long enough, and still bare #

Fourteen random arcs, each a fifth of a circle, have almost three times its length between them and cover it only a third of the time, because the circle is covered exactly when no gap between their starting points exceeds a fifth — and inclusion and exclusion over the gaps that are too long gives Stevens’s exact sum. For sixty arcs of a fortieth its terms reach 4,901 and cancel to $2 \times 10^{-20}$; for arcs of a sixtieth it takes 392.6 random arcs on average, against sixty placed with care, the logarithm of a coupon collector with a little more. Read the other way, the sum is the law of the longest gap among random points, which is $\ln n/n$ plus a Gumbel fluctuation with mean Euler’s constant.