Batched Coupon Collector Problem

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]$?

• I guess by $k$ you mean the target number of coupons out of $n$, but you should define the notation you use. The linked question does not assume that the coupons in each batch are distinct. Are you assuming to the contrary that you get $b$ different coupons? – Douglas Zare Jan 22 '16 at 20:27
• The question posed in that link is not assuming distinct batch items. However, that specific answer that I am referring to, has the assumption of distinct batch items. I defined $k$ as you suggested. Thanks! – Mohsen Karimzadeh Kiskani Jan 22 '16 at 21:24

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)$.

• Thanks Douglas for the beautiful insights and solution to the problem. – Mohsen Karimzadeh Kiskani Jan 24 '16 at 2:56

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.