A sum stopped early still says something

Nobody gets their own hat counted the arrangements that avoid every one of a list of conditions by an alternating sum: all of them, less those meeting each condition, plus those meeting each pair, less each triple, and so on to the end. It noticed along the way that the running total lands on alternate sides of the answer — 24, 0, 12, 8, 9 around a true 9 — and treated that as a feature of the route to an exact count.

The alternation is more useful than the count. It holds in every inclusion–exclusion problem, it can be proved in a line, and it means that a sum stopped early is a bracket, not a guess. Most of the time the full sum has far too many terms to compute; the first two or three are cheap, and they already pin the answer between two numbers.

A die that leaves a face out #

Roll a six-sided die repeatedly. What is the chance that, after $m$ rolls, some face has never appeared? The event is a union: face 1 missing, or face 2 missing, and so on. The chance a particular face is missing is $(5/6)^m$, and there are six faces, so the first guess is $6 \cdot (5/6)^m$.

That overcounts the rolls missing two faces, which it counted twice. There are 15 pairs of faces, and the chance a given pair is missing is $(4/6)^m$, so subtract $15 \cdot (4/6)^m$. Then add back the triples, $20 \cdot (3/6)^m$, subtract the quadruples, and so on. The full sum is exact, and the figure checks it against a completely different computation — following, roll by roll, the chance of having seen exactly $j$ faces.

The three dashed curves are the sum stopped after one, two and three terms. The first always lies above the truth, the second always below, the third above again, at every number of rolls from 6 to 40. At 12 rolls they read 0.673, 0.557 and 0.562, and the truth is 0.562: three terms have already landed within a thousandth. After 13 rolls the chance of a missing face first drops below a half.

The same curve answers a waiting question. The chance of a missing face falls from 0.562 at 12 rolls to 0.486 at 13, so half the time all six faces have appeared by the thirteenth roll. The average wait is longer, 14.7 rolls, which is six times $1 + \tfrac12 + \tfrac13 + \tfrac14 + \tfrac15 + \tfrac16$: the first new face takes one roll, the second takes $6/5$ rolls on average, and the last, with only one face left to find, takes six. The slow hunt for the last face stretches the average past the middle, and the curve’s long tail to the right is that stretch.

How good a stop is #

The inequalities measure their own error. Two consecutive stops bracket the truth, and they differ by exactly one term, so stopping after $t$ terms is wrong by at most the next term. At 12 rolls, stopping after two terms gives 0.557, and the third term is 0.00488; the truth is therefore within 0.00488 of 0.557. It is 0.562, off by 0.00485, which uses almost the whole allowance — the bound is not merely safe but close to sharp here.

That is what makes a stopped sum usable in practice. Computing one more term tells how much the previous stop could have been wrong by, so the work can stop as soon as the next term is below the precision wanted, with a guarantee rather than a hope.

Every term, and the side each stop lands on #

At ten rolls the terms are laid out one by one. The first, $6 \cdot (5/6)^{10}$, is about 0.969; the second takes away 0.260; the third adds 0.0195; the fourth takes away 0.00025; the fifth adds about a ten-millionth; the sixth adds nothing at all, because the chance that all six faces are missing after ten rolls is zero. The running total crosses the true value at each of the first four stops and then sits on it.

The terms shrink fast because they are powers of fractions that shrink: $(5/6)^{10}$, $(4/6)^{10}$, $(3/6)^{10}$. When the events are rare, each level of overlap is rarer still, and the sum can be stopped as soon as the next term is smaller than the precision wanted. The table is also a count of something else: the rolls that show every face are the onto maps from ten rolls to six faces, and the same alternating sum counts them — 0.2718 of all the ways ten rolls can fall.

The same sum counts onto maps #

Turned around, the calculation counts something that has no obvious relation to dice. A sequence of ten rolls that shows every face is a way of sending ten labelled rolls onto six faces with no face left out — an onto map. Their number is the full alternating sum with whole numbers in place of probabilities:

$$6^{10} - 6 \cdot 5^{10} + 15 \cdot 4^{10} - 20 \cdot 3^{10} + 15 \cdot 2^{10} - 6 \cdot 1^{10}.$$

