the birthday problem

The birthday problem asks a deceptively simple question: in a room of just 23 people, what is the chance that at least two of them share a birthday? Most people guess something tiny, because their own birthday is matched by a stranger only about 1 in 365 of the time. The surprising answer is that with 23 people the probability of some shared birthday is already better than half, about 50.7 percent. It is called a paradox not because it breaks any rule, but because it crashes head-on into a confident wrong intuition.

The trick is to count what you are really asking. You are not asking whether someone matches you; you are asking whether any pair among the group matches, and the number of pairs grows fast — 23 people make 23 × 22 / 2 = 253 distinct pairs, each a fresh chance for a collision. The clean way to compute it uses the complement rule: find the probability that all birthdays are different and subtract from 1. With everyone distinct so far, the second person must avoid 1 birthday (364/365), the third must avoid 2 (363/365), and so on. Multiply these out for 23 people and you get P(all different) ≈ 0.493, so P(a shared birthday) = 1 - 0.493 ≈ 0.507.

The birthday problem is a teaching parable for the whole subject: it shows why raw intuition needs the discipline of the axioms and careful counting. The lesson generalizes far beyond birthdays — it explains why hash-table collisions and cryptographic 'birthday attacks' happen much sooner than newcomers expect. Whenever many items are each compared against many others, the number of comparisons, not the number of items, drives the surprise, and only a careful complement calculation tames it.