= Birthday collision count
{title2=$C=\sum_{i<j}\mathbf1_{\{X_i=X_j\}},\quad\mathbb E[C]=\binom n2/m$}
The <birthday collision count> counts equal-label <unordered pairs>. Write it as a <sum> of <indicator random variables>:
$$
C=\sum_{1\leq i<j\leq n}\mathbf1_{\{X_i=X_j\}},\qquad\mathbb E[C]=\sum_{i<j}\frac1m=\frac{n(n-1)}{2m}.
$$
This uses <linearity of expectation>; mutual <independence> of the pair indicators is unnecessary. For 23 uniform calendar labels, $\mathbb E[C]=253/365\approx0.69315$, whereas $\mathbb P(C\geq1)\approx0.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.
Back to article page
