Asymptotics and Limit Distributions for the Generalized Double Dixie Cup Problem

Aristides V. Doumas, Vassilis G. Papanicolaou

Published 2014-12-11Version 1

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}(N)$ of coupons that a collector has to buy in order to complete $m$ sets of all $N$ existing different coupons. 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. We first give explicit formulas for the moments and the moment generating function of the random variable $T_{m}(N)$. Then, we develop techniques of computing the asymptotics of the first and the second moment of $T_{m}(N)$ as the number $N$ of different coupons becomes arbitrarily large (our techniques apply to the higher moments of $T_{m}(N)$ too). From these asymptotics we obtain the leading behavior of the variance $V[\,T_{m}(N)\,]$ of $T_{m}(N)$ as $N\rightarrow \infty$. Finally, the aforementioned formulas are used to obtain the limit distribution of the random variable $T_{m}(N)$ for large classes of coupon probabilities. As it turns out, in many cases $T_{m}(N)$ (appropriately normalized) converges in distribution to a random variable $Y$ with (cumulative) distribution function $\exp(-e^{-y}/(m-1)!)$ (which reduces to the standard Gumbel distribution in the case where $m = 1$ or $m = 2$). This is a generalization of a well-known result of P. Erd\H{o}s and A. R\'{e}nyi [Magyar. Tud. Akad. Mat. Kutat\'{o} Int. K\"{o}zl. 6 (1961), 215-220] regarding the limit distribution of $T_{m}(N)$ in the case of equal coupon probabilities. The present paper extends an earlier work of ours [Adv. Appl. Prob. 44 (1) (2012), 166-195], which dealt only with the case $m = 1$.