0
$\begingroup$

In the coupon collectors problem, there are $n$ unique coupons and each cereal box has 1 coupon only. I would like to modify the problem such that there are $m$ boxes of cereal in total and each box has $c_i (1 \le c_i \le n)$ number of coupons.

Then how many boxes of cereal do I need to buy to have $n$ unique coupons?

  • 0
    Are all the coupons in a given box guaranteed to be different? If not, you need enough boxes to have the number of coupons in the standard problem. If yes, I don't think there will be a nice solution for unspecified $c_i$2012-08-06
  • 0
    As per Ross Millikan, there are not enough details in the question. Furthermore, I don't understand how the parameter $m$ affects the problem, since it will not factor in the solution to your problem.2012-08-07
  • 0
    @RossMillikan No, it is not guaranteed to be different. I don't understand what "enough boxes" means. Could you explain more?2012-08-07
  • 0
    In the standard problem, you expect to need about $n \log n$ coupons to have a complete set. If each box just contains random coupons (drawn with replacement), you still need that many, so keep buying boxes until you have that many.2012-08-07
  • 0
    @RossMillikan Thanks a lot for explanation!2012-08-07

1 Answers 1

1

Since the coupons within a box are not guaranteed to be different, basically we are just buying boxes in batches of $c_i$.

As in the original coupon problem, we expect to have to buy $n \log n$ original boxes to make for a complete set of $n$ unique coupons. So if each new box contains $c$ coupons, we expect to need to buy $\dfrac{n \log n}c$.

However, without any specification on how the $c_i$ are distributed for the new boxes we cannot make an estimate of the number of boxes we need to buy in the new situation.

Let us tackle the general situation where each box has the same probability distribution, say chance $p_i$ to contain $i$ boxes, $1 \le i \le n$. Then each box is expected to contain $$E = \sum_{i=1}^n ip_i$$ coupons. It follows that we expect to have to buy $$\frac{n \log n}E$$ boxes to complete a set.