The Birthday Paradox: Why Collisions Happen Far Sooner Than Intuition Suggests

The setup, and why it feels wrong

The classic version of the problem asks: in a room of 23 randomly chosen people, what is the probability that at least two of them share a birthday (ignoring leap years, and treating all 365 days as equally likely)? Most people's gut estimate lands somewhere between 5% and 15% — 23 out of 365 feels small. The actual answer is just over 50%. With 70 people in the room, the probability climbs above 99.9%. The gap between intuition and the correct answer is large enough that this is genuinely called a "paradox," even though there's nothing logically contradictory about it — it's a paradox of intuition, not of mathematics.

Why intuition undercounts: it's about pairs, not people

The instinctive mistake is to think about the problem from a single person's point of view — "what's the chance someone shares my birthday" — which really is small (about 6% in a room of 23, since there are only 22 other people to compare against). But the actual question is about any pair among the whole group sharing a birthday, and the number of possible pairs grows much faster than the number of people. With n people, the number of distinct pairs is n(n−1)/2. At n = 23, that's 253 separate pairs, each an independent opportunity for a coincidence. Intuition tracks the linear growth of people; the real answer depends on the quadratic growth of pairs, and that mismatch is the entire source of the surprise.

The actual calculation

It's easier to compute the probability that no one shares a birthday and subtract from 1, rather than trying to directly account for every possible way a coincidence could occur. Add people to the room one at a time: the first person can have any birthday (probability 1). The second person must avoid the first person's birthday: probability 364/365. The third must avoid both previous birthdays: probability 363/365. Continuing this pattern for n people and multiplying all the individual probabilities together gives the probability that every birthday in the room is distinct:

P(all distinct) = (365/365) × (364/365) × (363/365) × ... × ((365−n+1)/365)

The probability of at least one shared birthday is then 1 minus that product. Plugging in n = 23 gives roughly 0.493 for "all distinct," so the complement — at least one match — is about 0.507, just over half. The function crosses 50% at exactly 23 people and rises steeply from there, which is why the jump from "surprising" to "near certain" happens over a relatively narrow range of group sizes rather than a slow climb.

The general pattern: collisions among many more 'slots' than people

The birthday problem is really a special case of a much more general question: if you draw n items at random (with replacement) from a pool of N possible values, how many draws does it take before a repeat becomes likely? For the birthday problem N = 365. A useful rule of thumb, derived from approximating the exact product above, is that the number of draws needed for a 50% chance of a collision is roughly 1.18 × √N — the square root of the pool size, not a fraction of it. For N = 365, √365 ≈ 19.1, and 1.18 × 19.1 ≈ 22.5, which matches the exact answer of 23 closely. This square-root scaling is the part that generalises far beyond birthdays.

Why this matters for hash functions

A cryptographic hash function maps an input of any size to a fixed-length output — say, 256 bits, giving 2²⁵⁶ possible output values. Naively, one might assume that finding two different inputs that produce the same hash output (a "collision") would take on the order of 2²⁵⁶ attempts, since that's how many possible outputs exist. The square-root scaling from the birthday problem says otherwise: because a collision only requires any two of your attempts to match each other — not a specific target — the expected number of attempts needed is closer to the square root of the output space, roughly 2¹²⁸ for a 256-bit hash. This is known as a birthday attack, and it's precisely why cryptographers double the bit-length of a hash function's output relative to the security level they want against collisions: a "128-bit secure against collisions" hash needs a 256-bit output, not a 128-bit one, exactly because of the square-root effect described above.

This is also why hash function design pays close attention to output length whenever collision resistance (rather than just preimage resistance) matters — for digital signatures, certificate authorities, and version-control systems that rely on hashes to uniquely identify content, an attacker exploiting the birthday bound needs dramatically fewer attempts than the raw output size would suggest.