Batched Coupon Collector Problem

Question

The batched coupon collector problem is a generalization of the coupon collector problem. In this problem, there is a total of $n$ different coupons. The coupon collector gets a random batch of $b$ different coupons each time. What is the average number of batches required to collect all of the $n$ coupons? If $b=1$, this is the classic coupon collector problem.

There is an interesting answer (by Did) to a similar problem posed in this link . But this answer does not work for the case of $k=n$ (where $k$ is the number of different coupons collected). It is mentioned there that it is unclear on how to find $E_{b,n}(T_k)$. How about $E_{b,n}[T_n]$?

Answer 1

Note. At the time of writing, the accepted answer to this question was that of Douglas Zare.

The accepted answer to this question is incorrect, albeit for what appears to be a relatively minor reason. I discovered this while answering a special case of the same question over at math.SE, where it was observed that in the special case $b=3$ and $n=10$, the formula from this post gave an absurdly large value.

After consulting the literature myself, I found the correct formula in Theorem 2 of Stadje [1990] (specifically equation (2.15) therein) with $p=1$ and $l=s=n$ and $m=b$. The desired expectation equals $$ \binom{n}{b}\sum_{j=0}^{n-1}\frac{(-1)^{n-j+1}\binom{n}{j}}{\binom{n}{b}-\binom{j}{b}}. $$

Comparing this formula with the (incorrect) one from the accepted answer, we change variables in the sum to $s=n-j$, yielding

$$ \sum_{s=1}^{n}\frac{(-1)^{s+1}\binom{n}{s}}{1-\binom{n-s}{b}/\binom{n}{b}}, $$ whereas the incorrect accepted answer states $$ \sum_{s=1}^{n-b}\frac{(-1)^{s+1}\binom{n}{s}}{1-\binom{n-s}{b}/\binom{n}{b}}. $$ The only difference is in the range of the summation, and it arises due to a mistake made by the accepted answer in the $i=0$ case of the following manipulation: $$ \sum_{S\not=\varnothing}(-1)^{|S|+1}\left(\frac{\binom{n-|S|}{b}}{\binom{n}{b}}\right)^i\overset{!}{=}\sum_{s=1}^{n-b}(-1)^{s+1}\binom{n}{s}\left(\frac{\binom{n-s}{b}}{\binom{n}{b}}\right)^i. $$ The equality holds when $i\not=0$, but when $i=0$ the terms with $s>n-b$ do in fact contribute. The corrected formula reads as follows: $$ \sum_{S\not=\varnothing}(-1)^{|S|+1}\left(\frac{\binom{n-|S|}{b}}{\binom{n}{b}}\right)^i=\sum_{s=1}^{n}(-1)^{s+1}\binom{n}{s}\left(\frac{\binom{n-s}{b}}{\binom{n}{b}}\right)^i. $$ The rest of the reasoning in the accepted answer is correct, and with this fix yields the correct answer.

Answer 2

See this paper of Mahmoud for an example of a paper on this topic and references to others, including papers on the exact question you ask.

Answer 3

Although this has been studied before, I find it interesting to apply basic techniques. Here are two.

First, let $p_i$ be the probability that the first $i$ batches don't cover everything, and let $I_i$ be the $0-1$ indicator for that event. The number of batches required to collect all $n$ is $\sum_{i=0}^\infty I_i$, so the average value is $\sum_{i=0}^\infty p_i$.

Each probability $p_i$ can be computed by inclusion-exclusion because it is easy to calculate the probability that $i$ batches will all miss a particular subset $S$.

$$p_i = \sum_{S \ne \emptyset} (-1)^{|S|+1} \left( \frac{n-|S| \choose b}{n \choose b} \right)^i = \sum_{s=1}^{n-b} (-1)^{s+1} {n \choose s} \left( \frac{n-s \choose b}{n \choose b} \right)^i$$

We can change the order of summation:

$$\begin{eqnarray}\sum_{i=0}^\infty p_i &=& \sum_{i=0}^\infty \sum_{s=1}^{n-b}(-1)^{s+1 }{n \choose s} \left( \frac{n-s \choose b}{n \choose b} \right)^i \newline &=&\sum_{s=1}^{n-b} \sum_{i=0}^\infty (-1)^{s+1} {n \choose s} \left( \frac{n-s \choose b}{n \choose b} \right)^i \newline &=& \sum_{s=1}^{n-b} \frac{(-1)^{s+1} {n \choose s}}{1- {n-s \choose b}/{n \choose b}} \end{eqnarray}$$

This is an exact answer, but because the sum alternates, it's hard to pick out the largest contribution. It takes some work to simplify the sum to $nH_n \approx n(\log n + \gamma)$ if $b=1$.

A second approach is to start with a standard coupon collector who picks coupons one at a time, and mark off batches of $b$ distinct coupons (ignoring coupons before the start of the batch). It takes an average of $c(n,b)= \frac{n}{n} + \frac{n}{n-1} + ... + \frac{n}{n-b+1}$ coupons to get a batch of $b$ distinct coupons, but after you find the last coupon you continue to the end of the batch. So, the average number of batches is between $nH_n/c(n,b)$ and $1+nH_n/c(n,b)$.