xviii. Coupon Collector

Problem. Each box contains one of $n$ equally likely coupons. How many boxes until you have all $n$?

Answer: $E=n{H}_n=n(1+\frac{1}{2}+\cdots +\frac{1}{n})\approx n\ln n+0.577n$. For $n=50$, about $225$ boxes.

double couponExpected(int n) { double e = 0; for (int i = 1; i <= n; i++) e += (double)n / i; return e; }   // n * H_n

Variant	Result
variance	$n^2\sum 1/i^2-n{H}_n<\frac{{\pi }^2}{6}{n}^2$
collect $k$ of the $n$	${\sum }_{i=0}^{k-1}\frac{n}{n-i}$
unequal probabilities $p_i$	${\int }_0^{\infty }\left(1-{\prod }_i(1-e^{-p_{i}t})\right)dt$ (inclusion–exclusion)
tail	$\mathrm{Pr}[T>n\ln n+cn]\le e^{-c}$

Proof: E = n H_n

Split the process into phases: phase $i$ ($0\le i<n$) starts when $i$ distinct coupons are held and ends at the next new one. Each draw in phase $i$ is new with probability $\frac{n-i}{n}$, so its length is geometric with mean $\frac{n}{n-i}$. By linearity of expectation $E={\sum }_{i=0}^{n-1}\frac{n}{n-i}=n{H}_n$. Checked against a Monte Carlo simulation for $n=6$.