The birthday paradox

Here is a bet you should take. Get 23 people in a room, and it is more likely than not that two of them have the same birthday. With a whole year of 365 days to spread across, that sounds far too few. Most people guess you would need closer to 180.

The mistake is thinking about yourself. If you walk in and look for someone who shares your birthday, then yes, you would need a huge crowd. But that is not the question. The question is whether any two people match, and that is a different beast.

Count the pairs instead of the people. Two people make one pair. Three people make three pairs. By the time you have 23 people, there are 253 different pairs, and every single pair is its own little chance for a match. With that many chances, a hit becomes likely fast.

Keep adding people and the odds climb steeply. At 50 people it is about 97%, and by 70 it is 99.9%, all but guaranteed. The widget shows the curve shooting up and the pairs piling on. It is called a paradox not because anything is contradictory, but because the true answer is so much smaller than your gut insists.

The clean way to get the number is to compute the opposite: the chance that no two people share a birthday, then subtract from one. Working out "nobody matches" is easy, because you can add people one at a time.

The first person can have any birthday. The second person, to avoid a clash, must miss that one day, so 364 of 365 days are safe. The third must miss two days, leaving 363 of 365. Each new person has fewer free days. Multiply those fractions together:

\[ P(\text{no match}) = \frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}\cdots\frac{365-n+1}{365}. \]

For \(n = 23\) this comes to about 0.493, so the chance of at least one shared birthday is \(1 - 0.493 = 0.507\), just over half. That is the whole result: 23 people, better than even.

Why it grows so fast. The engine underneath is the number of pairs. With \(n\) people the count of pairs is \(\binom{n}{2} = \tfrac{n(n-1)}{2}\), which grows with the square of \(n\). At 23 people that is 253 pairs. Since each pair shares a birthday with probability \(1/365\), the rough number of matches you would expect is about \(253/365 \approx 0.69\), already close to one. Double the people and you roughly quadruple the pairs, which is why the curve is so steep.

The trap. The reason the answer feels wrong is that people quietly swap it for a different question: how many others before someone shares my birthday? That version only counts the pairs that include you, just \(n\) of them rather than \(n^2\), so it really does need about 253 people for an even chance. Same room, two very different questions.

One honest caveat. The calculation assumes birthdays are spread evenly over the year and are independent. Real birthdays clump a little, with seasonal peaks and far fewer on 29 February. But any unevenness only makes a shared birthday more likely, so 23 is, if anything, a safe estimate.

Exact form and a clean approximation. The exact probability of at least one collision among \(n\) people drawing from \(d = 365\) equally likely days is

\[ P(n) = 1 - \frac{d!}{(d-n)!\,d^{\,n}} = 1 - \prod_{k=1}^{n-1}\left(1 - \frac{k}{d}\right). \]

Using \(1 - x \approx e^{-x}\) on each factor gives \(P(\text{no match}) \approx e^{-\sum_{k=1}^{n-1} k/d} = e^{-n(n-1)/(2d)}\). Setting that equal to one half and solving for \(n\) gives \(n \approx \tfrac{1}{2} + \sqrt{\tfrac14 + 2d\ln 2} \approx 1.177\sqrt{d}\). For \(d = 365\) that is about 22.5, which rounds up to 23.

The square-root law. The headline lesson is the scaling. To get an even chance of a collision among \(d\) possibilities you need only about \(1.177\sqrt{d}\) draws, and a collision becomes likely once the number of draws is on the order of \(\sqrt{d}\), not \(d\). It is the \(\sqrt{d}\), not \(d\), that ambushes the intuition. The expected number of draws until the first collision is a shade larger, about \(\sqrt{\pi d/2}\).

The birthday attack. The same arithmetic sets a hard limit in cryptography. A hash function with a \(b\)-bit output has \(2^b\) possible values, so by the birthday bound you expect two inputs to collide after only about \(2^{b/2}\) random tries, not \(2^b\). A 128-bit hash therefore offers roughly 64 bits of collision resistance, which is why MD5 and SHA-1 fell to engineered collisions and why a hash meant to resist them needs about double the output length. Searching for any two colliding messages this way is literally called a birthday attack, and Grover-style quantum search lowers the bound further, part of why quantum computing unsettles cryptography.

When the days are not equal. If the days are not uniformly likely, the collision probability only rises: the uniform distribution provably minimises the chance of a match for a fixed \(n\), a consequence of the convexity of the relevant sum. Two cousins are worth knowing. The "almost-birthday" problem, asking for two birthdays within a day or two of each other, needs far fewer people, around 14 for an even chance within one day. And the reverse question, the coupon collector problem, asks how many people before every one of the 365 days is someone's birthday, which needs about \(365\ln 365 \approx 2287\). Finding one coincidence is cheap; covering every slot is expensive.