That comes to 16,435,440, and dividing by the 60,466,176 possible sequences gives the 0.2718 in the table. The count also factors: it is $6! = 720$ times 22,827, where 22,827 is the number of ways to split ten rolls into six unlabelled non-empty groups, a Stirling number of the second kind. Inclusion–exclusion is the standard way to compute those numbers, and every stop of the sum brackets them just as it bracketed the chance — above, below, above — for anyone who needs only an estimate of how many ways a set can be split.

Why the stops alternate #

The proof looks at a single outcome and asks how many times the stopped sum counts it. Suppose an outcome belongs to exactly $j$ of the events — here, a sequence of rolls missing exactly $j$ faces. The first term counts it $j$ times, once for each event it is in. The second term subtracts it once for each pair of those events, $\binom{j}{2}$ times, and the third adds it back $\binom{j}{3}$ times.

Stopped after $t$ terms, the outcome has been counted $\binom{j}{1} - \binom{j}{2} + \cdots \pm \binom{j}{t}$ times, and a standard identity about the rows of Pascal’s triangle — the alternating sums of the entries that count routes — gives that total as

$$1 - (-1)^t \binom{j-1}{t}.$$

After an odd number of terms that is $1 + \binom{j-1}{t}$, at least 1; after an even number it is $1 - \binom{j-1}{t}$, at most 1. Every outcome in the union is counted at least once after an odd stop and at most once after an even stop, and outcomes in none of the events are never counted at all. Adding over all outcomes, the stopped sum is at least the size of the union after odd stops and at most it after even ones. An outcome in three events shows it: counted 3 times after one term, 3 − 3 = 0 times after two, and 3 − 3 + 1 = 1 time after all three.

These are the Bonferroni inequalities, after Carlo Emilio Bonferroni, who set them out in 1936. The first of them, that a union is no more likely than the sum of its parts, is older and simpler still: Boole’s inequality, or the union bound.

The hat problem, read as brackets #

Six hats: 720 arrangements, and the sum for those in which nobody gets their own hat is 720 − 720 + 360 − 120 + 30 − 6 + 1 = 265. Read as brackets, the running totals say that the answer is at most 720, at least 0, at most 360, at least 240, at most 270, at least 264 — and then exactly 265. The brackets narrow from both sides at once.

The hat problem is the wrong place to stop early, because its terms do not shrink quickly — the second term is as large as the first — and the full sum is only seven terms anyway. But the picture is the same as the die’s, and it is worth seeing that the exact count of the earlier essay was the end of a sequence of guaranteed bounds, each of which could have been reported on its own.

Birthdays, where the bracket breaks #

Twenty-three people computes the chance of a shared birthday exactly, by multiplying the chances that each new person misses everyone before. Inclusion–exclusion sees the same event as a union over pairs: the chance a given pair shares a birthday is $1/365$, and there are $\binom{k}{2}$ pairs, so the union bound gives $\binom{k}{2}/365$. Any two different pairs, overlapping or not, share their birthdays with chance $1/365^2$, so the second term subtracts the number of pairs of pairs over $365^2$.

At 23 people the truth, 0.507, sits between 0.454 and 0.693, as the inequalities promise. But the bracket is already wide, and it gets worse fast: the union bound passes 1 at 28 people, where it says nothing, and the two-term bound goes negative at 39. The bracket is only as good as the events are rare. With 23 people there are 253 pairs, each with a small chance, and a small chance multiplied by 253 is no longer small — the overlaps matter, and a few terms cannot account for them.

That is the practical rule the figures teach. The union bound is an excellent estimate precisely when it is small, and the second term then says how much better it is; once the bound approaches 1, stopping early has stopped being informative.

Counting numbers free of small primes #

The sieve of crossing out the composites removes the multiples of each prime in turn, and inclusion–exclusion counts what survives. Of the numbers from 1 to 1000, those divisible by 2 number 500, by 3 number 333, and so on; those divisible by both 2 and 3 are the multiples of 6, 166 of them; and the alternating sum over all 64 products of the primes 2, 3, 5, 7, 11 and 13 leaves exactly 190 numbers divisible by none of them — the same 190 a direct count finds.

The stops show both of the method’s faces. After one level the count is $-341$, a lower bound but a useless one. After two it is 336, then 175, then 190 — and there it stays, because every product of five of these primes exceeds 1000 and contributes nothing. In a sieve the terms eventually vanish outright, since a product larger than $N$ has no multiples up to $N$.

