Why do two people in 23 probably share a birthday?

Here is the usual line of thought. A year has 365 days. Twenty-three people can cover at most 23 of those days, about 6% of the year, so a shared birthday ought to be rare. When someone asks “does anyone here share a birthday?”, we quietly hear “does anyone share my birthday?” — and that really is unlikely in a room of 23.

But the question doesn’t care whose birthday it is. Any two people will do. Before we count anything, let’s just try it.

Fill a room

In the figure below, each dot is one person, placed on a ring of the 365 days of the year, January at the top and running clockwise. Every birthday is drawn at random, with each day equally likely. When two people land on the same day, their dots stack up and turn red, and the first shared day is labelled.

If you pressed Add until a match a few times, you probably saw rooms of 15, 25, 30 — sometimes fewer than 10. Across many tries, half of all rooms have their first match by the 23rd person. And when you run 1,000 rooms of 23, about 507 of them have a match. The number after the ± is the honest size of the sampling error: a thousand random rooms can easily land three points either side of the true value.

Count pairs, not people

The reason is that a match needs two people, so what matters is how many pairs of people there are. Each person can pair with everyone else, and every pair gets counted twice that way, so a room of n people holds

n(n − 1) / 2 pairs.

That grows roughly like the square of n. Twenty-three people make 253 pairs. Each pair has only a 1-in-365 chance of matching, but 253 chances at 1 in 365 add up.

Now compare the question we usually hear. Of those 253 pairs, only 22 include you. The chance that one of the other 22 people shares your birthday is 1 − (364/365)²², about 5.9%. That is the number our intuition tends to reach for.

The pair count is a good guide but not the exact answer, because pairs are not independent: if Ann matches Ben and Ben matches Cat, then Ann matches Cat. The exact calculation is easier from the other side. Ask for the chance that nobody shares. The first person can have any birthday. The second must avoid one day: 364 out of 365. The third must avoid two: 363 out of 365. Keep going and multiply:

P(no match) = 365/365 × 364/365 × 363/365 × … × (365 − n + 1)/365

For 23 people this product is 0.4927, so the chance of at least one shared birthday is 1 − 0.4927 = 0.5073, or 50.7%. With 57 people it is 99.0%, and with 70 people 99.9%. To reach even odds of someone sharing your birthday you need 253 other people — as many people as there are pairs in a room of 23.

Any number of days

Nothing here is special to birthdays. Replace the 365 days with any number d of equally likely values — lottery numbers, seat numbers, the outputs of a computer program — and draw at random. A repeat becomes likely once the number of pairs, about n²/2, is comparable to d. Working that out exactly gives a simple rule: the chance of a repeat reaches 50% after about

n ≈ 1.1774 × √d draws,

where 1.1774 is √(2 ln 2). For 365 days the rule gives 22.5, and the exact answer is 23. For a million values it gives 1,177; the exact count is 1,178. Square roots shrink big numbers dramatically: a million values only need about a thousand draws.

This is why cryptographers care about birthdays. A hash function turns any file into a short fixed-length fingerprint, say 128 bits, so there are d = 2¹²⁸ ≈ 3.4 × 10³⁸ possible fingerprints. Finding a file that matches one particular fingerprint by trial is like waiting for someone with your birthday: about 2¹²⁸ tries. But finding any two files with the same fingerprint, a collision, is the birthday problem: about 1.18 × 2⁶⁴ ≈ 2 × 10¹⁹ tries. That is why a hash with b bits offers only about b/2 bits of protection against collisions, and why modern standards such as SHA-256 use outputs twice as long as the security level they aim for. The attack is called a birthday attack.

Real birthdays are not uniform

Everything so far assumed every day is equally likely. Real birthdays aren’t. In the United States from 1994 to 2003 — 39.7 million births, counted by the National Center for Health Statistics — late summer and September were busiest, and holidays were quiet, because many deliveries are scheduled. The busiest date, 19 September, had 11% more births than an average day; 25 December had 37% fewer.

Does that help or hurt the chance of a match? It helps. When some days are more popular, people crowd onto them, and crowding is exactly what makes matches. Mathematically, equal chances for every day give the fewest matches of any pattern.

At real rates the chance for 23 people rises by only a tenth of a percentage point, from 50.73% to 50.83%, and 23 is still the smallest room that passes a half. The uniform model is a very good approximation — and where it is wrong, it errs on the side of underestimating matches.