The Birthday Paradox

Question

How many people must be in a room before the probability that some two share a birthday exceeds 50%? Justify the number, and explain why it's so much smaller than most people guess. (Ignore Feb 29; assume 365 equally likely birthdays.)

Accepted Answer

23 people. The probability all n birthdays differ is P(textall distinct) = prod_k=0^n-1 frac365-k365 = prod_k=1^n-1left(1 - frack365right). At n = 23 this product is approx 0.4927, so P(textshared) approx 0.5073 > frac12; at n=22 it is only 0.476. Why intuition fails People instinctively compare n to 365. But collisions are driven by pairs: 23 people contain binom232 = 253 pairs, each matching with probability frac1365. Using 1-x approx e^-x: P(textall distinct) approx expleft(-fracbinomn2365right), which crosses frac12 when binomn2 approx 365 ln 2 approx 253, i.e. n approx 23. The general scaling, collisions appearing around n sim sqrtN, matters in practice (hash collisions, birthday attacks in cryptography, coincidences in datasets).

The Birthday Paradox

Problem

Your answer

Hints

More Probability to train on