The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp

Doumas, Aristides V.; Papanicolaou, Vassilis G.

ESAIM: Probability and Statistics, Tome 20 (2016), pp. 367-399.

The “double Dixie cup problem” of [D.J. Newman and L. Shepp, Amer. Math. Monthly 67 (1960) 58–61] is a well-known variant of the coupon collector’s problem, where the object of study is the number $T_m\left(N\right)$ of coupons that a collector has to buy in order to complete $m$ sets of all $N$ existing different coupons. More precisely, the problem is to determine the asymptotics of the expectation (and the variance) of $T_m\left(N\right)$, as well as its limit distribution, as the number $N$ of different coupons becomes arbitrarily large. The classical case of the problem, namely the case of equal coupon probabilities, is here extended to the general case, where the probabilities of the selected coupons are unequal. In the beginning of the article we give a brief review of the formulas for the moments and the moment generating function of the random variable $T_m\left(N\right)$. Then, we develop techniques of computing the asymptotics of the first and the second moment of $T_m\left(N\right)$ (our techniques apply to the higher moments of $T_m\left(N\right)$ as well). From these asymptotic formulas we obtain the leading behavior of the variance $V\left[T_m\left(N\right)\right]$ as $N\to \infty$. Finally, based on the asymptotics of $E\left[T_m\left(N\right)\right]$ and $V\left[T_m\left(N\right)\right]$ we obtain the limit distribution of the random variable $T_m\left(N\right)$ for large classes of coupon probabilities. As it turns out, in many cases, albeit not always, $T_m\left(N\right)$ (appropriately normalized) converges in distribution to a Gumbel random variable. Our results on the limit distribution of $T_m\left(N\right)$ generalize a well-known result of [P. Erdős and A. Rényi, Magyar. Tud. Akad. Mat. Kutató Int. Közl. 6 (1961) 215–220] regarding the limit distribution of $T_m\left(N\right)$ for the case of equal coupon probabilities.

Classification : 60F05, 60F99
Mots clés : Urn problems, coupon collector’s problem, double Dixie cup problem, rising moments, limit distribution, Gumbel distribution, generalized Zipf law

T.M. Apostol, Introduction to Analytic Number Theory. Springer-Verlag, New York (1976). | Zbl

A.D. Barbour, L. Holst and S. Janson, Poisson Approximation, Oxford Studies in Probability – 2. Clarendon Press, Oxford (1992). | Zbl

C.M. Bender and S.A. Orszag, Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory. Springer-Verlag, New York (1999). | Zbl

A. Boneh and M. Hofri, The Coupon Collector Problem Revisited–a Survey of Engineering Problems and Computational Methods. Commun. Stat. Stochastic Models 13 (1997) 39–66. | DOI | Zbl

S. Boneh and V.G. Papanicolaou, General Asymptotic Estimates for the Coupon Collector Problem. J. Comput. Appl. Math. 67 (1996) 277–289. | DOI | Zbl

R.K. Brayton, On the asymptotic behavior of the number of trials necessary to complete a set with random selection. J. Math. Anal. Appl. 7 (1963) 31–61. | DOI | Zbl

P. Diaconis and S. Holmes, A Bayesian peek into Feller volume I, Special issue in memory of D. Basu. Sankhyā Ser. A 64 (2002) 820–841. | Zbl

A.V. Doumas and V.G. Papanicolaou, The Coupon Collector’s Problem Revisited: Asymptotics of the Variance. Adv. Appl. Prob. 44 (2012) 166–195. | DOI | Zbl

A.V. Doumas and V.G. Papanicolaou, Asymptotics of the rising moments for the Coupon Collector’s Problem. Electron. J. Probab. 18 (2012) 1–15. | Zbl

R. Durrett, Probability: Theory and Examples, Duxbury Advanced Series. Brooks/Cole – Thomson Learning, 3rd edn. Belmont, CA, USA (2005). | Zbl

P. Erdős and A. Rényi, On a classical problem of probability theory. Magyar. Tud. Akad. Mat. Kutató Int. Közl. 6 (1961) 215–220. | Zbl

R. Fagin, Asymptotic miss ratios over independent references. J. Comput. System Sci. 14 (1977) 222–250. | DOI | Zbl

W. Feller, An Introduction to Probability Theory and Its Applications. Vols. I and II. John Wiley & Sons, Inc., New York (1966). | Zbl

L. Flatto, Limit Theorems for Some Random Variables Associated with Urn Models. Ann. Prob. 10 (1982) 927–934. | DOI | Zbl

L. Holst, On Birthday, Collectors’, Occupancy and other classical Urn problems. Int. Statist. Rev. 54 (1986) 15–27. | DOI | Zbl

P.R. Jelenković, Asymptotic approximation of the move-to-front search cost distribution and least-recently-used caching fault probabilities. Ann. Appl. Prob. 9 (1999) 430–464. | DOI | Zbl

N. Kaplan, A generalization of a result of Erdős and Rényi. J. Appl. Prob. 14 (1977) 212–216. | DOI | Zbl

K.L. Locey and J.T. Lennon, Scaling laws predict global microbial diversity. Proc. of Natl. Acad. Sci. USA 113 (2016) 5970–5975. | DOI

H.M. Mahmoud, Pólya urn models. CRC Press, New York (2008). | Zbl

P. Neal, The Generalised Coupon Collector Problem. J. Appl. Prob. 45 (2008) 621–629. | DOI | Zbl

D.J. Newman and L. Shepp, The double Dixie cup problem. Amer. Math. Monthly 67 (1960) 58–61. MR0120672 | DOI | Zbl

S. Ross, A First Course in Probability, 8th edn. Pearson Prentice Hall, Pearson Education, Inc., Upper Saddle River, NJ (2010).

S. Ross, Introduction to Probability Models, 10th edn. Elsevier Inc., Burlington, MA (2010). | Zbl

W. Rudin, Real and Complex Analysis. McGraw-Hill, New York (1987). | Zbl

The Dixie Cup Company History. Available at: http://sites.lafayette.edu/dixiecollection/ (2016).