1
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 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
    Commented Jul 4, 2018 at 18:27
  • $\begingroup$ See forinstance sites.google.com/site/rbeeman976/home/collector $\endgroup$
    – Nate Eldredge
    Commented Jul 4, 2018 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
    Commented Jul 4, 2018 at 22:42

1 Answer 1

Reset to default
3
$\begingroup$

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$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .