A generalized coupon collector problem

DOI10.1239/JAP/1324046020MaRDI QIDQ3108477zbMATH OpenOpenAlexFDO

Authors Weiyu Xu, A. Kevin Tang

Publication date 4 January 2012

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.5608

zbMATH Keywords

state-space representationopportunistic schedulingcoupon collector problemexpected run

Mathematics Subject Classification ID

Extreme value theory; extremal stochastic processes (60G70) Combinatorial probability (60C05) Stopping times; optimal stopping problems; gambling theory (60G40)

Abstract: 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 $fracnlognd+fracnd(m-1)loglogn+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.

Recommendations

• The Generalised Coupon Collector Problem
• New results on a generalized coupon collector problem using Markov chains
• COUPON COLLECTING
• Optimization results for a generalized coupon collector problem
• Coupon collecting with quotas

Cites work

• scientific article; zbMATH DE number 3059214 (Why is no real title available?)
• Balanced Allocations
• Extreme value distributions for random coupon collector and birthday problems
• Martingale approach to the coupon collection problem
• Some New Aspects of the Coupon Collector's Problem
• The Double Dixie Cup Problem
• The Generalised Coupon Collector Problem
• The collector's brotherhood problem using the Newman-Shepp symbolic method

Cited in

(22)

• Applying coupon-collecting theory to computer-aided assessments
• On the optimality of coupon books
• The Weighted Coupon Collector’s Problem and Applications
• The coupon subset collection problem
• Waiting time for a small subcollection in the coupon collector problem with universal coupon
• Methods for Studying Generalized Birthday and Coupon Collection Problems
• Some upper and lower bounds on the coupon collector problem
• Some bounds on the coupon collector problem
• The Generalised Coupon Collector Problem
• Two Poisson limit theorems for the coupon collector's problem with group drawings
• The sticker collector's problem
• New results on a generalized coupon collector problem using Markov chains
• Optimal sampling strategies in the coupon collector's problem with unknown population size
• A survey of the coupon collector's problem with random sample sizes
• Optimization results for a generalized coupon collector problem
• Coupon subset collection problem with quotas
• Birthday paradox, coupon collectors, caching algorithms and self- organizing search
• Coupon collecting with quotas
• A generalized coupon collecting model as a parsimonious optimal stochastic assignment model
• Faster coupon collecting via replication with applications in gossiping
• The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp
• New easy to compute formulas for the moments of random variables appearing in the coupon collector problem

This page was built for publication: A generalized coupon collector problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3108477)