Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Query about Linearity of Expectation — Coupon collector problem

Revision en1, by vntshh, 2018-07-11 22:22:53

I was recently solving some problems on Linearity of Expectation. I was trying to solve the Coupon collector problem. The problem is: Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once? This is how I tried to solve the problem:

E[Number of coupons needed to draw so that each coupon comes atleast once]

E[Number of coupons drawn till i'th coupon is drawn for the first time]

This comes from the Linearity of Expectation (Link) since independency or dependency of events does not matter.

Now, let E[Number of coupons drawn till i'th coupon is drawn for the first time] = x

This can be solved by applying the following recursive equation,

x = 1 + ((n - 1) / n) * x

On solving, we get x = n.

Thus, E[Number of coupons needed to draw so that each coupon comes atleast once]  = n2

I know that I am wrong somewhere since the answer is n * Hn, but I don't know where exactly does it go wrong. I have discussed this with my friend kr_abhinav, but we couldn't find the mistake in the proof as well.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English vntshh 2018-07-11 22:22:53 1353 Initial revision (published)