The Birthday Paradox: Why 23 People Is Enough

How many people do you need in a room before it’s more likely than not that two of them share a birthday? Most people guess somewhere between 100 and 183, because 183 is half of 365 and half sounds like a sensible threshold.

The answer is 23.

That’s true, it’s been checked by simulation and by counting real birthdays, and it feels wrong to almost everyone, including people who know probability. It’s called a paradox only because it feels like one. Nothing in the logic is contradictory. The surprise is the whole point.

Why it feels wrong

When people picture this, they usually picture themselves: what’s the chance someone shares my birthday? That really is small. In a room of 23, it’s only about 6%.

But the question isn’t about you. It’s about any two people in the room. And the number of pairs of people grows much faster than the number of people.

Think of a party. With 3 people there are 3 pairs. With 5 there are 10. With 10 there are 45. With 23 there are 253. Every one of those is a chance for a match, and chances add up quickly.

Count the pairs

In a room of 23 people, each person can be paired with 22 others. That’s 23 × 22 = 506, but that counts every pair twice (Ann and Bob, and Bob and Ann), so there are 253 different pairs.

Each pair has a 1 in 365 chance of sharing a birthday. With 253 chances at a 1 in 365 event, a match stops looking unlikely. A rough check: 253 ÷ 365 is about 0.69, so you’d expect around two thirds of a match, and the chance of at least one, once you allow for overlaps, comes out close to a half.

The exact calculation

It’s easiest to work out the chance that nobody shares a birthday, then take that away from 1.

1. The first person can have any birthday.
2. The second must avoid the first: 364 out of 365 days work.
3. The third must avoid both: 363 out of 365.
4. …and so on, down to the 23rd person: 343 out of 365.

Multiply those together: 364/365 × 363/365 × … × 343/365 comes to about 0.493. So the chance that nobody matches is 49.3%, and the chance that at least two people do is 50.7%.

This trick, working out the chance that something doesn’t happen and subtracting from 1, is one of the most useful in all of probability. “At least one” questions are usually hard to reach head-on and easy to reach from the other side. If you’ve ever wondered how to answer “what’s the chance I get at least one six in four rolls”, the same move works.

How fast it grows

The curve is much steeper than most people expect:

By 57 people, you can bet almost any amount on a shared birthday. Only at 366 people is it certain, by the pigeonhole principle: you’d have run out of days.

A different question has a very different answer

Here’s the best way to feel the difference between “any pair” and “my birthday”. The same room, two questions:

For the first, 23 people is enough. For the second, you’d need about 253, more than half the days in the year. The reason is that only the pairs that include you count. In a room of 23, that’s just 22 pairs out of 253. It’s easy to confuse the two questions because they sound alike.

This is the commonest way to be wrong about the birthday problem: answering a question about you when the question is about anyone.

A real test: the presidents

You can check it on real data. Of the US presidents, two of them, James K. Polk and Warren G. Harding, were born on 2 November. With more than 40 people in the sample, the chance of at least one matching pair is above 90%, so it’s unremarkable.

The same holds for football matches: with 22 players on the pitch plus the referee, you have a room of 23, and in about half of all matches, two of them will share a birthday. Try it with a school class of 30 or a team of 40. It works better than most card tricks.

Variations that are just as surprising

Once you’ve counted pairs, you can ask nearby questions, and the answers are just as counter-intuitive.

• Birthdays within a day of each other. If “near” means the same day or the next one, you only need 14 people for even odds, because each pair now has three ways to match.
• Three people sharing a birthday. You need about 88 people for even odds of a triple, because triples are much rarer than pairs.
• Two groups. If you have two separate groups, say two classes of 23, the chance that someone in one shares a birthday with someone in the other is also high, because the pairs run across the groups: 23 × 23 = 529 of them.
• Other dates. The same arithmetic applies to anything with many possible values: phone numbers that end in the same four digits, cars with similar numberplates, people in a group who share a first name.

Try it on real data

It’s easy to test. Take any list with a few dozen dates in it: the members of a sports squad, the birthdays on a class register, the Wikipedia pages of people born in a given year. Count how many have a match. You’ll find the shared birthday much more often than you’d expect. After a few tries you stop being surprised, which is exactly what the maths predicts.

Where it matters beyond parties

Cryptography. Computers sometimes need to check whether two different inputs produce the same “hash”, a short fingerprint of data. Finding such a collision by brute force looks like it should take a number of tries equal to the number of possible fingerprints. The birthday effect says it takes only about the square root of that number. This is why a 128-bit hash gives only about 64 bits of protection against collisions, and why security designers use bigger ones than a naïve count suggests.

Databases and IDs. If you assign random IDs, clashes appear far sooner than the size of the ID space suggests. A system of 100,000 users with random 32-bit IDs has about a 70% chance of at least one clash.

Coincidences. This is the broader lesson. Statisticians Persi Diaconis and Frederick Mosteller called it the law of truly large numbers: with enough people and enough days, extremely improbable things are bound to happen to somebody. If a one-in-a-million coincidence can happen to any of a million people each day, it’ll happen to someone most days. It’s not a miracle. It’s the birthday problem at scale.

What to take from it

Our minds are good at noticing that something is surprising for me, and bad at counting how many chances there were for something surprising to happen to anyone. That’s why we’re astonished when we meet a stranger who shares our birthday, but not when we spot a coincidence among any two of the next hundred people we meet.

The practical test is to ask, of any coincidence, “how many chances were there?” A match between you and one other person is rare. A match somewhere among everyone is almost guaranteed. The more pairs there are, the less a coincidence should surprise you.

The probability test has the birthday question and a few others where counting the right things changes the answer.