Article contents
Optimality Results for Coupon Collection
Published online by Cambridge University Press: 24 October 2016
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=(logr−log(logr))∕r is close to optimal.
MSC classification
- Type
- Research Papers
- Information
- Copyright
- Copyright © Applied Probability Trust 2016
References
- 4
- Cited by