The coupon collector’s problem describes the following question: there are n different types of coupons and the collector will receive a random coupon every time, what is the expected trials that the collector can collect all n types of coupons? We can conclude that the expected trails grows as O(nlog⁡n).

The Distribution of Trails for a new Coupon

Let T be the time to collect all n types of coupons, and ti be the time to collect a new coupon after i−1 coupons have been collected. We can see that the probability of ti satisfies geometric distribution with pi=n−(i−1)n, then we conclude

We also obviously know that ti and tj are independent. Thus

The variance of the random variable T can be calculated as (since ti are independent)

A classical puzzle that can be modeled as Coupon Collector’s problem is that, for a cubic dice, we are expected to get all six points after how many trails? The answer for the question should be

Generalization

The Coupon Collector’s Problem has been generalized as the expected trails of collect m copy of each n coupons. When m=2, the problem is also called The Double Dixie Cup Problem1. The expectation of Tm satisfies

In the more general case, when pi is nonuniform, Philippe Flajolet gives2

If the collector receives d coupons each run3, in the asymptotic case the m copy of of each n coupons will be collected expected within time

The Coupon Collector’s Problem can also be generalized as stochastic process456. The paper from MAT7 also gives exhaustive analysis of this problem. The expectation can also be expressed using the Stirling numbers89.

References