MATEMATIČKI VESNIK
МАТЕМАТИЧКИ ВЕСНИК



MATEMATIČKI VESNIK
COUPON COLLECTOR PROBLEM WITH PENALTY COUPON
B. Todić

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 additional 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 additional 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.

Creative Commons License

Keywords: Coupon collector problem; penalty coupon; waiting time; Markov chain; transition probability matrix; random walk.

MSC: 60C05

DOI: 10.57016/MV-BGON6192

Pages:  15--28     

Volume  76 ,  Issue  1-2 ,  2024