| hard | probability |
A soda company is holding a contest where everyone who collects one each of N different coupons wins some prize. You get a coupon with each purchase of a soda, and each coupon is equally likely. What’s the expected number of soda bottles you have to buy in order to collect all the coupons?
Linearity of expectation
Divide the whole process in to stages. Each stage ends with collecting a coupon which is new ( different from the coupons we already have )
Let C_i be the random variable which denotes the number of coupons we buy in the stage i.
Let C be the random variable which denotes the number of coupons we buy in order to get all n coupons Now, C= C_1 + C_2 + ... + C_n Note C_1 = 1; In general, while we are during stage i , we already have with us (i-1) different coupons. So, the probability of getting a new coupon is p_i = n-(i-1)/n. Also note that each C_i is a Geometrically distributed random variable with success probability equal to p_i. So, E(C_i) = 1/p_i = n/(n-i+1). By using Linearity of Expectations, E(C) = E(C_1) +E(C_2) + ...+E(C_n) = n(1/n + 1/(n-1)+ ... +1) ~ nlogn.