Twenty-three people, even odds

Put twenty-three strangers in a room. The chance that two of them share a birthday is a little better than a coin toss. Most people guess you would need a crowd of well over a hundred. The gap between the guess and the truth comes from counting the wrong thing.

What is being claimed

Assume every person's birthday is equally likely to be any of 365 days, ignore leap years, and choose people independently. How many people do you need before a shared birthday is a better-than-even bet? Grinstead and Snell work it out exactly: the answer is 23. With 22 people the chance of a match is about 0.476; with 23 it is 0.5072972, which is one minus their 0.4927028. Their example exists to show that, as they put it, “naive intuition cannot always be trusted in probability.” The tempting guess, they note, is about half of 365, or 183.

Why it is worth knowing

The same arithmetic governs any process that drops items into slots at random. Lehman, Leighton and Meyer use it for items landing in a hash table, where two items in one slot are a collision, and they point out that it underlies the “birthday attacks” that crack certain cryptographic systems. Collisions arrive far sooner than the number of slots suggests, and a system designed on the naive guess will meet them early.

Count pairs, not people

The guess of 183 counts people against days, as if each arrival had to hit one particular birthday. But a match can happen between any two people in the room. Twenty-three people form 23 × 22 / 2 = 253 pairs, and every one of those pairs is a separate chance to share a day. The number of pairs grows with the square of the crowd, so it overtakes 365 long before the crowd does.

The exact calculation is easier from the other side. Ask for the chance that nobody matches. Line the people up. The first can have any birthday. The second must avoid one day: probability 364/365. The third must avoid two: 363/365. Multiply down the line. With 23 people the product falls to 0.4927028, so a match has the better odds.

Why the square appears

Lehman, Leighton and Meyer bound that product neatly. Each factor is one minus a small fraction, and one minus a small number is less than e raised to minus that number. Multiplying the factors adds the exponents, and the fractions add up to n(n−1)/2 divided by 365. That numerator is exactly the number of pairs. So the chance of no match is below e to the power of minus (pairs / 365). Our arithmetic: at 23 people that bound is almost exactly one half.

Their rule of thumb follows. With d days in a year and about the square root of 2d people, the chance of a match is about 1 − 1/e, roughly 0.632. For 365 days that is 27 people, and they give the true value as about 0.626. Their own example is a class of 95 students: comparing 95 to 365 you might guess about one in four, but a match is more than 99.999% certain. They also compute that such a class should expect about 12.23 matching pairs. Grinstead and Snell's Table 3.2 tells the same story: at 40 people the chance of no match is 0.1087682, and at 100 it is 0.0000003. An exercise in their book shows that for a year of n days the even-odds crowd grows like the square root of 2 ln 2 × n. For 365 that gives 22.5 (our arithmetic), close to the exact 23.

What the model leaves out

Real birthdays are not spread evenly over the year, and both books say so. Grinstead and Snell call it “intuitively clear (but not easy to prove)” that uneven birthdays make a match even more likely at 23. The problem does not seem to have a very old history: they trace problems of this type to R. von Mises, in a paper dated 1938–39, and it was made popular by William Feller's textbook in the 1950s.

In short

A shared birthday needs only two people out of the whole room, not one person out of 365 days. Twenty-three people make 253 pairs, the pairs grow with the square of the crowd, and at 23 the chance of a match first passes one half.