Collision Bounds Beyond the Birthday Problem

The problem. The birthday problem's headline result — 23 people are enough for a better-than-even chance two share a birthday — is well known enough that interviewers now push past it. Two natural follow-ups: what if the "days" aren't equally likely (real birthdays cluster around September)? And what does it take to get a triple match, not just a pair?

Recap: why 23 is the surprising answer

With $n$ people and $d=365$ equally likely days, the trick is to compute the complement — the probability of no shared birthday — because that's a clean product: $P(\text{no match}) = \prod_{k=0}^{n-1}\frac{365-k}{365}$. Each new person must avoid all previously claimed days. At $n=23$, this product drops just below $\frac12$, so $P(\text{some match}) = 1 - P(\text{no match})$ just exceeds 50%. The reason 23 feels too small is that people intuit "how many people to match me specifically" (that needs $n \approx 253$), not "how many people for any pair" — the number of pairs among 23 people is $\binom{23}{2}=253$, and it's that count of pairs, each a small chance of matching, that drives the surprising result.

The no-match probability in the birthday problem falls off roughly like $e^{-n(n-1)/2d}$ as $n$ grows — an exponential decay in the square of $n$. Drag the rate on the curve above to get a feel for how sharply an exponential can fall once its exponent starts growing, which is exactly why the crossover to "more likely than not" happens at a surprisingly small $n=23$ rather than something closer to $d=365$.

Extension 1: unequal bucket probabilities make collisions more likely, not less

If birthdays aren't uniform — some days are more popular — the true collision probability is always at least as large as the uniform case, for the same $n$. Intuition: uniform is the "hardest" case to get a match, because spreading days out evenly minimizes the chance of overlap; any clustering (some days more popular than others) only concentrates people onto fewer effective buckets and makes matches more likely. This is a general fact about balls into bins — an uneven distribution over bins never decreases collision probability compared to the uniform distribution over the same number of bins.

Worked example: probability of a triple match

What's the smallest $n$ such that the probability three people share a birthday exceeds 50%? This doesn't have the same clean complement trick, since "no triple match" still allows pairs to match. The standard approach approximates via expected number of triples: the number of triples among $n$ people is $\binom{n}{3}$, and each specific triple shares a birthday with probability $\frac{1}{365^2}$ (fix the first person's birthday, the other two must match it). Expected number of triple-matches $\approx \binom{n}{3}/365^2$. Setting this near 1 (a rough threshold for "likely to see at least one") gives $\binom{n}{3} \approx 365^2 = 133{,}225$, so $n(n-1)(n-2) \approx 799{,}350$, which solves to roughly $n \approx 93$. The known precise answer is $n=88$ for exceeding 50% — the rough count-matching approximation lands impressively close, which is itself a useful interview technique when an exact recursive computation isn't practical by hand.

The general technique: complement for pairs, expected-count for anything harder

For "probability of any pair matching," always reach for $1 - P(\text{no match})$, since the no-match event has a clean multiplicative form. For anything beyond a simple pair — triples, unequal bucket sizes, or generalized "$k$-collision" questions — the no-match complement usually stops being a clean product, and the practical fallback is the expected-number-of-matches approximation: compute $E[\text{number of matching groups}]$ via indicators, and use $P(\text{at least one}) \approx 1 - e^{-E}$ (or simply check where $E \approx 1$ crosses over) as a workable estimate under interview time pressure.