Some New Aspects of the Coupon Collector's Problem

We extend the classical coupon collector's problem to one in which two collectors are simultaneously and independently seeking collections of d coupons. We find, in finite terms, the probability that the two collectors finish at the same trial, and we find, using the methods of Gessel and Vienn...

Full description

Saved in:
Bibliographic Details
Published in:SIAM review 2006-09, Vol.48 (3), p.549-565
Main Authors: Myers, Amy N., Wilf, Herbert S.
Format: Article
Language:English
Subjects:
Approximation
Collectors
Coupon collectors problem
Coupons
Discount coupons
Discrete mathematics
Exact sciences and technology
Game theory
Generating function
Infinite series
Integers
Log integral function
Logic and foundations
Mathematical lattices
Mathematical logic, foundations, set theory
Mathematical models
Mathematical problems
Mathematics
Sciences and techniques of general use
Sigest
Studies
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We extend the classical coupon collector's problem to one in which two collectors are simultaneously and independently seeking collections of d coupons. We find, in finite terms, the probability that the two collectors finish at the same trial, and we find, using the methods of Gessel and Viennot, the probability that the game has the following "ballot-like" character: the two collectors are tied with each other for some initial number of steps, and after that the player who first gains the lead remains ahead throughout the game. As a by-product we obtain the evaluation in finite terms of certain infinite series whose coefficients are powers and products of Stirling numbers of the second kind. We study the variant of the original coupon collector's problem in which a single collector wants to obtain at least h copies of each coupon. Here we give a simpler derivation of results of Newman and Shepp and extend those results. Finally, we obtain the distribution of the number of coupons that have been obtained exactly once ("singletons") at the conclusion of a successful coupon collecting sequence.
ISSN:0036-1445
1095-7200
DOI:10.1137/060654438