The Birthday Paradox

What just happened?

In a group of 10 people the probability that at least two of them share a birthday is 11.7%. Most people’s intuition suggests you need half of 365 days — about 183 people — to exceed 50%. That is wrong: just 23 people are enough.

The complementary event — the key to the calculation:

It is easier to compute the probability that everyone has a different birthday, and subtract it from 1:

which is equivalent to a product of decreasing fractions:

Why does it work? (the invariant)

P(n) grows monotonically with n and approaches 100%. The secret does not lie in single people against one fixed date — what counts is every possible pair of people. With n people there are $n(n-1)/2$ pairs: with n=23 that is already 253 pairs, each with a small 1/365 chance of a date match, but together giving more than 50%. With n=70 the probability already exceeds 99.9%.

History of the paradox

The problem was first published by Richard von Mises in 1939 — it was probably known informally even earlier, e.g. to Harold Davenport around 1927, but it was von Mises who first presented it in print. Today it is a classic example of how intuition fails in probability — also used to illustrate “collisions” in computer science, e.g. in hash functions.

Why you need this for the exam:

The complementary event is one of the most useful tricks in combinatorics and probability — when “at least one/two” is hard to count directly, count “none” and subtract from 1. The trick: always check whether you are counting single elements or pairs/combinations — these most often “drive” surprisingly high results.

Remember: just 23 people are enough for the chance of a shared birthday to exceed 50% — because what counts is the number of pairs, not the number of people. P = 1 − 365!/(365ⁿ·(365−n)!).