Pointer Walk

The Birthday Paradox

23 people, and a 50% chance two share a birthday. It is not 23 chances. It is 253 pairs.

Maths for ProgrammersBeginner7 min read

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.

Every pair is a chance to matchInteractive

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.

  1. The first person can have any birthday

    365 out of 365.

  2. The second must avoid the first

    364 out of 365.

  3. The third must avoid both

    363 out of 365.

  4. Keep going, and multiply them all together

    For 23 people: (365 ÷ 365) × (364 ÷ 365) × (363 ÷ 365) × ... × (343 ÷ 365), which comes to about 0.493.

  5. Subtract from 1

    1 − 0.493 = 0.507. A 50.7% chance that at least two share a birthday.

python
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
PeopleChance that two share a birthday
1011.7%
2041.1%
2350.7%
3070.6%
5097.0%
5799.0%
7099.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.

SituationPossible valuesA collision becomes likely around
Birthdays36523 people
Random 32-bit ids4.3 billion77,000 items
Random 64-bit ids18 billion billion5 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    6 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress