Problem: Suppose that each box of cereal contains one of n different coupons. Once you obtain one of every type of coupon, you can send in for a prize. Question: How many boxes of cereal must you buy before obtaining at least one of every type of coupon. Let X be the number of boxes bought until at least one of every type of coupon is obtained. E[X] = nH(n) = nlnn | Probability for Computing LECTURE 5 MORE APPLICATION PROBABILISTIC ANALYSIS BIN 2010 Quoc Le Van Nguyen WITH AND BALLS Agenda Review Coupon Collector s problem and Packet Sampling Analysis of Quick-Sort Birthday Paradox and applications The Bins and Balls Model 2010 Quoc Le Van Nguyen Probability for Computing 2 Coupon Collector Problem Problem Suppose that each box of cereal contains one of n different coupons. Once you obtain one of every type of coupon you can send in for a prize. Question How many boxes of cereal must you buy before obtaining at least one of every type of coupon. Let X be the number of boxes bought until at least one of every type of coupon is obtained. E X nH n nlnn 2010 Quoc Le Van Nguyen Probability for Computing