In a room with 23 people, the probability that at least two share a birthday exceeds 50%. With 50 people it reaches about 97%. Almost everyone, hearing this for the first time, thinks it is a mistake: with 365 days available, 23 people seem very few. It is not a true paradox, but an example of how we underestimate the number of pairs that can be formed in a group. And it has very concrete consequences in computing.
The exact calculation
Assume 365 equally likely days and ignore leap years. Computing «at least two people share a birthday» directly is awkward, because there are many cases. It is better to use the complement: the probability that all birthdays are different.
- The first person can have any birthday: 365/365.
- The second must avoid the first one's: 364/365.
- The third must avoid the two already taken: 363/365.
- And so on, up to the n-th: (365 − n + 1)/365.
Multiplying:
P(all different) = (365 · 364 · … · (365 − n + 1)) / 365ⁿ
and the probability we want is 1 minus this value.
| People | P(at least one shared birthday) |
|---|---|
| 10 | about 12% |
| 23 | about 51% |
| 30 | about 71% |
| 40 | about 89% |
| 57 | about 99% |
Why the number is so low
Intuition fails because we think about the wrong question. We ask: «does anyone share my birthday?». That probability, with 22 other people, really is low: 1 − (364/365)²² ≈ 6%. But the question concerns any pair in the group. With 23 people the possible pairs are 23 · 22 / 2 = 253. Each pair has a small chance of matching, but 253 small chances added together become many.
The number of pairs grows with the square of the number of people, while the number of days stays fixed. It is this quadratic growth that makes collisions surprisingly quick.
An approximate formula
For large values there is a very handy approximation. If n objects are assigned at random among N possible values, the probability of at least one collision is roughly:
P ≈ 1 − e^(−n² / 2N)
From this we get a practical rule: the collision probability reaches 50% when n is about 1.18 · √N. For N = 365 this gives about 22.5, consistent with the exact result. More generally, collisions become likely when the number of items approaches the square root of the available space.
The consequences in computing
Hash functions
A hash function with a b-bit output has 2ᵇ possible values. One might think that about 2ᵇ attempts are needed to find two inputs with the same hash. The birthday paradox says instead that about 2^(b/2) are enough. A 64-bit hash therefore offers collision resistance on the order of 2³², about four billion attempts: a number within reach of an ordinary computer. This is why, when collision resistance is needed, hashes with outputs of at least 256 bits are used: effective security against collisions is about half the bits.
Random identifiers
The same reasoning applies to randomly generated IDs: booking codes, tokens, temporary file names, random primary keys. Suppose we generate random 6-digit codes, a million possible values. With about 1,180 codes issued, there is already a 50% probability that two coincide. If the system does not check for duplicates, a collision is not a remote event but almost a certainty after a few thousand issues.
Version 4 UUIDs contain 122 random bits. The square root of the space is on the order of 2⁶¹, an enormous number: this is why, under normal conditions, collisions are negligible, provided the random number generator is of good quality.
Hash tables
In data structures, too, collisions arrive early. Inserting items into a table with m slots, the first collision is expected after about √m insertions, well before the table is full. This is why hash tables are designed to handle collisions as the normal case, not as an exception.
The assumptions matter
The calculation assumes uniformly distributed birthdays. In reality births are not perfectly uniform across the year, and a non-uniform distribution increases the probability of matches: if some values are more frequent, it is easier for two items to land on the same one. The same goes for faulty random generators: a generator that produces some values more often than others causes collisions sooner than theory predicts.
In short
- With 23 people the probability of a shared birthday exceeds 50%.
- The key point is the number of pairs, which grows with the square of the group size.
- Collisions become likely around the square root of the value space.
- This is why a b-bit hash resists collisions only up to about 2^(b/2) attempts.
- Non-uniform distributions make collisions even more likely.
