Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-05T05:46:16.505Z Has data issue: false hasContentIssue false
  • English
  • Français

The Coupon Collector's Problem Revisited: Asymptotics of the Variance

Part of: Limit theorems

Published online by Cambridge University Press:  04 January 2016

Aristides V. Doumas  and
Vassilis G. Papanicolaou
Aristides V. Doumas*
Affiliation:
National Technical University of Athens
Vassilis G. Papanicolaou*
Affiliation:
National Technical University of Athens
*
∗ Postal address: Department of Mathematics, National Technical University of Athens, Zografou Campus, 157 80 Athens, Greece.
∗ Postal address: Department of Mathematics, National Technical University of Athens, Zografou Campus, 157 80 Athens, Greece.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We develop techniques for computing the asymptotics of the first and second moments of the number TN of coupons that a collector has to buy in order to find all N existing different coupons as N → ∞. The probabilities (occurring frequencies) of the coupons can be quite arbitrary. From these asymptotics we obtain the leading behavior of the variance V[TN] of TN (see Theorems 3.1 and 4.4). Then, we combine our results with the general limit theorems of Neal in order to derive the limit distribution of TN (appropriately normalized), which, for a large class of probabilities, turns out to be the standard Gumbel distribution. We also give various illustrative examples.

Keywords

Coupon collector's problemhigher asymptoticslimit distribution

MSC classification

Primary: 60F05: Central limit and other weak theorems 60F99: None of the above, but in this section
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 44 , Issue 1 , March 2012 , pp. 166 - 195
Copyright
© Applied Probability Trust 

References

Apostol, T. M. (1976). Introduction to Analytic Number Theory. Springer, New York.Google Scholar
Bender, C. M. and Orszag, S. A. (1999). Advanced Mathematical Methods for Scientists and Engineers. Springer, New York.Google Scholar
Boneh, A. and Hofri, M. (1997). The coupon-collector problem revisited—a survey of engineering problems and computational methods. Commun. Statist. Stoch. Models 13, 39–66.Google Scholar
Boneh, S. and Papanicolaou, V. G. (1996). General asymptotic estimates for the coupon collector problem. J. Comput. Appl. Math. 67, 277–289.CrossRefGoogle Scholar
Boros, G. and Moll, V. (2004). Irresistible Integrals. Cambridge University Press.Google Scholar
Brayton, R. K. (1963). On the asymptotic behavior of the number of trials necessary to complete a set with random selection. J. Math. Anal. Appl. 7, 31–61.Google Scholar
Durrett, R. (2005). Probability: Theory and Examples, 3rd edn. Cambridge University Press.Google Scholar
Feller, W. (1966). An Introduction to Probability Theory and Its Applications, Vol. I, John Wiley, New York.Google Scholar
Flajolet, P., Gardy, D. and Thimonier, L. (1992). Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39, 207–229.CrossRefGoogle Scholar
Hildebrand, M. V. (1993). The birthday problem. Amer. Math. Monthly 100, 643.Google Scholar
Holst, L., Kennedy, J. E. and Quine, M. P. (1988). Rates of Poisson convergence for some coverage and urn problems using coupling. J. Appl. Prob. 25, 717–724.CrossRefGoogle Scholar
Neal, P. (2008). The generalised coupon collector problem. J. Appl. Prob. 45, 621–629.CrossRefGoogle Scholar
Ross, S. (2006). A First Course in Probability, 7th edn. Pearson Prentice Hall.Google Scholar
Rudin, W. (1987). Real and Complex Analysis. McGraw-Hill, New York.Google Scholar