Section 11.1

The Coupon Collector

Geometric stages summed: collecting all n types, k of n types, several draws per round, visiting every vertex of a complete graph.

Toolkit

Break a waiting time into stages, each lasting until the next “new” event occurs; if stage $i$ succeeds on each trial with probability $p_i$ independently, its duration is $\mathrm{Geom}(p_i)$ with mean $1/p_i$ , and total expected time is $\sum_i 1/p_i$ by linearity of expectation — no need for the joint distribution.

Key facts:

\mathbb{E}[\text{time to collect all }n\text{ coupons}] = n\sum_{i=1}^n \frac{1}{i} = nH_n,

\mathbb{E}[\text{time to collect }k\text{ of }n] = n\sum_{i=n-k+1}^{n} \frac1i.

When several draws occur per round, or successes aren’t simply “one new type per trial,” set up the state as the number of types collected so far and let $e_j$ denote expected remaining rounds from state $j$ ; transition probabilities give a backward recursion

e_j = 1 + \sum_k P(j\to k)\,e_k,

solved from the terminal state backwards. When target events have unequal probabilities (e.g. distinct required factors), treat each as its own coupon with its own hitting probability and sum.

Problems