Using Recursion to Solve Coupon Collector

I read a brilliant answer by Mike Spivey on one of the questions and I was wondering how I could use it to solve a coupon collectors problem.

The problem is : There are coupons labelled 1,2,3...,10 how many coupons do I need to collect in order to have one of each labels. I know that the answer is $\displaystyle \sum_{i=1}^{10} \dfrac{10}{i}$

Here is my attempt : Let $X_i$ be the random variable corresponding to the number of coupons needed to be collected to have exactly $i$ unique labels.

\begin{align} E(X_1)&=1\\ E(X_2|X_1)&=\dfrac{9}{10}.(X_1+1)+\dfrac{1}{10}.(E(X_2))\\ \implies E(X_2)&=\dfrac{9}{10}.(E(X_1)+1)+\dfrac{1}{10}.(E(X_2))\\ \text{Similarly,}\\ E(X_3)&=\dfrac{8}{10}.(E(X_2)+1)+\dfrac{2}{10}.(E(X_3))\\ \vdots \end{align} But this gives me the wrong answer. I know that there is a problem in my second equation but don't know why. My logic was as follows: Assuming I know how much it takes to get 1 coupon $(E(X_1))$ with probability 9/10 I find 2 in $E(X_1)+1$ else, I just have $E(X_2)$.

Neither does the formula in the aforementioned question work. Can someone help me set up the recursion equation?

(If possible, please retain my Random Variables. I am more interesting in knowing why my logic is failing in designing the recursion than answering the original question)


Let $W_1$ be the "waiting time" (number of purchases) until the first coupon, let $W_2$ be the waiting time between the first coupon and the second, and so on up to $W_{10}$. Then we will collect $X=W_1+W_2+\cdots +W_{10}$ coupons by the time we have them all.

We want $E(X)=E(W_1)+E(W_2)+\cdots +E(W_{10})$.

$W_1$ is very simple, it is $1$ with probability $1$, so has expectation $1$.

After we have $i$ different coupons, the probability that a coupon we get is new is $\frac{10-i}{10}$. So $W_{i+1}$ is a geometrically distributed random variable with probability of success $p=\frac{10-i}{10}$. Such a geometric random variable has mean $\frac{1}{p}=\frac{10}{10-i}$.

Now add up.

The above analysis can be set up as a recurrence. Let $X_i$ be the time until the $i$-th (new) coupon. Then $X_{i+1}=X_i+W_{i+1}$ where $W_j$ is as in the discussion above. We have $$E(X_{i+1})=E(X_i)+E(W_{i+1})=E(X_i)+\frac{10}{10-i}.$$


To follow your approach, you need to note that if you fail on the second coupon because it matches the first, you are not at the beginning but at the point you already have one. This says your second equation should be $E(X_2)-E(X_1)=\frac 9{10}\cdot 1 + \frac 1{10}(1+E(X_2)-E(X_1))$. The first term comes from success on the next coupon and the second says that with chance $\frac 1{10}$ you draw one and are back where you started. The fact that $E(X_2)-E(X_1)$ is the same as André Nicolas $W_2$ shows the parallel between these approaches. This yields $\frac 9{10}(E(X_2)-E(X_1))=1$ or $E(X_2)=\frac {20}9$