The Birthday Paradox: Why 23 People Is All You Need

If I ask you how many people you need in a room for there to be a better-than-even chance that two of them share a birthday, most guesses land around 180 — roughly half of 365. The actual answer is 23. In a room of 23 randomly chosen people, the probability that at least two share a birthday is about 50.7%. With 30 people it’s 70%. With 50 people it’s 97%. With 70 people, you’re past 99.9%.

This feels wrong. If there are 365 possible birthdays and you only have 23 people, how can the collision be likely? The mismatch between intuition and arithmetic is what gives this result its traditional name: the birthday paradox. It’s not a paradox in the logical sense — the math is elementary. It’s a paradox in the sense that human beings are poorly equipped to reason about combinations, and small examples expose that blind spot sharply.

What the intuition gets wrong

The usual mistaken reasoning goes: “There are 365 days. I have 23 people. 23 out of 365 is about 6%. So the odds should be around 6%.”

That calculation is answering a different question. It’s approximately the probability that a specific person in the room shares a birthday with one of the others. That’s not what was asked. The question is whether any two of the 23 people share a birthday, and the number of pairs you need to check is far larger than 23.

With 23 people, the number of distinct pairs is

$\binom{23}{2} = \frac{23 \cdot 22}{2} = 253.$

Each pair is an independent opportunity for a match. You’re not checking 23 coincidences — you’re checking 253. Suddenly the answer stops looking implausible.

The calculation

The cleanest way to compute the probability is to use complementation: first calculate the probability that nobody shares a birthday, then subtract from 1.

Line up the 23 people one by one. The first person has any birthday — probability 1, essentially. The second person has a different birthday from the first with probability $364/365$. The third has a different birthday from both with probability $363/365$. In general, the $n$-th person has a unique birthday (given no previous collisions) with probability $(365 - n + 1)/365$.

So the probability that all 23 have different birthdays is

$P(\text{all different}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{343}{365} = \prod_{k=0}^{22} \frac{365 - k}{365}.$

Working through the product: $P(\text{all different}) \approx 0.4927$. Therefore

$P(\text{at least one match}) = 1 - 0.4927 \approx 0.5073.$

Just over 50%. The magic number is 23.

A general formula

For $n$ people and $d$ equally likely possibilities (days in a year, but also hash values, or anything discrete), the probability of no collision is

$P_0(n, d) = \prod_{k=0}^{n-1} \frac{d - k}{d}.$

This product is awkward to evaluate by hand but admits a useful approximation. Taking logarithms:

$\ln P_0(n, d) = \sum_{k=0}^{n-1} \ln\left(1 - \frac{k}{d}\right) \approx -\sum_{k=0}^{n-1} \frac{k}{d} = -\frac{n(n-1)}{2d}.$

The approximation uses $\ln(1 - x) \approx -x$ for small $x$, which is reasonable when $n$ is much smaller than $d$. Exponentiating:

$P_0(n, d) \approx e^{-n(n-1)/(2d)}.$

So the probability of at least one collision is approximately

$P(\text{collision}) \approx 1 - e^{-n(n-1)/(2d)}.$

For this to cross 50%, you need $n(n-1)/(2d) \approx \ln 2 \approx 0.693$, which gives $n \approx \sqrt{2d \ln 2}$. With $d = 365$ this yields $n \approx 22.5$. Consistent with the 23 we found directly.

The broader punchline: the number of samples needed to produce a collision scales with the square root of the number of possibilities, not with the number itself. That square root is the source of most of the counterintuitive behaviour.

Where this actually matters

The birthday paradox is not just an entertaining party trick. It has serious consequences in cryptography.

A cryptographic hash function maps arbitrary input to a fixed-length output — say, a 256-bit string. Two different inputs that produce the same output form a collision. For a hash to be secure, collisions should be practically impossible to find. You might think that for a hash with $2^{256}$ possible outputs, you’d need to try $2^{256}$ random inputs to find a collision.

You’d be wrong. By the birthday bound, you need only about $\sqrt{2^{256}} = 2^{128}$ inputs to have a good chance of a collision. That’s still astronomically large, but it’s the square root of what naive counting suggests. This is why cryptographic hashes use outputs twice as long as the target security level: a hash promising 128-bit security needs a 256-bit output, because collision attacks are the binding constraint.

The same counting underlies the security of digital signatures, password storage, and blockchain identifiers. Every system that relies on hash collisions being rare has to worry about the square-root effect. This is not a corner case. It’s the reason most modern cryptographic algorithms are sized the way they are.

Variations and extensions

The basic birthday problem has several natural generalisations.

Almost-birthday problem. Instead of exact matches, what’s the probability that two people have birthdays within $k$ days of each other? For $k = 1$ (birthdays within a day), 50% is reached with only 14 people. The counting scales even more aggressively.

Collisions among specific groups. If you have $n$ men and $n$ women, what’s the probability some man shares a birthday with some woman? This is a different calculation (no self-pairing), and the answer scales differently. 50% is reached when $n \approx 19$, so a group of about 38.

Strong birthday problem. What’s the probability that every person in a group shares a birthday with at least one other? This scales much more slowly. For 50% probability, you need over 3000 people.

Coupon collector’s problem. The reverse question — how many draws from 365 days until you’ve seen every birthday at least once? Expected value is $365 \cdot H_{365} \approx 2365$, where $H_n$ is the $n$-th harmonic number. Much slower scaling.

The broader moral

The birthday paradox is the canonical entry point to a recurring lesson in probability: human intuition for compound events is terrible.

We are comfortable reasoning about single events. The chance of rain tomorrow. The chance of a single coin flip. We are much worse at reasoning about the number of events happening in a collection. This shows up everywhere. A medical test with 99% accuracy, applied to a population where 1% have the condition, has far more false positives than true positives — a fact that continues to surprise doctors learning Bayes’ theorem. A weather forecast that is 70% accurate day by day is wrong at least once over a week with probability $1 - 0.7^7 \approx 92\%$.

These are the same kind of error as the birthday paradox. Small per-event probabilities compound faster than intuition suggests, and the compounding is dominated by combinatorial counting rather than by the individual event probabilities.

The habit worth cultivating: when reasoning about collections, count pairs. Count comparisons. Count the opportunities for the unlikely event to happen. The answer is almost always more than your gut suggests.

And if you’re ever at a party with 23 people, you now have a better-than-even chance of finding two birthdays to celebrate.

Frequently asked

Why is it called a paradox if the math is clear?

Because the result conflicts sharply with human intuition. 'Paradox' here means 'counterintuitive,' not 'logically impossible.' The mathematics is straightforward — it's the mismatch with what people expect that earns it the label.

Does the birthday paradox have real-world applications?

Yes, prominently in cryptography. Birthday attacks exploit exactly this counting effect to break hash functions much faster than brute force suggests. A hash with a 128-bit output needs only about 2^64 queries to find a collision — the square root of what naive counting would suggest.

Continue reading

Formula

The Gaussian Distribution

The bell curve — the probability distribution that appears whenever many independent random effects add up. The cornerstone of statistics.

Read →Blog

The Monty Hall Problem and Why Probability Tricks Your Brain

A game-show puzzle from the 1990s that fooled thousands of mathematicians — and what it reveals about how badly our intuition handles conditional probability.

Read →Blog

The St. Petersburg Paradox: When Infinity Meets Common Sense

Flip a coin until tails. If it takes n flips, you win 2ⁿ dollars. Expected payoff: infinite. So why won't anyone pay more than $20 to play? A 300-year-old puzzle about rational decision-making.

Read →