The multiple coupon collector problem
I've written about the Coupon Collector Problem and variations several times, most recently here.
Brian Beckman left a comment linking to an article he wrote, which in turn links to a paper on the Double Dixie Cup Problem[1].
The idea behind the Coupon Collector Problem is to estimate how long it will take to obtain at least one of each ofn coupons when drawing coupons at random with replacement from a set ofn.
The Double Dixie Cup Problem replaces coupons with dixie cups, and it asks how many couples you'd expect to need to collect until you havetwo of each cup.
The authors in [1] answer the more general question of how long to collectm of each cup, som = 1 reduces to the Coupon Collector Problem. The punchline is Theorem 2 from the paper: the expected number of cups (or coupons) is
for fixed m as n .
Here Cm is a constant that depends on m (but not on n) and o(1) is a term that goes to zero as n .
Since log log n is much smaller than log n when n is large, this says that collecting multiples of each coupon doesn't take much longer, on average, than collecting one of each coupon. It takes substantially less time than playing the original coupon collector gamem times.
Related posts[1] Donald J. Newman and Lawrence Shepp. The Double Dixie Cup Problem. The American Mathematical Monthly, Vol. 67, No. 1 (Jan., 1960), pp. 58-61.
The post The multiple coupon collector problem first appeared on John D. Cook.