I'm trying to wrap my head around the nuances of probability and tried to solve the coupon collector problem https://en.wikipedia.org/wiki/Coupon_collector%27s_problem using the following recursive solution. Although i understood the correct solution:- http://www.cs.tufts.edu/comp/250P/classpages/coupon.html , for the life of me I'm unable to figure out what is wrong here.
Consider N coupons to be collected. It is clear that if it takes some number of collections to get all tickets, the last ticket collected has to be a unique one. Let the last coupon collected be x$$1\le x \le N$$ Now to collect N-1 other coupons we need E(N-1) number of collections. Also the exp. number of trials to get x after this is N. This means that total number of collections required is E(N-1)+N. Now, the number of ways x can be chosen is N and each way is equally likely, so the recurrence becomes:- $$E(N) = N*(E(N-1) + N)/N$$ $$=E(N-1) + N$$
I understand it might be very trivial an error, but I would appreciate some explanation.
The error is hiding in your definition of $E(N)$. When you use $E(N)$ it is the expected time to get $N$ coupons given a population of $N$. In your recurrence, when you use $E(N-1)$ it is the expected time to get $N-1$ coupons given a population of $N$, which is the way the published solutions use it. This is correct. You don't say what your problem is, but I suspect you are using it as the expected time to get $N-1$ coupons out of a population of $N-1$. That will lead to a quadratic increase in the expected time instead of $N \log N$ increase.