Coupon collecting

Coupon collecting is a classical homework problem in undergraduate probability. Suppose there exist different types of coupons. At each time one selects a coupon of a uniformly random type. In expectation, how many coupons does one need to collect before one has at least one coupon of every type? The analogous problem of throwing balls in bins is similar: suppose there were bins and one threw balls uniformly randomly into the bins. How many balls would one throw, in expectation, before all the bins were filled?

By the pigeonhole principle one would have to collect at least coupons, but this is not enough. With probability one would get at least one overlap and thus, at least one bin would be empty. If is the (random) number of coupons required to cover all the types, then the task is to find .

It is useful to approach this in an inductive fashion: assume that types have already been collected. Since the number of selections required to get a new type is a geometric random variable of success probability . Thus, in expectation, one needs tries to get a new type after collecting types. This yields that, starting from nothing, one needs tries in expectation, where denotes the harmonic sum upto . This number is roughly yielding that .

More interesting forms of “coupon-collecting” type questions are, say, the number of tries are needed to obtain a coupon of each type with high probability (and not just in expectation). Or, assuming one collected coupons u.a.r as before, what would be the rough size of the coupon type with maximum collection. It is interesting how relatively simple problems arise in unexpected places. I started this post after noting that the same “coupon collector” effect yields a lower bound of randomly sampled entries to recover a rank matrix of size (as proved Tao and Candes’ paper on low rank matrix recovery).