The siblings of the coupon collector

A. V. Doumas ; V. G. Papanicolaou

Teoriâ veroâtnostej i ee primeneniâ, Tome 62 (2017) no. 3, pp. 556-586

Résumé

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]$.

Détail

Keywords: urn problems, generalized coupon collector's problem (GCCP), hyperharmonic numbers, Lambert series, generalized Zipf law.