3
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$ Jan 22, 2016 at 20:27
  • $\begingroup$ 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! $\endgroup$
    – mhsnk
    Jan 22, 2016 at 21:24

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ It's been a long time that I have worked on this problem and I totally forgot it. But to your wisdom, I will just untag the accepted solution. $\endgroup$
    – mhsnk
    Jun 30, 2019 at 1:57
  • $\begingroup$ Sure, and I have updated my answer just now to include a detailed explanation of the mistake. The logic of the other answer is correct, relatively minor "bugfix". $\endgroup$
    – pre-kidney
    Jun 30, 2019 at 2:02
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Thanks Douglas for the beautiful insights and solution to the problem. $\endgroup$
    – mhsnk
    Jan 24, 2016 at 2:56
  • $\begingroup$ This answer is incorrect, as can be seen from the discussion on math.SE (math.stackexchange.com/questions/3278200/box-of-10-chocolates/…) regarding the case $b=3,n=10$. By monotonicity, this expression should be less than the corresponding coupon collector, which is $\frac{100}{3}$, but when you evaluate it (see gist.github.com/avi-levy/0ca97f5d33028b3e4f399f9dd20b69b8) you obtain a value around $45$. $\endgroup$
    – pre-kidney
    Jun 30, 2019 at 0:44
  • $\begingroup$ Or rather, the $100/3$ should be $7381/252\approx 29$ but the same argument applies... $\endgroup$
    – pre-kidney
    Jun 30, 2019 at 0:51
  • $\begingroup$ One potential source of inaccuracy is the unjustified interchange of summation and infinite alternating summation $\endgroup$
    – pre-kidney
    Jun 30, 2019 at 0:55
  • $\begingroup$ @Douglas Zare I found the source of the inaccuracy, and it is not related to the interchange of summation, but rather to an incorrect truncation of the range of the $s$ summation. In fact, it is an understandable mistake since the truncated terms in the sum are zero except when $i=0$, and that is the problem case. Fortunately there is a simple fix, and the correct formula is even simpler! See my answer. $\endgroup$
    – pre-kidney
    Jun 30, 2019 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.