About the Birthday Paradox | Pairs, the Calculation and Birthday Attacks

The paradox

Ask people how many guests a party needs before two of them probably share a birthday, and most will say about 180, half of 365. The real answer is 23: then the chance is 50.7%. With 57 guests it is 99%. It is called a paradox not because it is contradictory, but because it goes so strongly against our intuition.

Why intuition fails

In a room we unconsciously reason from ourselves: what is the chance that someone shares my birthday? With 365 days that chance is small. But the paradox is about all possible pairs in the room, not about a match with one particular person: A and B, B and C, A and C, and so on. With 23 people you can make 253 different pairs, and each of them could share a birthday.

Pairs grow with the square

n people make n × (n − 1) / 2 pairs: 10 people make 45 pairs, 23 make 253, 57 make 1,596 and 100 make 4,950. Each pair shares a birthday with chance 1/365, so 253 pairs give on average 253/365 ≈ 0.69 shared pairs. Doubling the group roughly quadruples the pairs, and that is why the chance of a shared birthday shoots up.

The calculation step by step

The easiest way is to work out the chance that nobody shares a birthday, and subtract it from 100%. The first person claims any day. The second person has a chance of 364/365 of not having the same birthday. The third has a chance of 363/365 of differing from the first two, and so on. For 23 people:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49.3%

Because the chance that everyone has a different birthday is 49.3%, the opposite, at least one shared birthday, has a chance of 100% − 49.3% = 50.7%.

Someone with your birthday

The chance that someone shares your own birthday is a different question. Each of the other n − 1 people misses your birthday with chance 364/365, so the chance that someone has it is 1 − (364/365)ⁿ⁻¹. With 23 people that is only 5.9%, and you need 253 others before it passes 50%. Only 22 of the 253 pairs in a group of 23 include you.

The square root rule and birthday attacks

For N equally likely values, a repeat becomes likely after about 1.2 × √N draws: √365 ≈ 19, and 1.2 × 19 ≈ 23. This matters a great deal in computer security. Attackers use birthday attacks to find two inputs with the same cryptographic hash, a collision, for example to forge a digital signature. Thanks to the birthday paradox they need far fewer tries than intuition suggests: about 2⁶⁴ for a 128-bit hash instead of 2¹²⁸. That is why modern hashes such as SHA-256 have long outputs.

Explore it in PictorX

Open the birthday paradox and a group of 23 people forms on a circle, one person at a time. Every newcomer adds a line to each person already there, and the caption counts the pairs. Their birthdays drop onto a calendar, and a day with two or more lights up. Below, the calculation for the group size stands next to the share of tested groups that had a shared birthday, and the chart shows the chance for every group size, for any two people and for someone with your birthday. Add people one by one, choose 2 to 366 people, test up to 100,000 groups at up to 10,000 a second, or test every group size and watch the dots trace the curve.

Frequently asked questions

What is the birthday paradox?

The surprising fact that in a group of only 23 people, the chance that two of them share a birthday is more than 50%: 50.7%.

Why are 23 people enough?

Because 23 people make 253 pairs, and every pair is a chance for a shared birthday. We tend to count only the 22 pairs that include ourselves.

How many people do you need for a 99% chance?

57. With 70 people the chance is 99.9%, and with 366 people a shared birthday is certain, because there are only 365 days.

What is a birthday attack?

An attack on a cryptographic hash that uses the birthday paradox: among about √N random inputs, two probably have the same hash value out of N possible values, so collisions are found far sooner than by trying to match one given hash.

Does the result change with real birthdays?

Hardly. Real birthdays are not spread perfectly evenly over the year, and an uneven spread makes a shared birthday slightly more likely. 29 February, which comes once every four years, makes almost no difference.