The story of the birthday paradox

Imagine a classroom with 23 people. What is the chance that at least two of them share a birthday? Most people guess it is low. But the calculation says with 23 people it is about 50.7%, already more than half. This is called a “paradox”, but nothing contradicts itself. Intuition and the answer just disagree.

Why 23 is enough

The key is that any two people can match. That is a different question from finding someone who shares your own birthday. Among 23 people there are 253 different pairs. As the group grows, the number of pairs grows roughly with the square of the group size, so a match turns up sooner than you expect.

To calculate, find the chance that nobody matches and subtract it from 1. The first person can have any day, the second must avoid one day (364 out of 365), the third must avoid two (363 out of 365), and so on. Multiplying 364/365, 363/365 and so on gives the chance that everyone's birthday is different. This site's program confirms that 23 people give 50.7297%, that 22 people fall short of 50%, and that the chance never drops as the group grows. The same formula gives about 99.9% for 70 people, which is nearly certain. It only reaches 100% at 366 people, by the pigeonhole principle.

The calculation assumes 365 equally likely days and no leap years. Real birthdays are not evenly spread, but unevenness is said to make a match more likely, not less.

Who noticed it first?

The problem is said to have been considered around 1927 by the mathematician Harold Davenport, who never published it. The first published version is said to be Richard von Mises's paper of 1939. It is hard to name a single discoverer.

The same idea is used in cryptography. To find two different inputs that give the same hash value, you do not have to try every possibility; roughly the square root of the number of possibilities is enough. This is called a “birthday attack”, and it works for the same reason matching birthdays turn up so early.

How to think about it

• Don't count matches directly. There are too many ways to match. Compute the opposite, “everyone different”, and subtract from 1.
• Count pairs. Look at how many pairs of people there are, not just how many people. That shows how fast things grow.
• Be clear whose birthday you are looking for. It is “any two people”, not “someone with mine”. Mixing these up changes the answer completely.
• Try it many times. Gather random groups and count how many contain a match; the share lines up with the calculation.

On the puzzle page you can change the group size and watch the dot move along the curve, or run 1,000 groups and compare the result with theory. It is a simple model that ignores leap years and seasonal patterns.