Coupon Collector Problem

The coupon collector problem: Given $n$ equally likely coupon types, how many draws (with replacement) until you have at least one of each? $$E[T] = n \cdot H_n = n\left(1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}\right) \approx n \ln n$$ Derivation via linearity of expectation: After collecting $k$ distinct types, the probability of getting a new type on the next draw is $\frac{n-k}{n}$. The expected number of draws to get the next new type is $\frac{n}{n-k}$ (geometric distribution). Summing: $$E[T] = \sum_{k=0}^{n-1} \frac{n}{n-k} = n \sum_{j=1}^{n} \frac{1}{j} = n H_n$$ When to use: "How long until all states are visited?" / "Expected time to complete a collection." Also appears in hashing (expected time until first collision ≈ $\sqrt{\pi n / 2}$ by birthday paradox — different problem but related flavor).