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$?)

  • 3
    $\begingroup$ This is a version of the coupon collector's problem, so you'd probably find the answer in the related literature. $\endgroup$ – Nate Eldredge Jul 4 '18 at 18:27
  • $\begingroup$ See forinstance sites.google.com/site/rbeeman976/home/collector $\endgroup$ – Nate Eldredge Jul 4 '18 at 18:31
  • $\begingroup$ 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. $\endgroup$ – kodlu Jul 4 '18 at 22:42

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.