Asymptotics of the rising moments for the coupon collector's problem

Aristides V Doumas (National Technical University of Athens)
Vassilis G Papanicolaou (National Technical University of Athens)

Abstract


We develop techniques of computing the asymptotics of the moments of the number $T_N$ of coupons that a collector has to buy in order to find all $N$ existing different coupons as $N\rightarrow \infty.$ The probabilities (occurring frequencies) of the coupons can be quite arbitrary. After mentioning the case where the coupon probabilities are equal we consider the general case (of unequal probabilities). For a large class of distributions (after adopting a dichotomy) we arrive at the leading behavior of the moments of $T_N$ as $N\rightarrow \infty.$ We also present various illustrative examples.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 1-15

Publication Date: March 22, 2013

DOI: 10.1214/EJP.v18-1746

References

  • Adler, Ilan; Oren, Shmuel; Ross, Sheldon M. The coupon-collector's problem revisited. J. Appl. Probab. 40 (2003), no. 2, 513--518. MR1978107
  • Apostol, Tom M. Introduction to analytic number theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976. xii+338 pp. MR0434929
  • Baum, Leonard E.; Billingsley, Patrick. Asymptotic distributions for the coupon collector's problem. Ann. Math. Statist. 36 1965 1835--1839. MR0182039
  • Bender, Carl M.; Orszag, Steven A. Advanced mathematical methods for scientists and engineers. I. Asymptotic methods and perturbation theory. Reprint of the 1978 original. Springer-Verlag, New York, 1999. xiv+593 pp. ISBN: 0-387-98931-5 MR1721985
  • Boneh, Arnon; Hofri, Micha. The coupon-collector problem revisited—a survey of engineering problems and computational methods. Comm. Statist. Stochastic Models 13 (1997), no. 1, 39--66. MR1430927
  • Boneh, Shahar; Papanicolaou, Vassilis G. General asymptotic estimates for the coupon collector problem. J. Comput. Appl. Math. 67 (1996), no. 2, 277--289. MR1390185
  • Brayton, Robert King. 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. MR0158427
  • Doumas, Aristides V.; Papanicolaou, Vassilis G. The coupon collector's problem revisited: asymptotics of the variance. Adv. in Appl. Probab. 44 (2012), no. 1, 166--195. MR2951551
  • du Boisberranger, Jérémie; Gardy, Danièle; Ponty, Yann. The weighted words collector. 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), 243--264, Discrete Math. Theor. Comput. Sci. Proc., AQ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012. MR2957335
  • Durrett, Richard. Probability: theory and examples. Second edition. Duxbury Press, Belmont, CA, 1996. xiii+503 pp. ISBN: 0-534-24318-5 MR1609153
  • Erdős, P.; Rényi, A. On a classical problem of probability theory. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 1961 215--220. MR0150807
  • Feller, William. An introduction to probability theory and its applications. Vol. I. Third edition John Wiley & Sons, Inc., New York-London-Sydney 1968 xviii+509 pp. MR0228020
  • Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs. Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Appl. Math. 39 (1992), no. 3, 207--229. MR1189469
  • Foata, Dominique; Han, Guo-Niu; Lass, Bodo. Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes. (French) [Hyperharmonic numbers and the coupon collector's brotherhood] Sém. Lothar. Combin. 47 (2001/02), Article B47a, 20 pp. MR1894021
  • Godwin, H. J.: On cartophily and motor cars, textitMath. Gazette 33 (1949) 169--171.
  • Holst, Lars. On birthday, collectors', occupancy and other classical urn problems. Internat. Statist. Rev. 54 (1986), no. 1, 15--27. MR0959649
  • Janson, Svante. Limit theorems for some sequential occupancy problems. J. Appl. Probab. 20 (1983), no. 3, 545--553. MR0713504
  • Neal, Peter. The generalised coupon collector problem. J. Appl. Probab. 45 (2008), no. 3, 621--629. MR2455173
  • Newman, Donald J.; Shepp, Lawrence. The double dixie cup problem. Amer. Math. Monthly 67 1960 58--61. MR0120672
  • Rudin, Walter. Real and complex analysis. Third edition. McGraw-Hill Book Co., New York, 1987. xiv+416 pp. ISBN: 0-07-054234-1 MR0924157
Bookmark and Share


Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.