A Generalized Coupon Collector Problem

Details A Generalized Coupon Collector Problem A Generalized Coupon Collector Problem

2010-10-27

arxiv.org/abs/1010.5608v2

Computer Science

Information Theory

20 pages, 6 figures, preprint

Scientific paper

This paper provides analysis to a generalized version of the coupon collector problem, in which the collector gets $d$ distinct coupons each run and she chooses the one that she has the least so far. On the asymptotic case when the number of coupons $n$ goes to infinity, we show that on average $\frac{n\log n}{d} + \frac{n}{d}(m-1)\log\log{n}+O(mn)$ runs are needed to collect $m$ sets of coupons. An efficient exact algorithm is also developed for any finite case to compute the average needed runs exactly. Numerical examples are provided to verify our theoretical predictions.

Affiliated with

Also associated with

No associations

Rating

A Generalized Coupon Collector Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Generalized Coupon Collector Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Generalized Coupon Collector Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-485083