Expected Sum of Rolls in the Coupon Collector Problem
You roll a fair six-sided die over and over until every face (1 through 6) has appeared at least once.
Let $S$ be the total of all your rolls — not just how many times you rolled, but the actual sum of all the numbers you see.
What is $E[S]$?
Hints
- Think about whether the expected sum can be decomposed using the expected number of rolls and the expected value per roll.
- Wald's identity says $E[\sum_{i=1}^{N} X_i] = E[N] \cdot E[X]$ for i.i.d. $X_i$ and a stopping time $N$ with finite expectation.
- Compute $E[N]$ using the coupon collector formula $E[N] = 6 \cdot H_6 = 14.7$, then multiply by $E[X] = 3.5$.
Worked Solution
How to Think About It: This is the coupon collector problem with a twist -- instead of just counting the number of rolls, you want the total sum of the die values. The first instinct is to think this is complicated because the stopping time $N$ depends on which values you rolled, not just how many. But here is the key: Wald's identity tells you $E[S] = E[N] \cdot E[X]$, where $X$ is a single roll. The identity works because the $X_i$ are i.i.d. and $N$ is a stopping time with finite expectation. The fact that $N$ depends on the values of the rolls is fine -- Wald's identity does not require $N$ to be independent of the $X_i$, only that the $X_i$ are i.i.d. with finite mean and $E[N] < \infty$.
Quick Estimate: The expected number of rolls in the coupon collector problem with 6 items is:
$$E[N] = 6 \cdot H_6 = 6\left(1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6}\right) = 6 \times \frac{49}{20} = \frac{147}{10} = 14.7$$
The expected value of a single die roll is $E[X] = 3.5$. So the quick estimate is $14.7 \times 3.5 = 51.45$.
Approach: Apply Wald's identity directly.
Formal Solution:
Let $X_1, X_2, \ldots$ be i.i.d. rolls of a fair die, each uniform on $\{1, 2, 3, 4, 5, 6\}$. Let $N$ be the stopping time -- the number of rolls until all 6 faces have appeared. Let $S = \sum_{i=1}^{N} X_i$.
Wald's Identity states: if $X_i$ are i.i.d. with $E[|X_i|] < \infty$ and $N$ is a stopping time with $E[N] < \infty$, then
$$E\left[\sum_{i=1}^{N} X_i\right] = E[N] \cdot E[X_1]$$
Both conditions are satisfied here: - $E[|X_i|] = 3.5 < \infty$ - $E[N] = 14.7 < \infty$ (the coupon collector has a well-known finite expectation)
The coupon collector expected count is computed by decomposing into geometric phases. After seeing $k$ distinct faces, the probability of a new face on the next roll is $(6 - k)/6$, so the expected rolls in phase $k$ is $6/(6 - k)$:
$$E[N] = \sum_{k=0}^{5} \frac{6}{6-k} = \frac{6}{6} + \frac{6}{5} + \frac{6}{4} + \frac{6}{3} + \frac{6}{2} + \frac{6}{1} = 1 + 1.2 + 1.5 + 2 + 3 + 6 = 14.7$$
Therefore:
$$E[S] = E[N] \cdot E[X_1] = 14.7 \times 3.5 = \frac{147}{10} \times \frac{7}{2} = \frac{1029}{20} = 51.45$$
Answer: $E[S] = 51.45$ (equivalently $\frac{1029}{20}$).
Intuition
Wald's identity is one of those results that feels too good to be true the first time you see it. The stopping time $N$ clearly depends on which values you rolled -- if you keep rolling 1s, $N$ is large. So it seems like the sum should depend on the correlation between $N$ and the roll values. But the identity works because of a cancellation: conditional on being in phase $k$ (having seen $k$ distinct faces), every roll still has the same marginal distribution -- it is uniform on $\{1, \ldots, 6\}$ regardless of which faces you have already collected. The stopping rule depends on the identity of the faces, not their numeric values, so there is no systematic bias toward high or low rolls in longer sequences.
In quant work, Wald's identity shows up whenever you have a random sum with a random number of terms -- total P&L from a random number of trades, aggregate loss from a random number of insurance claims, etc. The key check is always: are the individual terms i.i.d. with finite mean, and does the stopping time have finite expectation?