Coupon collector problem: why does not this solution work?

51 Views Asked by At

Problem:

Suppose your favourite brand of cereals is having a competition, where in each box of cereals there is a coupon with a positive integer number between 1 and $N$, and you win a prize if you collect coupons with all numbers between 1 and $N$. How many boxes do you need to buy on average in order to win, i.e. collect all the coupons?

My solution:

Let's set the case for $N = 4$, as an example.

The expected value $E$ can be given by a sum of terms:

$(4\frac{1}{4}\frac{3}{4}\frac{2}{4}\frac{1}{4})4$, basically in the parenthesis you have the probability of taking the first one, probability is one, then a second different one, a third different one, and the last one.

$(4\frac{1}{4}\frac{3}{4}\frac{2}{4}\frac{3}{4})(E+3)$, basically here you pick one of the first three you already picked, so you get $E+3$

$(4\frac{1}{4}\frac{3}{4}\frac{2}{4})(E+2)$, here you pick one of the first two you already picked, so you get $E+2$

$(4\frac{1}{4}\frac{1}{4})(E+1)$, here you pick the same first one you have already picked up, so you get $E+1$

So, in the end

$E = (4\frac{1}{4}\frac{3}{4}\frac{2}{4}\frac{1}{4})4 + \\ (4\frac{1}{4}\frac{3}{4}\frac{2}{4}\frac{3}{4})(E+3) + \\ (4\frac{1}{4}\frac{3}{4}\frac{2}{4})(E+2) + \\ (4\frac{1}{4}\frac{1}{4})(E+1)$

And this gives me $E = 142/6$, different from the standard solution (and it is also a non integer number).

Did I miss some case? Where is wrong my reasoning here?