Gaussian phases in generalized coupon collection
Hosam M. Mahmoud · Advances in Applied Probability · 2010
In this paper we consider a generalized coupon collection problem in which a customer repeatedly buys a random number of distinct coupons in order to gather a large number n of available coupons. We address the following question: How many different coupons are collected after k = k n draws, as n → ∞? We identify three phases of k n : the sublinear, the linear, and the superlinear. In the growing sublinear phase we see o ( n ) different coupons, and, with true randomness in the number of purchases, under the appropriate centering and scaling, a Gaussian distribution is obtained across the entire phase. However, if the number of purchases is fixed, a degeneracy arises and normality holds only at the higher end of this phase. If the number of purchases have a fixed range, the small number of different coupons collected in the sublinear phase is upgraded to a number in need of centering and scaling to become normally distributed in the linear phase with a different normal distribution of the type that appears in the usual central limit theorems. The Gaussian results are obtained via martingale theory. We say a few words in passing about the high probability of collecting nearly all the coupons in the superlinear phase. It is our aim to present the results in a way that explores the critical transition at the ‘seam line’ between different Gaussian phases, and between these phases and other nonnormal phases.