Number of draws to see every object at least once

Question

I woke up this morning with the following question on my mind:

What is (the distribution of) the number of draws you need to sample (with replacement) from an urn with $n$ distinct objects until you have seen every object at least once.

Calling this number $N$, it is quite easy to see that $\mathbb{E}[N]$ is of order $n\log n$. Moreover, simulations suggest that $$ \frac{N-n \log n}{n} $$ converges in distribution to some non-trivial, non-normal distribution $\mu$.

So my more precise question is: Has this observation been proven, and, if so, what is the distribution $\mu$?

Thanks.

Answer 1

This problem is known as the Coupon Collector's Problem. For instance, it is known that $E(N) = n \log n + \gamma n + \frac{1}{2} + o(1)$, where $\gamma$ is the Euler-Mascheroni constant $\gamma \approx 0.577$, and $\mathrm{Var}(N) \leq 2n^2$. Hence, the quantity $\frac{N - n \log n}{n}$ you are interested in, satisfies:

\begin{align} E\left(\frac{N - n \log n}{n}\right) &= \gamma + \frac{1}{2n} + o\left(\frac{1}{n}\right), \\ \mathrm{Var}\left(\frac{N - n \log n}{n}\right) &\leq 2. \end{align}

Several other results to bound the tails of the distribution are known; see the Wikipedia-page for more on that.