Coupon collector's problem variation with packages of unique coupons

271 Views Asked by At

Given a collection of $n$ coupons, you can purchase a package of $k$ unique coupons. What is the probability that you will collect all $n$ with $T$ packages?

For the case where $k=n$, you always get the full collection after 1 package.

For the case $k=n-1$, after one draw it is the probability of not drawing the last remaining card, so it should be similar to a geometric distribution.

For the case $k=1$, the answer reduces to the usual coupon collector's problem, found here Probability distribution in the coupon collector's problem

What is the general formula?


I just realized this is a duplicate of a question on MO, so the answers there may also be helpful: https://mathoverflow.net/questions/229060/batched-coupon-collector-problem

1

There are 1 best solutions below

3
On BEST ANSWER

The Coupon Collector's Problem with the coupons arriving in packages of unique coupons can be solved by inclusion-exclusion, much like the standard Coupon Collector's Problem.

Let's say a collection of $T$ packages of $k$ coupons has "Property $i$" if none of the packages include coupon number $i$, for $1 \le i \le n$, and define $S_j$ to be the totals of the probabilites of all the collections with $j$ of the properties, for $1 \le j \le n$. Then $$S_j = \binom{n}{j} \left( \frac{\binom{n-j}{k}}{\binom{n}{k}} \right) ^T$$ By inclusion-exclusion, the probability that a collection of $T$ packages has none of the properties (in other words, contains a complete set of coupons) is $$1+\sum_{j=1}^n (-1)^j S_j$$