= Collision probability of two independent categorical draws
{title2=$\mathbb P(X=Y)=\sum_i p_i^2$}
Suppose two <independent random variables> have the same <categorical distribution>, with label <probability>[probabilities] $p_1,\ldots,p_m$. The disjoint equal-label <events> give
$$
\mathbb P(X=Y)=\sum_{i=1}^m p_i^2.
$$
For the original chosen <probability>[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\leq m\sum_i p_i^2$, so uniform <probability>[probabilities] minimize this two-draw collision <probability>. This pair formula alone does not supply the entire group collision <probability> for a nonuniform model.
Back to article page
