A generalized coupon collector problem

DOI10.1239/JAP/1324046020zbMATH Open1239.60030arXiv1010.5608OpenAlexW3104290553MaRDI QIDQ3108477FDOQ3108477

Authors: Weiyu Xu, A. Kevin Tang 

Publication date: 4 January 2012

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

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.

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

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

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)

Cites Work

• Balanced Allocations
• Title not available (Why is that?)
• The Double Dixie Cup Problem
• The collector's brotherhood problem using the Newman-Shepp symbolic method
• The Generalised Coupon Collector Problem
• Some New Aspects of the Coupon Collector's Problem
• Extreme value distributions for random coupon collector and birthday problems
• Martingale approach to the coupon collection problem

Cited In (22)

• Applying coupon-collecting theory to computer-aided assessments
• The Weighted Coupon Collector’s Problem and Applications
• On the optimality of coupon books
• 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
• New easy to compute formulas for the moments of random variables appearing in the coupon collector problem
• The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp

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)