Coupon Collector Problem
Definition
The coupon collector problem asks: if there are $n$ distinct types of coupons collected uniformly at random (with replacement), how many draws are needed to collect all $n$ types?
Result
The expected number of draws is
$$ \mathbb{E}[T] = n \sum_{k=1}^{n} \frac{1}{k} = n\, H_n \sim n \ln n, $$where $H_n$ is the $n$-th harmonic number.
Application to Coupling
The coupon collector bound provides an upper bound on the coupling time for independent coupling of Markov chains on a finite state space: the two chains must “collect” agreement in every state.