Journal article
A Generalized Coupon Collector Problem
Journal of applied probability, Vol.48(4), pp.1081-1094
12/2011
DOI: 10.1017/S0021900200008639
Abstract
This paper presents an analysis of a generalized version of the coupon collector problem, in which the collector receives d coupons each run and chooses the least-collected coupon so far. In the asymptotic case when the number of coupons n goes to infinity, we show that, on average, (nlogn) / d + (n / d)(m − 1)log logn + O(mn) runs are needed to collect m sets of coupons. An exact algorithm is also developed for any finite case to compute the exact mean number of runs. Numerical examples are provided to verify our theoretical predictions.
Details
- Title: Subtitle
- A Generalized Coupon Collector Problem
- Creators
- Weiyu XuA. Kevin Tang
- Resource Type
- Journal article
- Publication Details
- Journal of applied probability, Vol.48(4), pp.1081-1094
- DOI
- 10.1017/S0021900200008639
- ISSN
- 0021-9002
- eISSN
- 1475-6072
- Language
- English
- Date published
- 12/2011
- Academic Unit
- Electrical and Computer Engineering
- Record Identifier
- 9984083868702771
Metrics
7 Record Views