Birthday problem ($P_{n,m}=1-{\prod }_{j=0}^{n-1}(1-j/m)$)

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.

In a group of total size $n\ge 1$, designate one member and ask whether any of the other $n-1$ labels equals that member's label. Conditional on the designated label, all the other draws avoid it with probability $1-1/m$. Independence givesFor $n=23$, this is approximately $5.86\%$, while the probability of some matching pair is approximately $50.73\%$. The designated-member question examines $22$ pairs; the any-pair question examines all $253$. A repeated label elsewhere in the group does not require a match with its designated member.

The birthday collision count counts equal-label unordered pairs. Write it as a sum of indicator random variables:This uses linearity of expectation; mutual independence of the pair indicators is unnecessary. For 23 uniform calendar labels, $\mathbb{E}[C]=253/365\approx 0.69315$, whereas $\mathbb{P}(C\ge 1)\approx 0.50730$. A configuration with three equal labels contributes three pairs, so counting pairs and recording whether any pair exists are different random variables.

Treating every pair event as mutually independent would give the wrong exact formula. For three draws, $X_1=X_2$ and $X_1=X_3$ force $X_2=X_3$. The probability that all three equalities hold is $1/m^2$, while the product of their individual probabilities is $1/m^3$ for $m>1$. This distinguishes independence of the original label draws from mutual independence of events built from overlapping draws.

The union bound gives $P_{n,m}\le \min (1,n(n-1)/(2m))$. Using $1-x\le e^{-x}$ on the distinct-label product givesThe lower bound reaches at least one half when $n(n-1)/(2m)\ge \log 2$. The simple approximation $n\approx \sqrt{2m\log 2}$ predicts a group size near 23 for $m=365$. It is the quadratic number of pairs that makes the square root appear.

For a precise limiting statement, let $m\to \infty$ and $n/\sqrt{m}\to c\ge 0$. Expanding the logarithm of the complement yieldsOn this scale the remainder tends to zero. Thus a fixed substantial collision probability appears after order $\sqrt{m}$ draws. For $m=2^b$ uniform output labels, the corresponding scale is order $2^{b/2}$; matching one specified birthday instead involves a number of draws of order $m$.

Suppose two independent random variables have the same categorical distribution, with label probabilities $p_1,\dots ,p_m$. The disjoint equal-label events giveFor the original chosen probabilities $(1/2,1/4,1/8,1/8)$, this is $11/32=0.34375$, rather than the uniform four-label value $1/4$. The Cauchy-Schwarz inequality gives $1=({\sum }_i{p}_i{)}^2\le m{\sum }_i{p}_i^2$, so uniform probabilities minimize this two-draw collision probability. This pair formula alone does not supply the entire group collision probability for a nonuniform model.