23 people
How many people need to be in a room before there is a better than even chance that two of them share a birthday?
Most people reason like this: there are 365 days, so you would need about half of that, around 180 people.
The real answer is 23.
Nothing about this is a trick or a paradox in the logical sense. It is called the birthday paradox because the true answer is so far from what intuition says. Seeing why intuition fails is useful well beyond birthdays.
Start. One person in the room. Nobody to share a birthday with.
- People
- 1
- Pairs
- 0
- Chance of a shared birthday
- 0.0%
The wrong question
The guess of 180 answers a different question: "how many people until someone shares my birthday?".
For that, each other person is one chance in 365 of matching you, and you really do need a few hundred people.
But the question was about any two people matching. You are not special. Ana could match Ben. Ben could match Cy. Every pair in the room is a separate chance.
Count the pairs
That changes the arithmetic completely. The number of chances is not the number of people. It is the number of pairs.
Example
How fast pairs pile up
2 people: 1 pair.
3 people: 3 pairs.
5 people: 10 pairs.
10 people: 45 pairs.
23 people: 253 pairs.
Each new person pairs up with everyone already in the room, so the 23rd person alone adds 22 new pairs.
With n people the number of pairs is n × (n − 1) ÷ 2. That grows roughly with the square of n. Double the people and you get about four times the pairs.
So 23 people is not 23 chances at a 1-in-365 shot. It is 253 chances. No wonder one of them comes up.
Working it out exactly
It is easier to calculate the opposite: the chance that nobody shares a birthday. Then subtract from 1.
The first person can have any birthday
365 out of 365.
The second must avoid the first
364 out of 365.
The third must avoid both
363 out of 365.
Keep going, and multiply them all together
For 23 people: (365 ÷ 365) × (364 ÷ 365) × (363 ÷ 365) × ... × (343 ÷ 365), which comes to about 0.493.
Subtract from 1
1 − 0.493 = 0.507. A 50.7% chance that at least two share a birthday.
def shared_birthday_chance(people):
all_different = 1.0
for i in range(people):
all_different *= (365 - i) / 365
return 1 - all_different
shared_birthday_chance(23) # 0.507| People | Chance that two share a birthday |
|---|---|
| 10 | 11.7% |
| 20 | 41.1% |
| 23 | 50.7% |
| 30 | 70.6% |
| 50 | 97.0% |
| 57 | 99.0% |
| 70 | 99.9% |
With 57 people it is 99% certain. You do not need anything like 365.
Why programmers care
Swap "people" for "items" and "birthdays" for "possible values", and this is the mathematics of collisions: two different things accidentally getting the same id, the same hash, the same random number.
The same square-root effect applies. If there are N possible values, expect a collision after roughly the square root of N items, far sooner than N.
| Situation | Possible values | A collision becomes likely around |
|---|---|---|
| Birthdays | 365 | 23 people |
| Random 32-bit ids | 4.3 billion | 77,000 items |
| Random 64-bit ids | 18 billion billion | 5 billion items |
That is why an id scheme that "has billions of possibilities" can still fail with thousands of users. The full story, with an animation, is in Random ID Collisions.
It also has a place in security. An attack that tries to find any two inputs with the same hash needs only about the square root of the number of possible hashes. This is called a birthday attack, and it is the reason secure hash outputs are made twice as long as you might think necessary.
Key takeaways
- With 23 people there is a 50.7% chance that two share a birthday.
- The surprise comes from counting people when you should count pairs.
- 23 people make 253 pairs, and the number of pairs grows with the square of the group.
- Work it out by multiplying the chances that each person avoids all the earlier ones, then subtracting from 1.
- The same effect makes random ids and hashes collide much sooner than expected.