Return to Revisions

Birthday problem:

The probability density function of the number of distinct values $Z$ for population size $M$ and sample size $N$ is given by $$P(Z = j) = \binom{M}{j} \sum_{k=0}^j (-1)^k \binom{j}{k} \left(\frac{j - k}{M}\right)^N, \quad j \in \{1, 2, \ldots, \min(M,N)\}$$ $$=\frac{M!}{M^N(M-j)!}S_N^{(j)}$$ (Stirling number of the second kind)
If you wish $Z$ to be close to $M$ with large probability you will need $N\gtrsim M\log M$.