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?

Hint

Linearity of expectation

Solution

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.

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.

Source: Quant Interview

Enable Like and Comment Latest solved Puzzles

Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level

© BRAINSTELLAR |