Coupon Collecting with Quotas

Russell May

Abstract


We analyze a variant of the coupon collector's problem, in which the probabilities of obtaining coupons and the numbers of coupons in a collection may be non-uniform. We obtain a finite expression for the generating function of the probabilities to complete a collection and show how this generalizes several previous results about the coupon collector's problem. Also, we provide applications about computational complexity and approximation.


Full Text: PDF