[Math] Coupon Collector Problem with Batched Selections

combinatoricscoupon-collectordiscrete mathematicsprobability

I am trying to solve a variation on the coupon collector's problem.

In this scenario, someone is selecting coupons at random with replacement from n different possible coupons. However, the person is not selecting coupons one at a time, but instead, in batches.

Here's an example problem formulation: There are 100 distinct coupons. A person makes selections in 10-coupon batches at random (each coupon with replacement). What is the expected number of batches necessary to have selected 80 unique coupons?

I have been able to determine the expected number of selections necessary to have selected k unique coupons when selecting one at a time (much like Henry's answer to a similar question), but I'm a bit stumped as to how to go about solving it with this particular wrinkle.

Any tips/guidance would be greatly appreciated.

Best Answer

The probability not to have all $n$ coupons after drawing $k$ coupons is

$$ \def\stir#1#2{\left\{#1\atop#2\right\}} P(K\gt k)=1-\frac{n!}{n^k}\stir kn $$

(see e.g. Probability distribution in the coupon collector's problem). Thus, if we draw in batches of $b$ coupons, the expected number of batches is

\begin{align} \sum_{j=0}^\infty P(K\gt jb) &= \sum_{j=0}^\infty\left(1-\frac{n!}{n^{jb}}\stir{jb}n\right) \\ &= \sum_{j=0}^\infty\left(1-\frac1{n^{jb}}\sum_{l=0}^n(-1)^{n-l}\binom nll^{jb}\right) \\ &= \sum_{j=0}^\infty\sum_{l=0}^{n-1}(-1)^{n-l+1}\binom nl\left(\frac ln\right)^{jb} \\ &= \sum_{l=0}^{n-1}(-1)^{n-l+1}\binom nl\frac1{1-\left(\frac ln\right)^b}\;. \end{align}

For instance, for $n=2$, this is

$$ \frac2{1-2^{-b}}-1=1+\frac2{2^b-1}\;. $$