Coupon Collector Problem with Penalty Coupon

Abstract

In this paper we consider a generalization of the coupon collector problem where we assume that the set of available coupons consists of standard coupons and an addi-tional penalty coupon, which does not belong to the collection and interferes with collecting standard coupons. Applying Markov chain approach the following problem is solved: how many coupons (on average) one has to purchase in order to complete a collection without interference or to collect n more penalty coupons than standard coupons. Also, we obtain ad-ditional results related to the distribution of the waiting time until the collection is sampled without interference or until n more penalty coupons than standard coupons is sampled.