Birthday problem

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.