Matpic
mathematics, in pictures
Concept

Collision

Two things landing in the same place, which is what a counting argument produces when there are more things than places. Bounding how many places there are is therefore a way of proving that two things must coincide, without saying which two.

Named by 10 essays across 3 fields — each of them below, with the objects they name alongside it.

13 into 12. 13 items spread as evenly as 12 boxes allow. Even at their most even, some box holds 2, because 13 is more than 12 × 1.

More things than boxes

If there are more objects than containers, some container holds two. That is the entire principle, it is impossible to disagree with, and it settles questions that look nothing like it.

discrete · Pigeonhole When a shared birthday becomes likely. The chance that some pair in a group shares a birthday, against group size. It passes a half at 23 people, where the probability is 50.7%.

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.

probability · Birthday problem Waiting for all 6 kinds. One bar per new kind: the expected number of draws needed to see a kind not yet seen, rising as fewer of them are left, and adding to 14.70 draws in total.

How long until every one turns up

Draw at random from six equally likely kinds until all six have appeared. The wait is not six draws, and it is not sixty; it is fourteen point seven, and the number is a harmonic sum wearing a hat.

probability · Expectation A year of birthdays with a seasonal swing of ±50%, peaking in September. Bars for the 365 days of a model calendar with a seasonal swing of ±50%, peaking in September, drawn as each day's excess or shortfall against an even year. A shared birthday among 23 people has chance 54.86% against 50.73% for the even year, the first group with an even chance is 22, and the calendar behaves like 324.4 equally likely days.

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.

probability · Birthday problem The walk x² + 1 modulo 101, drawn as the letter ρ. Starting at 2 and squaring and adding 1 modulo 101, the walk visits 8 values once on a tail and then runs round a cycle of 9 values for ever.

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.

probability · Birthday problem How long x² + c runs before repeating, for four constants. Four survival staircases on a logarithmic scale of length: two following the birthday curve, and two for c equal to 0 and minus 2 lying far to the right.

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.

probability · Birthday problem Four seeds of the middle-square method, each until it repeats. Values against step for the four-digit seeds 6239, 1234, 5735, 4100 under the middle-square rule, each ending where a value repeats: after 111, 57, 31, 4 steps.

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.

computation · Pseudorandomness Four lists, merged in pairs, find a cancelling quadruple. A merge tree for four lists of 256 random 24-bit strings: two merges on the low 8 bits, then one on all 24, ending in 1 solution(s).

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.

probability · Birthday problem One shared birthday, as a measurement of the year. Histogram over 20000 rooms of the estimate T(T − 1)/2 from the first shared birthday, averaging 361 against 365, spread widely.

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.

probability · Birthday problem The cells a small generator can reach. m = 256, a = 229, 64×64 cells: plain 256 cells, 10 distinct gaps; scrambled 252 cells, 46 distinct gaps.

Birthdays spaced too evenly

Scatter n birthdays through a year of k days, sort them, and count how many of the gaps between neighbours repeat an earlier gap. For random birthdays the count is close to a Poisson variable with mean n³/4k. A linear congruential generator with m states, read in pairs, matches that law until the grid has as many cells as the generator has states, and then leaves it at once: at sixteen times as many cells, every run of the spacings count rejects it. The sample that catches it is about five times the cube root of the period — 8,192 outputs for a 32-bit generator, thirteen million for a 64-bit one — and the same states, scrambled before they are read, pass.

computation · Pseudorandomness

Named alongside it

The objects these essays reach for when they reach for this one.

Birthday problemExpectationPseudorandomnessVarianceComplementary countingIndependenceIterationPigeonhole principleSimulationSquare rootAlgorithmApproximation

All concepts