Optimality Results for Coupon Collection
Abstract We consider the coupon collection problem, where each coupon is one of the types 1,β¦, s with probabilities given by a vector π. For specified numbers r 1 ,β¦, r s , we are interested in finding π that minimizes the expected time to obtain at least r i type- i coupons for all i =1,β¦, s . For example, for s =2, r 1 =1, and r 2 = r , we show that p 1 =(log r βlog(log r ))β r is close to optimal.