The Birthday Problem and Collisions
Why 23 people is enough for a shared birthday, and where else the same maths ambushes you.
In a room of twenty-three people, there is a better than even chance that two share a birthday. Most people guess the answer is somewhere near a hundred and eighty.
The reason the intuition fails is a question-substitution: people compute their own chance of sharing with someone else, which is small, rather than the chance that any pair shares, which is not.
The same square-root behaviour shows up wherever repeated draws are made from a fixed pool, which makes it far more practically useful than a party trick.
The calculation
The direct approach is to compute the probability that everyone's birthday is different and subtract from one. The second person must avoid one date, so 364/365. The third must avoid two, so 363/365. Multiply those fractions down the room.
By 23 people the product of those fractions falls just below 0.5, so the probability of at least one shared birthday rises just above it — 50.7%, to be precise. By 30 people it is 70.6%, by 50 it is 97.0%, and by 70 it is 99.9%.
The reason it climbs so fast is the number of pairs. Twenty-three people form 253 distinct pairs, and each pair has a 1-in-365 chance of matching. Two hundred and fifty-three chances at 1-in-365 gives you roughly even odds, which is exactly what the calculation produces.
Probability of a shared birthday, by room size
- 10 people: 11.7% · 20 people: 41.1% · 23 people: 50.7%
- 30 people: 70.6% · 50 people: 97.0% · 70 people: 99.9%
- 23 people form 253 pairs, which is why it crosses a half so early.
The substituted question
Ask someone to estimate and most will implicitly answer a different question: what is the chance somebody shares my birthday? That is a much smaller number — in a room of 23 it is about 6% — and it scales linearly with room size rather than quadratically.
The difference is between one person against 22 others, and every pair against every other pair. The first grows with n, the second with n squared over two, and the gap between them widens fast.
To get to even odds on the substituted question you do need around 253 people, which is close to the number people usually guess. The guess is not random; it is the correct answer to the wrong question.
The general rule: square root of the space
The birthday result generalises. To reach roughly even odds of a collision when drawing from a space of N equally likely values, you need about 1.18 times the square root of N draws — for practical purposes, the square root of N.
That is a far smaller number than intuition suggests for any large N. From a million possibilities you expect a collision after about a thousand draws. From a billion, after about thirty-four thousand.
The rule is worth memorising because it comes up constantly: any time something is drawn repeatedly from a fixed pool and you care whether two draws match, the answer is around the square root of the pool size.
- 365 days: even odds at about 23 people.
- 10,000 four-digit PINs: even odds of a repeat at about 118 people.
- 1,000,000 values: even odds at about 1,000 draws.
- The rule of thumb is √N draws for even odds of a collision.
Where it shows up in practice
Random identifiers are the most common case. A four-digit PIN has 10,000 possibilities, so in a group of 118 people you would expect two to have picked the same one — assuming they picked randomly, which they emphatically do not.
Repeated draws from a picker follow the same rule. Draw from a corpus of thirty-four charades prompts ten times and a repeat is more likely than not, which surprises people who feel the corpus is large.
In security it is the reason token and key lengths are chosen as they are: a system needs its identifier space large enough that the square root of it still exceeds the number of identifiers it will ever issue, which is why a 128-bit identifier is used where a 64-bit one would seem ample.
The assumptions, and how much they matter
The standard calculation assumes birthdays are uniformly distributed across the year and that people in the room are independent. Neither is exactly true: births vary by month and by day of the week, and any room might contain twins.
Non-uniformity makes collisions more likely, not less, so the 23-person figure is a conservative estimate. Real-world data pushes the crossover point marginally lower rather than higher.
The assumption that matters more is independence, and it fails in rooms selected in ways correlated with birth date — a school year group, for instance, is drawn from a narrow band of dates and will show far more collisions than the general formula predicts.
Frequently asked questions
Why is 23 enough?
Because 23 people form 253 distinct pairs, and each pair has a 1-in-365 chance of matching. That many chances gives roughly even odds.
Why do people guess so much higher?
Because they answer a different question — the chance somebody shares their own birthday, which needs around 253 people for even odds. The guess is the right answer to the wrong question.
What is the general rule?
For a pool of N values, even odds of a collision arrive after about the square root of N draws.
How does this apply to PINs?
A four-digit PIN has 10,000 possibilities, so in a group of about 118 you would expect two randomly chosen PINs to match.
Does it apply to a random picker?
Yes. Drawing ten times from a corpus of thirty-four makes a repeat more likely than not, which is the same arithmetic.
Do uneven birthday rates change the answer?
They make collisions slightly more likely, so 23 is a conservative figure. Real data pushes the crossover marginally lower.
What about a school year group?
That breaks the independence assumption badly — the dates are drawn from a narrow band, so collisions are far more common than the formula predicts.
Why does this matter for security?
Because identifier spaces must be large enough that their square root still exceeds the number of identifiers ever issued, which is why 128-bit values are used where 64 would seem ample.
Tools that use this
Related guides
Sampling With and Without Replacement
The single decision that changes every number downstream of your draw.
Entropy and Password Strength
Bits of entropy, in plain terms, and why a longer random password beats a cleverer one.
How Shuffling Actually Works
Fisher-Yates, one swap at a time, and why it is the only shuffle worth using.