Birthday problem
Named by 10 essays across 3 fields — each of them below, with the objects they name alongside it.
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.
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 collision that finds a factor
A walk through the remainders modulo a number must eventually repeat, and it repeats modulo each hidden prime factor long before it repeats modulo the number. Pollard saw that the earlier repeat can be detected without knowing the prime — and that its timing is the birthday problem, so the cost is the square root of the factor.
Fourteen people within a day
Twenty-three people probably include two with the same birthday. Fourteen probably include two whose birthdays are at most a day apart, and seven, two within a week. The near miss has an exact formula, found by a trick that takes k days away after every birthday and turns the question back into the plain one on a shorter year, and the pattern behind every threshold is a single square root: a window of k days either side makes each pair 2k + 1 times as likely to collide.
A room where nobody is alone
Twenty-three people probably include two who share a birthday. How many are needed before every single person shares a birthday with somebody else in the room? The answer is 3,064 — more than it takes for every day of the year to be somebody's birthday — and the reason is a count of loners, which rises as the room fills, peaks at 134 when the room is the size of the year, and then falls so slowly that the last loner lingers for thousands of arrivals.
Two constants that do not walk at random
Pollard's factoring method trusts x² + c modulo a prime to repeat as soon as a random function would, after about √p steps. For c = 1 and c = 3 it does. For c = 0 and c = −2 it runs twelve to eighteen times longer on average, with almost no tail and enormous cycles, because those two maps are multiplication in disguise and their cycles are set by the order of 2 rather than by chance. Every other constant walks at random — including in the one respect in which x² + c is plainly not random, that it is two-to-one.
Square it and keep the middle
John von Neumann's first generator of random numbers squared a number and kept its middle digits. Followed from every four-digit seed, it never lasts more than 111 steps before a value repeats — a third of what the birthday problem allows a truly random rule — and one seed in five ends at zero for ever. A counter added before each squaring cures the collapse.
Every function is a tree with two marks
There are n to the n functions from n points to themselves, and n to the n − 2 trees on those points. André Joyal noticed in 1981 that the missing factor of n² is a choice of two points — a head and a tail — and that a function, read the right way, simply is a tree with a head and a tail. The reading turns Cayley's formula into one line and hands over a fact about random trees from the birthday problem.
Four lists find a collision sooner
Two lists of random 24-bit strings need about four thousand entries each before some string appears in both — the birthday bound. Ask instead for one string from each of four lists whose exclusive-or is zero, and lists of a few hundred suffice, because merging the lists in pairs manufactures the near-misses a direct search would have to find by luck. David Wagner's algorithm turns the square root into a cube root, and more lists into smaller roots.
Counting a population by its repeats
The birthday problem runs forwards from a known year to the chance of a match. Run it backwards and the matches measure the year: count how many pairs among the draws came out the same, and the number of kinds is about the number of pairs divided by that. It costs the square root of the population rather than a census of it — and when the kinds are unevenly common, what the repeats measure is not how many kinds there are but how many they behave like.
Named alongside it
The objects these essays reach for when they reach for this one.
CollisionSimulationExpectationVarianceComplementary countingExhaustive searchIndependenceIterationPoisson approximationPseudorandomnessRandom functionSquare root