TOPICS
Search

Coupon Collector's Problem


The coupon collector's problem asks for the number of independent and identically distributed draws needed to observe every one of n types of object, where n is a positive integer. On each draw, type i has probability p_i>=0, with

 sum_(i=1)^np_i=1.

The collection time is the first draw at which all types have appeared. If any p_i=0, this time is infinite. For the discrete uniform distribution, p_i=1/n, and the expectation value of the collection time is nH_n, where H_n is a harmonic number.

For repeated complete collections, let T_(n,m) be the number of independent uniform draws required until each of the n types has appeared at least m times. Castro and Marinho (2026) determined a Gumbel distribution limit as m=m(n)->infty. Let F_m be the distribution function of the gamma distribution with shape m and scale 1, and set t_(n,m)=nF_m^(-1)(1-1/n). If m/lnn tends to 0, a finite positive value alpha, or infinity, respectively, the window w_(n,m) is n, nW/(W+1) with W=W_(-1)(-e^(-1-1/alpha)), or nW/(W+1) with W=W_(-1)(-e^(-1-lnn/m)). Here W_(-1) is the negative real branch of the Lambert W-function. For every real theta,

 lim_(n->infty)Pr(T_(n,m)<=t_(n,m)+thetaw_(n,m))=exp(-e^(-theta)),

and ET_(n,m)=t_(n,m)+gammaw_(n,m)+o(w_(n,m)), where gamma is the Euler-Mascheroni constant (Castro and Marinho 2026).


See also

Birthday Problem, Complete Set

Explore with Wolfram|Alpha

References

Castro, M. E. and Marinho, R. "Cutoff Profile for the Coupon Collector with Many Collections." 23 Oct 2026. https://arxiv.org/abs/2610.33199.Havil, J. "Collecting a Complete Set." §13.9 in Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, pp. 130-131, 2003.Hildebrand, M. V. "The Birthday Problem." Amer. Math. Monthly 100, 643, 1993.Numberphile. "The Math (and Money) of Soccer Stickers." Apr. 26, 2018. https://www.youtube.com/watch?v=aKPkQCys86c.

Referenced on Wolfram|Alpha

Coupon Collector's Problem

Cite this as:

Weisstein, Eric W. "Coupon Collector's Problem." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CouponCollectorsProblem.html

Subject classifications