The smooth estimate is instructive in a different way. Ignoring the rounding, a proportion $(1 - 1/2)(1 - 1/3)(1 - 1/5)\cdots$ of numbers survives, which predicts 191.8, and the product form is the one the sieve written as a product takes. Each term of the exact sum rounds $1000/d$ down, and with 64 terms the rounding errors can accumulate. With six primes the damage is under two; with all the primes below $\sqrt{N}$ for large $N$, the number of terms is astronomically larger than the count itself, and the rounding swamps the answer.

Why sieves stop early on purpose #

That swamping is the reason sieve methods in number theory truncate inclusion–exclusion deliberately. Viggo Brun, around 1919, stopped the sum after a carefully chosen level, accepting a bracket in exchange for keeping the rounding errors under control, and used the upper bound to prove that the twin primes are rare enough for the sum of their reciprocals to converge — whereas the sum of the reciprocals of all the primes diverges.

That was a theorem the exact sum could never have delivered, because the exact sum was unusable. An inequality with few terms beat an equality with too many. The whole subject of sieve methods grew from the observation that Bonferroni’s brackets, applied with care about which terms to keep, answer questions that the full inclusion–exclusion formula only restates. The sieve that cannot finish meets the same limitation from the side of primes.

The union bound in probability #

The first inequality, a union no more likely than the sum of its parts, is the most used estimate in probability. To show that none of a large number of bad things happens, it is enough to show that their chances add up to less than 1, with no need to know how the bad things overlap. Proofs that some structure exists — a colouring with no forbidden pattern, a code with no short errors — very often come down to exactly that sum.

The classic instance is Erdős’s argument of 1947. Colour each of the links among 32 people red or blue by tossing a coin. A particular group of 10 people has 45 links among them, so the chance that all 45 come out the same colour is $2 \times 2^{-45}$. There are 64,512,240 groups of 10, and the union bound puts the chance that some group is all one colour at no more than about $3.7 \times 10^{-6}$. That is less than 1, so some colouring of the 32 people has no group of 10 whose links all match. The first term of inclusion–exclusion has proved that a colouring exists without producing one, which is the subject of the colouring nobody has ever seen; six people at a party is the smallest case in the other direction, where every colouring of the links contains a matching group of three.

The second inequality supplies the other side. When the union bound says a chance is small, subtracting the pairwise overlaps gives a lower bound, and together the two say the chance is small but not negligible. The second-moment method of finding a threshold with two moments is a close relative: where the union bound uses the first moment of a count of bad events, the second-order corrections use pairs of them.

A bracket that cannot say which end is nearer #

Every full sum drawn is small enough to compute. The die has six events and the sieve has 64 products, so the exact value is always available for comparison. The situations where stopping early matters — hundreds of events, or primes up to the square root of a large number — are exactly the ones no figure can check against an exact answer.

The rarity condition is described, not measured. The birthday figure shows the bracket breaking as events become common, but no single number marks where stopping early stops being useful; that depends on how much precision is wanted and how fast the terms shrink.

And the bracket says where the truth is, not which end is nearer. The inequalities put the answer between consecutive stops; they do not say which stop is closer. On the six hats the stop after three terms, 360, lies 95 above the answer and the stop after four, 240, lies 25 below it, and nothing in the inequalities predicts that the lower end is the better one.

Still open: how much the sieve can see #

Brun’s truncation, and the sieves built on it since, can bound how many numbers survive the removal of small primes very accurately — but they run into a barrier for the primes themselves. The parity problem, identified by Selberg, shows that sieves of this kind cannot distinguish numbers with an even number of prime factors from those with an odd number, so on their own they cannot prove that infinitely many twin primes exist. Whether there are infinitely many twin primes is open, and the best result, that infinitely many pairs of primes lie within 246 of each other, needed ideas beyond the classical sieve to reach.

When the exact answer is too long, keep the bracket #

Inclusion–exclusion is usually presented as a formula whose value is the answer. Stopped anywhere, it is also a pair of guaranteed bounds, alternately above and below, and that is the form in which it survives at scale: in the union bound that powers a thousand existence proofs, in the corrections that sharpen it, and in the sieves that counted twin primes when the exact formula could not.

When a sum of corrections is too long to finish, look at whether its partial sums bracket the answer. If they alternate, the first few terms are not an approximation of unknown quality but a certificate of where the answer lies.