2
$\begingroup$

I was looking at various extensions of the classical Coupon Collector problem, but couldn't find any answers or hints for the following modification:

Assume there are $n$ distinct coupons and you get them in batches of a different (random) size. That is, assume that every time you get a black box with coupons in it, whose number can be from $0$ to $n$ and coupons within a black box are distinct. The probability of having a specific coupon in a box is $p$ (that is, it's the same for all). What is the expected number of black-boxes one needs to open to collect all coupons?

$\endgroup$
3
$\begingroup$

I'll assume that you intended to imply that each coupon independently has probability $p$ to be in any given black box.

Then we have $n$ independent Bernoulli trials with probability $p$ and are looking for the expected time for all of them to have succeeded at least once. The probability for a given coupon not to have been collected after $k$ black boxes is $(1-p)^k$, so it has been collected with probability $1-(1-p)^k$, so the probability for all coupons to have been collected is $\left(1-(1-p)^k\right)^n$, so the probability that they haven't all been collected is $1-\left(1-(1-p)^k\right)^n$. The expected number of black boxes required to collect all coupons is the sum of these probabilities:

\begin{align} \sum_{k=0}^\infty\left(1-\left(1-(1-p)^k\right)^n\right) &=\sum_{k=0}^\infty\left(1-\sum_{j=0}^n\binom nj\left(-(1-p)^k\right)^j\right) \\ &=\sum_{k=0}^\infty\sum_{j=1}^n(-1)^{j-1}\binom nj(1-p)^{jk} \\ &=\sum_{j=1}^n(-1)^{j-1}\binom nj\sum_{k=0}^\infty(1-p)^{jk} \\ &=\sum_{j=1}^n(-1)^{j-1}\binom nj\frac1{1-(1-p)^j}\;. \end{align}

The same result can also be derived using the maximum-minimums identity. The time it takes to collect all coupons is the maximum of the times $X_i$, where $X_i$ is the time it takes to collect the $i$-th coupon:

\begin{align} \def\ex#1{\mathbb E\left[#1\right]} \ex{\max_iX_i} &=\sum_i\ex{X_i}-\sum_{i\lt j}\ex{\min\{X_i,X_j\}}+\sum_{i\lt j\lt k}\ex{\min\{X_i,X_j,X_k\}}-\cdots \\ &=\sum_{j=1}^n(-1)^{j-1}\binom nj\frac1{1-(1-p)^j}\;, \end{align}

since the minimum of the completion times of $j$ particular coupons is the expected time it takes for a Bernoulli trial with success probability $1-(1-p)^j$ to succeed. Equivalently, we could use inclusion-exclusion to find the probability that not all coupons have been collected and then sum over $k$ as above.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

Hint 1: The expected number of coupons in a single box is $E[X]$. The expected number of coupons in two boxes is $E[X+X] = E[X] + E[X] = 2E[X]$. You can extend this to the expected number of coupons in $m$ boxes. So you can calculate the expected number of boxes required to get a total of $y$ coupons.

Hint 2: There is a formula for counting the number of coupons required to collect all $n$ coupons. Once you calculate this, you can replace $y$ in Hint 1.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Am I right thinking that it will be about $\frac{n \ln n}{K }$, where $K$ is the expected number of coupons in a box, that is $K = np$? $\endgroup$ – Vika Apr 6 '16 at 17:23
  • $\begingroup$ @Vika the expected number of coupons in a box is $K = \frac{n+1}{2}$, other than that, you're correct. $\endgroup$ – ashleydc Apr 6 '16 at 18:14
  • $\begingroup$ Why doesn't the answer depend on $p$ then? If $p$ is really small, then I think we will need to buy more boxes. $\endgroup$ – Vika Apr 6 '16 at 19:29
  • $\begingroup$ @Vika My apologies, I mis-read the question and didn't see the part about the coupons in the black box being distinct. I thought that there could be duplicate coupons. I'm taking a second look at this and will edit my answer if I can come up with an approach $\endgroup$ – ashleydc Apr 7 '16 at 2:44
  • $\begingroup$ The reason that I was confused was because when I read that there could be between $1$ and $n$ coupons in a box, I thought that the probability for each was identical (for example, the probability of receiving a box with $n$ coupons was $\frac{1}{n}$). It looks like the problem is actually stating that there is $1$ box with $n$ coupons, $n$ boxes with $1$ coupon, ... Is this correct? $\endgroup$ – ashleydc Apr 7 '16 at 3:07

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.