The ‘coupon collection problem’ refers to a class of occupancy problems in which j identical items are distributed, independently and at random, to n cells, with no restrictions on multiple occupancy. Identifying the cells as coupons, a coupon is ‘collected’ if the cell is occupied by one or more of the distributed items; thus, some coupons may never be collected, whereas others may be collected once or twice or more. We call the number of coupons collected exactly r times coupons of type r. The coupon collection model we consider is general, in that a random number of purchases occurs at each stage of collecting a large number of coupons; the sample sizes at each stage are independent and identically distributed according to a sampling distribution. The joint behavior of the various types is an intricate problem. In fact, there is a variety of joint central limit theorems (and other limit laws) that arise according to the interrelation between the mean, variance, and range of the sampling distribution, and of course the phase (how far we are in the collection processes). According to an appropriate combination of the mean of the sampling distribution and the number of available coupons, the phase is sublinear, linear, or superlinear. In the sublinear phase, the normalization that produces a Gaussian limit law for uncollected coupons can be used to obtain a multivariate central limit law for at most two other types — depending on the rates of growth of the mean and variance of the sampling distribution, we may have a joint central limit theorem between types 0 and 1, or between types 0, 1, and 2. In the linear phase we have a multivariate central limit theorem among the types 0, 1,…, k for any fixed k.

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 kn draws? Our analysis is asymptotic as n → ∞. We concentrate on the case when kn draws are made, where kn / n → ∞ (the superlinear case), although we sketch known results for other ranges of kn. 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.

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 = kn draws, as n → ∞? We identify three phases of kn: 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.

A circle is covered by random arcs with a given length a and endpoints chosen (independently and uniformly) among m equispaced points on the circle. The asymptotic distribution as a → 0 and m → ∞of the number of arcs required for complete coverage is given. The result connects earlier results for the cases ma = 1 (a discrete problem) and m = ∞ (the continuous limiting case).