Volume 20, 2016
|Page(s)||367 - 399|
|Published online||23 November 2016|
The coupon collector’s problem revisited: generalizing the double Dixie cup problem of Newman and Shepp
Revised: 1 June 2016
Accepted: 8 June 2016
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 Tm(N) of coupons that a collector has to buy in order to complete m sets of all N existing different coupons. More precisely, the problem is to determine the asymptotics of the expectation (and the variance) of Tm(N), as well as its limit distribution, as the number N of different coupons becomes arbitrarily large. 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. In the beginning of the article we give a brief review of the formulas for the moments and the moment generating function of the random variable Tm(N). Then, we develop techniques of computing the asymptotics of the first and the second moment of Tm(N) (our techniques apply to the higher moments of Tm(N) as well). From these asymptotic formulas we obtain the leading behavior of the variance V [ Tm(N) ] as N → ∞. Finally, based on the asymptotics of E [ Tm(N) ] and V [ Tm(N) ] we obtain the limit distribution of the random variable Tm(N) for large classes of coupon probabilities. As it turns out, in many cases, albeit not always, Tm(N) (appropriately normalized) converges in distribution to a Gumbel random variable. Our results on the limit distribution of Tm(N) generalize a well-known result of [P. Erdős and A. Rényi, Magyar. Tud. Akad. Mat. Kutató Int. Közl. 6 (1961) 215–220] regarding the limit distribution of Tm(N) for the case of equal coupon probabilities.
Mathematics Subject Classification: 60F05 / 60F99
Key words: Urn problems / coupon collector’s problem / double Dixie cup problem / rising moments / limit distribution / Gumbel distribution / generalized Zipf law
© EDP Sciences, SMAI 2016
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.