The Generalised Coupon Collector Problem

Coupons are collected one at a time from a population containingndistinct types of coupon. The process is repeated until allncoupons have been collected and the total number of draws,Y, from the population is recorded. It is assumed that the draws from the population are independent and identically distributed (draws with replacement) according to a probability distributionXwith the probability that a type-icoupon is drawn being P(X=i). The special case where each type of coupon is equally likely to be drawn from the population is the classic coupon collector problem. We consider the asymptotic distributionY(appropriately normalized) as the number of couponsn→ ∞ under general assumptions upon the asymptotic distribution ofX. The results are proved by studying the total number of coupons,W(t), not collected intdraws from the population and noting that P(Y≤t) = P(W(t) = 0). Two normalizations ofYare considered, the choice of normalization depending upon whether or not a suitable Poisson limit exists forW(t). Finally, extensions to theK-coupon collector problem and the birthday problem are given.