The Birthday Problem

Ask most people how many strangers in a room you'd need before it's more likely than not that two share a birthday, and they guess somewhere near 183 (half of 365). The real number is 23, and the reason for the gap is where an interviewer wants to see you look.

Why the direct approach is the wrong direction

Computing "probability at least one pair matches" directly means summing over every possible way a match could occur — one pair matching, or two pairs, or three, all while everyone else differs — which gets complicated fast. The complement, "no two people share a birthday," is a single clean multiplication, so solve for that and subtract from 1.

Working the complement

Assume 365 equally likely birthdays, no leap years, and $n$ people. Line the people up one at a time.

• Person 1 can have any birthday: probability $365/365$.
• Person 2 must avoid person 1's birthday: probability $364/365$.
• Person 3 must avoid both already-taken birthdays: probability $363/365$.
• ...continuing, person $n$ must avoid the $n-1$ birthdays already taken: probability $(366-n)/365$.

Multiplying these (they're not independent events, but each conditional probability is exactly this, so the product is exact):

$P(\text{no match}) = \frac{365}{365}\cdot\frac{364}{365}\cdot\frac{363}{365}\cdots\frac{366-n}{365}$

So $P(\text{match}) = 1 - P(\text{no match})$.

Worked example: n = 23

Multiply out the 23 fractions above. Numerically, $P(\text{no match}) \approx 0.4927$, so $P(\text{match}) \approx 1 - 0.4927 = 0.5073$ — just over 50%, with only 23 people. At $n=50$ the match probability is already about 97%, and at $n=70$ it's over 99.9%.

Why it's so much smaller than 183. The number of pairs among $n$ people is $\binom{n}{2} = n(n-1)/2$, which grows quadratically. At $n=23$, that's $\binom{23}{2} = 253$ distinct pairs, each an independent-ish chance to collide — you don't need $n$ close to 365, you need the pair count to be comparable to 365, and 253 pairs among 365 days is already enough chances for a collision to be likely.

The complement-and-pair-counting habit reappears in hash collision analysis: a hash table with $m$ slots starts seeing collisions with decent probability once roughly $\sqrt{m}$ items are inserted, for exactly the same quadratic-pair-count reason as the birthday problem.