Tag Info

In probability, the coupon collector's problem models "collect all the coupons and win" contests. In its simplest form, suppose n distinct types of coupon are equally likely to occur: what is the expected number of coupons we must draw to collect at least one of each type?

In probability, the coupon collector's problem models "collect all the coupons and win" contests. In its simplest form, suppose n distinct types of coupon are equally likely to occur: what is the expected number of coupons we must draw to collect at least one of each type?

The Wikipedia article shows that the expected value of the time to collect all $n$ types of coupon, $T$, grows rapidly as a function of $n$. In particular,

$$\mathbb{E}(T) = n \sum_{k=1}^n \frac{1}{k} = n H_n$$

where $H_n$ is the $n^\mathrm{th}$ harmonic number. Asymptotically, $\mathbb{E}(T)$ is approximately $n \log n$.

There are more sophisticated versions of the problem, for instance the version described on Wolfram MathWorld in which $n$ objects are repeatedly sampled, but where the probability $p_i$ of picking the $i^\mathrm{th}$ object can differ between objects, subject to the constraint $\sum_{i=1}^n p_i = 1$.