Generalized Coupon Collection: The Superlinear Case

• Published in: Journal of applied probability 2011-03, Vol.48 (1), p.189-199
• Main Author: Smythe, R. T.
• Format: Article
• Language: English
• Subjects: 05A05; 60C05; 60F05; 60G42; Applications; Approximation; Asymptotic methods; Central limit theorem; coupon collection; Coupons; Determinism; Exact sciences and technology; Limit theorems; martingale; Martingales; Mathematical theorems; Mathematics; occupancy problem; Poisson limit; Probability and statistics; Probability distribution; Probability theory and stochastic processes; Random numbers; Random variables; Sample size; Sciences and techniques of general use; Statistics; Stochastic processes; Studies; Urn model
• ISSN: 0021-9002; 1475-6072
• DOI: 10.1239/jap/1300198144

We consider a generalized form of the coupon collection problem in which a random number, S, of balls is drawn at each stage from an urn initially containing n white balls (coupons). Each white ball drawn is colored red and returned to the urn; red balls drawn are simply returned to the urn. The question considered is then: how many white balls (uncollected coupons) remain in the urn after the k n draws? Our analysis is asymptotic as n → ∞. We concentrate on the case when k n draws are made, where k n / n → ∞ (the superlinear case), although we sketch known results for other ranges of k n . A Gaussian limit is obtained via a martingale representation for the lower superlinear range, and a Poisson limit is derived for the upper boundary of this range via the Chen-Stein approximation.