Skip to main content
3 of 4
added 230 characters in body
Herman
  • 101
  • 1
  • 5

How to solve a generalization of the Coupon Collector's problem

The coupon collector's problem is a problem in probability theory that states the following (from wikipedia):

Suppose that there are $n$ coupons, from which coupons are being collected with replacement. What is the probability that more than $t$ sample trials are needed to collect all $n$ coupons?

A generalization of this problem was proposed by Newmann & Shepp, by requiring that $k$ samples of each coupon be collected. The answer to this is known.

I, however, need to calculate the answer to an even further generalization, which is:

How many sample trials are needed to collect a certain subset of $n$, call it $m$, at least $k$ times?

Any help or a point in the right direction would be greatly appreciated.

(Edit:) Here is an example to illustrate the problem:

Let's say we would like to collect coupons that come with a certain brand of cereal. We know there are 10 (read: $n$) different types of coupons , but we are really only interested in 5 (read: $m$) of the 10 (since these coupons apply to products we would like to buy). We would like to also give sets of these 5 coupons to our friends, so they can share in the joy. So, assuming every coupon has equal chance to appear in any box of cereal, how many boxes would you need to buy to have 3 (read: $k$) sets of the 5 coupons you are interested in?

The difference that $m$ introduces to the problem is the following: For every coupon you collect, the odds of collecting a new coupon becomes less. If it was only $n$, then when you have collected all but the last coupon your chance of getting the last one in the next trial is $1/n$. If you are only interested in collecting $m$ though, the chance of collecting the last coupon on the next trial is $(n-m+1)/n$

(Edit #2): This problem can be stated simply as a balls-and-bins problem. If we have $n$ bins, how many balls need to be thrown so that at least $m$ bins have at least $k$ balls?

Herman
  • 101
  • 1
  • 5