Coupon collector

Coupon Collector's Problem

High-level idea. Decompose the total waiting time into independent geometric stages, then apply linearity of expectation.

Stage decomposition

Let $T$ be the total number of rolls of a fair $N$-sided die needed to observe every face at least once. Define stage $k$ ($k = 1, \ldots, N$) as the period that begins the moment the $(k{-}1)$-th distinct face was first seen and ends when the $k$-th distinct face is first seen. Writing $T_k$ for the number of rolls in stage $k$,

$$T = T_1 + T_2 + \cdots + T_N.$$

Distribution of each stage

At the start of stage $k$, exactly $k-1$ faces have been observed. Each roll independently reveals a previously unseen face with probability

$$p_k = \frac{N-(k-1)}{N} = \frac{N-k+1}{N}.$$

Hence $T_k \sim \operatorname{Geometric}(p_k)$ (number of trials until first success), so

$$E[T_k] = \frac{1}{p_k} = \frac{N}{N-k+1}.$$

Closed-form expected value

By linearity of expectation,

$$E[T] = \sum_{k=1}^{N} \frac{N}{N-k+1}.$$

Reindexing with $j = N-k+1$ (as $k$ runs $1 \to N$, $j$ runs $N \to 1$):

$$E[T] = N \sum_{j=1}^{N} \frac{1}{j} = N \cdot H_N,$$

where $H_N = \displaystyle\sum_{j=1}^{N} \frac{1}{j}$ is the $N$-th harmonic number.

Numerical evaluation for $N = 100$

Using the Euler–Maclaurin asymptotic expansion

$$H_N = \ln N + \gamma + \frac{1}{2N} - \frac{1}{12N^2} + \frac{1}{120N^4} - \cdots,$$

with $\gamma = 0.57721566490153\ldots$ (Euler–Mascheroni constant):

$$\begin{aligned} H_{100} &\approx \underbrace{4.60517018598809}_{\ln 100} + \underbrace{0.57721566490153}_{\gamma} + \underbrace{0.00500000000000}_{1/200} - \underbrace{0.00000833333}_{1/120000} \\ &\approx 5.18737752. \end{aligned}$$

Therefore,

$$E[T]\big|_{N=100} = 100 \times H_{100} \approx 518.74.$$

Rounded to the nearest integer:

$$\boxed{519}.$$