= Birthday problem
{title2=$P_{n,m}=1-\prod_{j=0}^{n-1}(1-j/m)$}
{wiki}
= Birthday paradox
{synonym}
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\geq1$ and $n\geq0$ be <integers>. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\leq n\leq m$, the probability of at least one matching pair is
$$
\boxed{P_{n,m}=1-\frac{m(m-1)\cdots(m-n+1)}{m^n}=1-\prod_{j=0}^{n-1}\left(1-\frac jm\right).}
$$
At $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.<Introduction to Probability by Charles M. Grinstead and J. Laurie Snell>[§3.1, Example 3.3 and Table 3.1, printed pp. 77–78: uniform-calendar assumptions, distinct-label product and threshold]{ref}
For the stipulated calendar, \b[$P_{22,365}\approx47.57\%$ and $P_{23,365}\approx50.73\%$]. Only 23 people suffice to put the probability above one half. There are $\binom{23}{2}=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.
\Image[/birthday-any-pair-versus-specified-person.png]
{title=Any matching pair becomes likely much sooner than a match with one specified person}
{description=Original exact computations under the independent uniform 365-label model. The solid curve allows every pair in a group of total size $n$; the lower curve requires a match with one designated member. The dashed curve is the exponential lower bound for any-pair collision probability. This is a model calculation, not observed birthday data.}
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.
Back to article page
