# What is this distribution?

Let $M$ be a positive integer, and let $X_1, X_2, \dots$ be i.i.d. r.v.'s having uniform distribution in the set $\{1, \dots, M\}$. For given $N$, let $Z_N$ denote the number of distinct elements of the set $\{X_1, \dots, X_N\}$.

Question: What is the distribution of $Z_N$?

(In the end, I want to estimate how large $N$ has to be such that $Z_N$ is close to $M$ with high probability. For example, how large does $N$ have to be such that $Z_N > 0.9 M$ with probability at least $1/2$?)

• This is a version of the coupon collector's problem, so you'd probably find the answer in the related literature. – Nate Eldredge Jul 4 '18 at 18:27
• See forinstance sites.google.com/site/rbeeman976/home/collector – Nate Eldredge Jul 4 '18 at 18:31
• Given you have $k$ coupons the waiting time $W_k$ for the next coupon is has Geometric distribution with success probability $(M-k)/M$ and expectation $M/(M-k)$. Summing for $k=0,\ldots,M-1$ gives expected wait for all coupons as $M H_M=M(\ln M+\gamma).$ with the Euler-Mascheroni constant making an appearence. Due to independence of the $W_k$ the variance is also easy to obtain. – kodlu Jul 4 '18 at 22:42

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)\}$$ $\qquad\qquad\qquad\qquad=\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$.