The Birthday Paradox

How many people do you need in a room before it’s more likely than not that two of them share a birthday? Most people guess somewhere close to 183, half of 365. The actual answer is 23, and the gap between intuition and reality is what makes this such a good example of how badly humans reason about combinatorics.

Counting collisions instead of matches

It’s much easier to compute the probability that no two people share a birthday than to compute the probability that some pair does. With $n$ people and 365 equally likely birthdays,¹ the probability of no collision is

and so the probability we actually care about is its complement:

Each new person added to the room doesn’t just add one new chance of a collision, they add one new chance against every person already there. That’s what gives the curve its characteristically explosive early growth: with 23 people there are $\binom{23}{2} = 253$ pairs to check, not 23.

Checking it by simulation

When a formula feels too clean to trust, simulate it:

import random

def has_collision(n, days=365, trials=20000):
    hits = 0
    for _ in range(trials):
        birthdays = [random.randrange(days) for _ in range(n)]
        if len(set(birthdays)) < n:
            hits += 1
    return hits / trials

for n in (10, 23, 40, 57):
    print(f"n={n:>2}  P(match) ~= {has_collision(n):.3f}")

n=10  P(match) ~= 0.117
n=23  P(match) ~= 0.507
n=40  P(match) ~= 0.891
n=57  P(match) ~= 0.990

23 people is the smallest room where the odds tip in favor of a match; by 57 it’s essentially guaranteed. The same $1 - \prod(\ldots)$ shape shows up anywhere you’re checking pairs instead of individuals — hash collisions, birthday attacks on cryptographic digests,² deduplication in a database — which is the real reason this puzzle keeps coming back up.

An aside on formal proof

Unrelated to the birthday paradox itself, but since we’re already reaching for rigor: here’s what an induction proof looks like in Lean 4, just to see a proof-assistant language rendered instead of a general-purpose one:

theorem add_comm_example (a b : Nat) : a + b = b + a := by
  induction b with
  | zero => simp
  | succ n ih => simp [Nat.add_succ, ih]