Birthday problem
A Socratic walk-through of the birthday problem — reasoned out one step at a time, not lectured.
The question we started with
THE QUESTION #Why does a room of only twenty-three people probably contain a shared birthday?
Twenty-three people, three hundred and sixty-five days. The intuition is immediate and confident: twenty-three is a sliver of three hundred and sixty-five, so a shared birthday must be a long shot. Yet the answer is 50.7 percent — better than a coin. Before we do any arithmetic, it is worth asking what the intuition actually computed, because it did compute something, and it got a defensible answer to a different question.
Reasoning it through
REASONING #What did you picture when you read "twenty-three people"? Most people picture themselves standing among them, checking each face against their own birthday. That is twenty-two comparisons, and for that question the intuition is right — the chance that someone in the room shares your particular birthday is only about 6 percent.
But the question never mentioned you. It asked whether any two of them match. So how many chances are there really? Person one can be compared with twenty-two others; person two with the twenty-one not yet counted; and so on. That sum is 23 times 22 divided by 2 — 253 pairs. Notice what happened: twenty-three people, but two hundred and fifty-three opportunities. The intuition counted people. The problem counts pairs.
And why does that gap widen so fast? Add one person to a room of twenty-three and you have not added one chance, you have added twenty-three. Pairs grow roughly as the square of the head count while days on the calendar stay fixed at 365, so the two quantities cross far earlier than a head count suggests.
Now make it exact, which is easier than it looks if you flip the question. Rather than chase the many ways a match can happen, ask for the one way it cannot: everybody different. The second person must miss the first's birthday — 364 chances in 365. The third must miss both — 363 in 365. Multiply that chain down to the twenty-third person and you get 0.4927. So the chance of at least one match is 1 minus that: 0.5073.
Does that scale the way the pair-counting predicts? At 50 people there are 1,225 pairs and the probability is 97 percent. At 70 there are 2,415 pairs and it is 99.9 percent — with 70 people in a room of 365 days, near-certainty. Meanwhile the "shares my birthday" version crawls: it needs 253 people to reach even odds, which is a pleasing coincidence with the pair count and not a connection worth reading anything into.
The analogy
THE ANALOGY #Picture the room as a handshake instead of a headcount. Twenty-three people is a small crowd, but if everyone shakes everyone's hand exactly once, 253 handshakes happen. The question was never "how many people are here" — it was "how many handshakes are there, and does any one of them come up matching?"
Handshakes are independent events you could watch one at a time, whereas birthday pairings are not fully independent — if A matches B and B matches C, then A must match C — which is why treating the 253 pairs as 253 separate coin flips gives 50.0 percent rather than the exact 50.7.
Clarifying the model
THE MODEL #Three refinements, each of which someone always raises.
Birthdays are not uniformly distributed — September is crowded, late December and February 29 are thin. Does that break the calculation? It shifts it, but only in one direction: any departure from uniformity makes a match more likely, not less. Uniformity is the worst case, so 50.7 percent is a floor. Twins in the room push the same way.
The result is not a paradox in the logical sense, and nothing surprising is happening in the mathematics. What is surprising is a fact about human attention: asked about a group, we quietly substitute ourselves as one endpoint of every comparison. Almost every "improbable coincidence" story has the same shape — the teller counts the one match that occurred and forgets the enormous number of pairings that could have produced one.
Finally, this is not a curiosity. The same counting governs hash collisions: with N possible outputs, you should expect a collision after roughly the square root of N items, not N. That is why a 64-bit fingerprint is not remotely as safe as its length suggests, and it is the reason the attack is literally called a birthday attack.
A picture of it
THE PICTURE #How to readTwo questions plotted against the same axis. The upper curve is "do any two people here share a birthday" — it crosses 50 percent between 20 and 23 people and is nearly flat against the ceiling by 50. The lower, almost straight curve is "does anyone here share my birthday", which is still under 18 percent at 70 people. The gap between the curves is the whole illusion: the upper one grows with the number of pairs, the lower one only with the number of people.
What became clearer
WHAT CLEARED #The room's head count is not the quantity that matters. Matches are made by pairs, and pairs grow with the square of the head count, so 23 people quietly carry 253 chances against a 365-day calendar. Ask instead whether anyone matches one specific birthday and the count collapses back to 22 chances — which is exactly the question the intuition answered, and answered correctly.
Where to go next
ONWARD #- Why the same square-root rule sets the practical strength of cryptographic hashes.
- How many people are needed for three to share a birthday, and why that calculation is much harder.
- Why "one in a million" coincidences are expected daily in a population of millions.
Key terms
TERMS #| Term | What it means |
|---|---|
| Complement rule | computing the chance of "at least one" by finding the chance of "none" and subtracting from 1. |
| Pairwise comparison | a check between two members of a set; a group of n has n(n-1)/2 of them. |
| Birthday attack | an attack exploiting the fact that collisions in a hash of N possible values appear after about the square root of N attempts. |
Every term the collection defines is gathered in the glossary.