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.