Batch Coupon Collector Expected Coverage Time

Expectation · Hard · Free problem
There are $N = 100$ distinct participants. Each round, $k = 6$ participants are selected uniformly at random without replacement within the round (so each round picks a size-$k$ subset), with rounds being independent of each other. Let $T$ be the number of rounds until every participant has been selected at least once. 1. Derive an exact expression for $E[T]$. 2. Give a tight approximation to $E[T]$ in terms of harmonic numbers. 3. Quantify the relative error of the approximation for $N = 100$, $k = 6$.

Open the full interactive solver, hints, and worked solution →