Independence
Named by 30 essays across 6 fields — each of them below, with the objects they name alongside it.
A bell curve assembled out of coin flips
Drop six hundred balls through a board of pegs, each bouncing left or right at random, and they pile up in a shape that can be predicted precisely. Nothing coordinated them.
Getting pi by dropping needles on the floor
Throw a needle at a lined floor enough times, count how often it crosses a line, and pi falls out. There is no circle anywhere in the experiment.
Twenty-three people
A room needs 253 people before someone probably shares a birthday with you. It needs 23 before two of them probably share one with each other. The gap between those numbers is the whole problem.
A walk that always comes home, until it does not
Step left or right at random, forever, and the walk returns to where it started with certainty. On a grid it also returns. In space it does not, and about a third of walks leave and never come back.
The door that was not opened
Three doors, one prize, a host who opens a losing door and offers a swap. Switching wins two times in three, and the reason is not about doors — it is about what the host was allowed to do.
Two worlds that both obey the rules
A statement is independent of a list of axioms when there is a structure satisfying the axioms where it holds and another where it fails. That is not a claim about what nobody has managed to prove — it is a proof that nobody can.
A sequence that explodes and still stops
Goodstein's sequence starting at 4 climbs past any number you care to name and reaches zero after about ten to the hundred and twenty million steps. The proof that it stops is a second sequence, running alongside it, that goes down.
The average settles and the wobble does not
Two theorems are usually met a page apart and sound as though one is a sharper version of the other. They are the same sums looked at through two different magnifying glasses: divide by the number of them and everything collapses to a point, divide by its square root and a shape appears.
The shape that averaging leaves alone
Adding independent quantities blurs their distributions together, and rescaling restores the width. Almost every shape is changed by that operation. Exactly one is returned unaltered, and that is why sums of unrelated things keep arriving at it.
An average that never settles
The average of many independent quantities is supposed to steady as their number grows. For one famous distribution it does not steady at all — the average of a thousand draws has exactly the same distribution as a single draw, and no amount of further averaging changes it.
The choice nobody can write down
Given finitely many pairs, picking one thing from each is a finite list of decisions and needs no justification. Given infinitely many, the list cannot be finished — and whether one exists anyway is an axiom, independent of everything else, whose consequences include a theorem most people refuse to believe.
Sampling where the answer lives
Monte Carlo error cannot be made to fall faster than the square root, so the only thing left to attack is the constant in front of it. Drawing points where the integrand is large, and dividing by how often they were drawn, leaves the answer alone and can shrink the noise many times over.
The colouring nobody has ever seen
Count the monochromatic sets a random colouring is expected to contain. If the average is below one, some colouring has none — and the argument is finished, having produced nothing anyone can look at.
The size that cannot be pinned down
There is no largest infinity, because no collection has as many members as it has sub-collections. What is not settled is whether anything sits between the first two — and that is not an open problem but a proved absence of an answer.
An ordinal as a growth rate
Index a family of functions by the ordinals, each one iterating the last, and the index becomes a measure of how fast a function grows. The point where the index leaves what arithmetic can prove is exactly where the Goodstein sequence became unprovable.
How many get their own hat
The chance that nobody gets their own hat settles on 1/e. The chance that exactly one person does settles on 1/e too, exactly two on 1/(2e), exactly three on 1/(6e) — the Poisson distribution with mean 1. The reason is a set of averages that come out exactly 1 at every size, and the counts reach the limit so fast that eight hats are within six ten-thousandths of it.
Any unevenness brings the match sooner
Real birthdays are not spread evenly across the year, and every such departure pushes the famous twenty-three down rather than up. The proof is one move on two days at a time, and what it leaves behind is a single number — the one ecologists use to count species.
A number larger than every number
Ask for a number bigger than 0, bigger than 1, bigger than 2, and so on for ever. Every finite piece of that request is granted by an ordinary number, so compactness grants all of it at once — in a structure that satisfies every sentence true of the whole numbers and still contains something beyond all of them. Nothing in first-order logic can say 'and nothing else'.
Fair bits from an unfair coin
Read a biased coin's flips in pairs, keep 01 as 0 and 10 as 1, and throw away the rest: the output is exactly fair, whatever the bias, and nobody needs to know the bias. The trick wastes most of the coin, the waste can be recycled almost up to the ceiling Shannon's entropy sets — and it fails quietly the moment the flips remember each other.
A function that adds and is nowhere a line
Every continuous function with f(x + y) = f(x) + f(y) is a straight line through the origin. Drop continuity and, given the axiom of choice, there are others — functions that add perfectly and whose graphs are scattered densely over the whole plane. A finite piece of the construction can be drawn exactly; the whole of it needs a basis of the real numbers that no one can write down.
Infinitely many guessers, finitely many wrong
An infinite line of people each wears a black or white hat, sees every hat in front and none of their own, and must guess their own colour. With a finite line, each guesser is right half the time whatever they agree in advance. With an infinite line and the axiom of choice, they can agree a strategy under which all but finitely many are right — and nobody can carry it out.
Two children and the sentence about one of them
A family has two children and at least one is a boy. The chance that both are boys is one in three — or one in two, or anything from one in three to certainty — and every one of those answers is right for some way the sentence could have come to be said. There is no host and no door, and the protocol is still the whole problem.
A majority wiser than its members
Condorcet's other theorem turns voting round: the voters no longer have preferences but judgements about a single fact, each a little more likely right than wrong. Then a simple majority of many of them is almost certainly right — 6,763 voters who are each right 51% of the time make a majority right 95% of the time. The theorem survives voters worse than a coin, if the average is better. It does not survive voters who share their mistakes, and when their skills differ the right rule weighs votes rather than counting them.
Evidence measured in decibans
Write a probability as odds and take the logarithm, and every piece of evidence becomes a length. A positive result on a good test is thirteen decibans; a negative one is minus twenty. Lay the lengths end to end from the prior and the posterior is where they stop, in any order. The rule fails in exactly one way — when two pieces of evidence share a cause — and Turing built a code-breaking method on the arithmetic.
Two weak sources make one fair bit
No fixed rule can turn every weakly random source into fair bits: for any rule, some source with almost full unpredictability makes it constant. Two independent sources are different. Multiply their bits in pairs, add, and keep the parity — and if the two together carry more unpredictability than the length of one, the result is nearly fair, whatever else the sources do. The reason is that the table of those parities is balanced on every large rectangle.
How often two generates every remainder
For some primes p, the powers of 2 run through every non-zero remainder before repeating; for others they get stuck in a smaller cycle. Among the primes up to two million the first kind make up 37.43% — and Artin predicted 37.40% in 1927 by treating each way of getting stuck as an independent accident. For the base 5 the same prediction is wrong, because two of the accidents are secretly the same one, and nobody can yet prove that 2 works for infinitely many primes at all.
![What a rule collects when every value comes from the same distribution. uniform on [0, 1]: best rule 0.995, one threshold 0.635 of E[max] at n = 200; exponential: best rule 0.905, one threshold 0.678 of E[max] at n = 200; Pareto, tail exponent 2: best rule 0.802, one threshold 0.714 of E[max] at n = 200; Pareto, tail exponent 1.2: best rule 0.802, one threshold 0.682 of E[max] at n = 200.](/f/what-a-rule-collects-when-every-value-comes-from-the-same-distribution-cdb6768b.svg)
When every value comes from the same hat
A rule that sees values one at a time and must keep or discard each on the spot can guarantee half of what a prophet collects, and no more, when the values come from different distributions. When they all come from the same one, the guarantee rises to 0.745 — and a single fixed threshold, set so that each value crosses it with chance 1/n, already secures 1 − 1/e. For bounded values the best rule collects nearly everything; only a heavy tail, where one enormous value carries the prize, keeps the gap open.
Certain of a coin that is not there
Bayes' theorem is exact, and it is only as good as the list of hypotheses it is given. Hand it a list that leaves out the truth and it does not hesitate: it becomes certain of the entry that is least wrong, in a precise sense — the one closest in Kullback–Leibler divergence — and if two entries are equally wrong it never settles at all. Hand it a model that assumes independence where there is none, and its intervals shrink as fast as they would for honest data while covering the truth less and less often.
Which vote finds the truth more often
A court that must decide two premises and their conjunction can vote on the premises or on the conclusion, and the two votes sometimes disagree. Suppose there is a right answer and each judge is more often right than wrong. Then the question has an exact answer: for three judges the conclusion vote is more often right when competence is below √½ and the premise vote above it, and in a large court the premise vote wins at any competence — while the conclusion vote turns out to be a built-in standard of proof.
The choice inside a countable union
A countable union of countable sets is countable: list each set, then walk the grid of all their members along its diagonals. The proof is two lines and every student meets it early. It also makes infinitely many arbitrary choices at once — one listing for each set — and without the axiom of choice the theorem can fail: there are consistent worlds in which the real numbers are a countable union of countable sets, and worlds in which countably many pairs of socks cannot be counted.
Named alongside it
The objects these essays reach for when they reach for this one.
ConvergenceExpectationBayes' theoremNormal distributionVarianceAxiom of choiceBinomial distributionChoice functionConditional probabilityConsistencyConvergence rateCounting argument