The birthday problem, worked out Image: Francesca Cesa Bianchi, CC BY-SA 3.0 IT

The birthday problem, worked out

How many people must be in a room before it is more likely than not that two of them share a birthday? Most people guess somewhere between 100 and 183. The answer is 23, and with 23 people the probability is 50.7 per cent. With 50 people it is 97 per cent, and with 70 it is 99.9 per cent. The result is called the birthday paradox, though nothing in it is paradoxical once you count the right thing.

Count the pairs, not the people

The intuition goes wrong because it compares 23 people with 365 days. The event we care about is "some two people share a birthday", a different event from "someone shares my birthday", and the number of pairs grows much faster than the number of people. With 23 people there are

\[ \binom{23}{2} = \frac{23 \times 22}{2} = 253 \]

pairs, and each pair has a chance of about 1 in 365 of matching. Two hundred and fifty-three chances at 1 in 365 is a lot of chances. That is the whole idea; the rest is making it exact.

The calculation

The direct route, adding up the probabilities of exactly one match, two matches, three people on one day, and so on, is a mess. The clean route goes through the complement: compute the probability that all 23 birthdays are different, and subtract from one.

Line the people up. The first person's birthday can be any day. The second must avoid one day, which happens with probability \(364/365\). The third must avoid two days, probability \(363/365\), and so on down to the 23rd, who must avoid 22 days. Assuming the birthdays are independent and each day equally likely,

\[ \mathrm{P}(\text{all different}) = \frac{365}{365} \times \frac{364}{365} \times \frac{363}{365} \times \cdots \times \frac{343}{365} = 0.4927. \]

So the probability of at least one shared birthday among 23 people is \(1 - 0.4927 = 0.5073\). The table gives the figure for a few group sizes.

People1020233040505770
Chance of a shared birthday11.7%41.1%50.7%70.6%89.1%97.0%99.0%99.9%

Fifty-seven people are enough for 99 per cent. You would need 367 to be certain, because only then do the pigeonholes run out, and the gap between 57 and 367 is the gap between "almost certain" and "certain" that probability is always drawing attention to.

A quicker approximation

Each of the 253 pairs fails to match with probability \(364/365\). If the pairs were independent, which they are not quite, the probability that no pair matches would be \((364/365)^{253} = 0.4995\), close enough to the exact 0.4927 for most purposes. A still simpler version uses the fact that \(1 - x \approx e^{-x}\) for small \(x\): with \(n\) people,

\[ \mathrm{P}(\text{at least one match}) \approx 1 - \exp\!\left(-\frac{n(n-1)}{2 \times 365}\right). \]

Setting this to one half and solving gives \(n \approx 1.18\sqrt{365} = 22.5\). That square root is the useful part. For a "year" of \(N\) days, the number of people needed for an even chance of a match is about \(1.18\sqrt{N}\), and the number of pairs needed is about \(0.69 N\).

The cousins of the problem

A football squad at a World Cup has 23 players, by regulation, and the birthday problem predicts that about half the squads should contain a shared birthday. Journalists check this every four years, and it has held every time; in 2014, 16 of the 32 squads had a pair.

A four-digit PIN has 10,000 possible values. How many customers before two of them probably share a PIN? The formula gives \(1.18\sqrt{10{,}000} = 118\). A bank with 118 customers would already expect a collision, and a bank with a million customers has every PIN used about a hundred times, which is why your PIN protects your card and not your identity.

In computing, a hash function turns a file into a short fingerprint, and two different files with the same fingerprint are a collision. A fingerprint of 128 bits has \(2^{128}\) possible values, which sounds safe, but the birthday arithmetic says that a collision becomes likely after about \(\sqrt{2^{128}} = 2^{64}\) files. That is the birthday attack, and it is the reason cryptographers size their fingerprints at twice the length that a naive calculation suggests.

Then there is the version people get wrong in the opposite direction. How many people must be in the room before it is likely that someone shares your birthday? Now the pairs that count are only the ones that include you, \(n - 1\) of them, and the answer is 253 people, not 23. The surprise of the birthday problem comes entirely from the difference between a match somewhere and a match with a particular person.

The assumptions

The calculation assumes that birthdays are independent and that every day is equally likely. Neither is exactly true. Births in most countries peak in late summer and dip around Christmas, and 29 February exists. Both departures from uniformity make matches slightly more likely, not less, because any clustering of birthdays onto fewer days raises the chance of a collision. Twins in the room break independence and raise the chance further. The textbook answer of 23 is therefore a slight overestimate of the number needed, and the real world is a little more coincidental than the calculation says.

That is the general lesson, and it is more useful than the number. Coincidences are common because the number of opportunities for a coincidence is large and goes unnoticed. Someone dreams of a plane crash the night before one happens, somewhere, in a world of eight billion dreamers; two people at a party have the same birthday; two lottery draws share four numbers. Before being impressed by a coincidence, count the pairs.

Unit 3 of the Statistics Masterclass works through the birthday problem as its first example of the complement rule and the multiplication rule, and goes on to the Monty Hall problem and to the question of what a positive medical test means, where the same habit of counting cases carefully does the work.

Learn statistics properly

The Statistics Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program