Birthday problem
= Birthday problem
{wiki}
For $n$ independent uniform draws from $m$ labels, the probability of all labels being distinct is $\prod_{j=0}^{n-1}(1-j/m)$ when $n\leq m$, and zero otherwise. Applying $1-x\leq e^{-x}$ gives a collision probability at least $1-\exp[-n(n-1)/(2m)]$. The transition therefore occurs at sample size of order $\sqrt m$, not $m$: many pairs can collide before many labels have been sampled.