Geodesic
The siblings of the coupon collector
Teoriâ veroâtnostej i ee primeneniâ, Tome 62 (2017) no. 3, pp. 556-586 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The following variant of the collector's problem has attracted considerable attention relatively recently. There is one main collector who collects coupons. Assume there are $N$ different types of coupons with, in general, unequal occurring probabilities. When the main collector gets a "double,” she gives it to her older brother; when this brother gets a "double,” he gives it to the next brother, and so on. Hence, when the main collector completes her collection, the album of the $j$th collector, $j=2, 3, \dots$, will still have $U_j^N$ empty spaces. In this article we develop techniques of computing asymptotics of the average $\mathbf{E}[U_j^N]$ of $U_j^N$ as $N\to \infty$, for a large class of families of coupon probabilities (in many cases the first three terms plus an error). It is notable that in some cases $\mathbf{E}[U_j^N]$ approaches a finite limit as $N\to \infty$, for all $j\ge 2$. Our results concern some popular distributions such as exponential, polynomial, logarithmic, and the (well known for its applications) generalized Zipf law. We also conjecture on the maximum of $\mathbf{E}[U_j^N]$.
Keywords: urn problems, generalized coupon collector's problem (GCCP), hyperharmonic numbers, Lambert series, generalized Zipf law. 
@article{TVP_2017_62_3_a6,
     author = {A. V. Doumas and V. G. Papanicolaou},
     title = {The siblings of the coupon collector},
     journal = {Teori\^a vero\^atnostej i ee primeneni\^a},
     pages = {556--586},
     year = {2017},
     volume = {62},
     number = {3},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/TVP_2017_62_3_a6/}
}
TY  - JOUR
AU  - A. V. Doumas
AU  - V. G. Papanicolaou
TI  - The siblings of the coupon collector
JO  - Teoriâ veroâtnostej i ee primeneniâ
PY  - 2017
SP  - 556
EP  - 586
VL  - 62
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TVP_2017_62_3_a6/
LA  - en
ID  - TVP_2017_62_3_a6
ER  - 
%0 Journal Article
%A A. V. Doumas
%A V. G. Papanicolaou
%T The siblings of the coupon collector
%J Teoriâ veroâtnostej i ee primeneniâ
%D 2017
%P 556-586
%V 62
%N 3
%U http://geodesic.mathdoc.fr/item/TVP_2017_62_3_a6/
%G en
%F TVP_2017_62_3_a6
A. V. Doumas; V. G. Papanicolaou. The siblings of the coupon collector. Teoriâ veroâtnostej i ee primeneniâ, Tome 62 (2017) no. 3, pp. 556-586. http://geodesic.mathdoc.fr/item/TVP_2017_62_3_a6/

[1] I. Adler, S. Oren, S. M. Ross, “The coupon collector's problem revisited”, J. Appl. Probab., 40:2 (2003), 513–518 | DOI | MR | Zbl

[2] L. E. Baum, P. Billingsley, “Asymptotic distributions for the coupon collector's problem”, Ann. Math. Statist., 36:6 (1965), 1835–1839 | DOI | MR | Zbl

[3] J. du Boisberranger, D. Gardy, Y. Ponty, “The weighted words collector”, 23rd intern. meeting on probabilistic, combinatorial, and asymptotic methods for the analysis of algorithms (AofA'12), Discrete Math. Theor. Comput. Sci. Proc., Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2012, 243–264 | MR | Zbl

[4] A. Boneh, M. Hofri, “The coupon-collector problem revisited – a survey of engineering problems and computational methods”, Comm. Statist. Stochastic Models, 13:1 (1997), 39–66 | DOI | MR | Zbl

[5] S. Boneh, V. G. Papanicolaou, “General asymptotic estimates for the coupon collector problem”, J. Comput. Appl. Math., 67:2 (1996), 277–289 | DOI | MR | Zbl

[6] G. Boros, V. Moll, Irresistible integrals. Symbolics, analysis and experiments in the evaluation of integrals, Cambridge Univ. Press, Cambridge, 2004, xiv+306 pp. | DOI | MR | Zbl

[7] 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 | MR | Zbl

[8] P. Diaconis, S. Holmes, “A Bayesian peek into Feller volume. I”, Sankhyā Ser. A, 64:3, part 2, Special issue in memory of D. Basu (2002), 820–841 | MR | Zbl

[9] A. V. Doumas, V. G. Papanicolaou, “The coupon collector's problem revisited: asymptotics of the variance”, Adv. in Appl. Probab., 44:1 (2012), 166–195 | DOI | MR | Zbl

[10] A. V. Doumas, V. G. Papanicolaou, “Asymptotics of the rising moments for the coupon collector's problem”, Electron. J. Probab., 18 (2013), 41, 15 pp. | DOI | MR | Zbl

[11] A. V. Doumas, V. G. Papanicolaou, “The coupon collector's problem revisited: generalizing the double Dixie cup problem of Newman and Shepp”, ESAIM Probab. Statist., 20 (2016), 367–399 | DOI | MR | Zbl

[12] R. Durrett, Probability: theory and examples, Duxbury Advanced Series, 3rd ed., Thompson Brooks/Cole, Belmont, CA, 2005, xi+497 pp. | MR | Zbl

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

[14] W. Feller, An introduction to probability theory and its applications, v. 1, 3rd ed., John Wiley Sons, Inc., New York–London–Sydney, 1968, xviii+509 pp. | MR | MR | Zbl | Zbl

[15] D. Foata, Guo-Niu Han, B. Lass, “Les nombres hyperharmoniques et la fratrie du collectionneur de vignettes”, Sém. Lothar. Combin., 47 (2001/02), B47a, 20 pp. | MR | Zbl

[16] D. Foata, D. Zeilberger, “The collector's brotherhood problem using the Newman–Shepp symbolic method”, Algebra Universalis, 49:4 (2003), 387–395 | DOI | MR | Zbl

[17] H. J. Godwin, “On cartophily and motor cars”, Math. Gaz., 33:305 (1949), 169–171 | DOI | Zbl

[18] G. H. Hardy, E. M. Write, An introduction to the theory of numbers, 4th ed., Clarendon Press, Oxford, 1960, xvi+421 pp. | MR | Zbl

[19] L. Holst, “On birthday, collectors', occupancy and other classical urn problems”, Internat. Statist. Rev., 54:1 (1986), 15–27 | DOI | MR | Zbl

[20] F. G. Maunsell, “A problem in cartophily”, Math. Gaz., 22:251 (1938), 328–331 | DOI | Zbl

[21] P. Neal, “The generalized coupon collector problem”, J. Appl. Probab., 45:3 (2008), 621–629 | DOI | MR | Zbl

[22] D. J. Newman, L. Shepp, “The double Dixie Cup problem”, Amer. Math. Monthly, 67 (1960), 58–61 | DOI | MR | Zbl

[23] N. Pintacuda, “Coupons collectors via the martingales”, Boll. Un. Mat. Ital. A (5), 17:1 (1980), 174–177 | MR | Zbl

[24] S. M. Ross, Introduction to probability models, 9th ed., Academic Press, Amsterdam, 2006, xviii+782 pp. | MR | Zbl

[25] W. Rudin, Real and complex analysis, 3rd ed., McGraw-Hill Book Co., New York, 1987, xiv+416 pp. | MR | Zbl

[26] The Dixie Cup company history http://sites.lafayette.edu/dixiecollection/company-history/

[27] Simulation of GCCP (uniform, linear and Zipf) http://www.math.ntua.gr/~papanico/