Birthday problem

How many people do you need in a room before two of them probably share a birthday? Most people guess something like 180 — half of 365. The real answer is 23.

With 23 people, probability of a shared birthday: theoretical 50.7% empirical 50.7% (2000 trials)

group size 23 trials (empirical) 2000

Black curve: exact probability from 1 − ∏(1 − k/365). Blue dot: empirical rate from 2000 random groups of 23. Dashed lines mark the 50% crossover at n = 23.

P (collision) = 1 - k = 0 \prod n - 1 \frac{365 - k}{365}

Why so few

The trick is counting pairs, not people. With n people there are $n (n - 1) /2$ pairs. At n = 23 that’s 253 pairs — 253 chances for a match. Each individual pair has only a 1/365 chance of a collision, but 253 independent chances add up fast.

The formula above just tracks that directly: for each of the n people, the probability their birthday is new given all previous births is $(365 - k) /365$ . Multiply those together for P(no collision); subtract from 1.

What to notice

The curve is non-linear — it rises slowly then accelerates. 50% arrives earlier than intuition suggests, 99% by just n = 57.
The empirical dot tracks the theoretical curve tightly even at modest trial counts. Birthday collisions are a well-behaved estimator.
This is why hash collisions become likely much sooner than hash-output size implies. A 128-bit hash doesn’t give you 2^128 safety — it gives you roughly 2^64.