# 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)

-
I do not understand the last term in the identity for $E(X_2\mid X_1)$. – Did Jan 26 '13 at 3:02
@Did Its like 9/10 times I will finish in the next attempt and 1/10 I will have to simply "start again". I feel that term is wrong, any recommendations? – Inquest Jan 26 '13 at 3:42
@Inquest: But you still have the first coupon, so you're not starting again. (That's the difference with my answer you mention, where getting a tail does force you to start the process of achieving $n$ consecutive heads all over again from the beginning.) As far as constructing a recurrence for the coupon collector problem, I would do it like André does. – Mike Spivey Jan 26 '13 at 3:47
As @MikeSpivey said. – Did Jan 26 '13 at 5:05

## 2 Answers

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$

-

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}{i}$. So $W_{i+1}$ is a geometrically distributed random variable with probability of success $p=\frac{10-i}{i}$. 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}.$$

-
Is there any way to do this using recursion without changing how I have defined my Random variables? I really want to see why my logic is failing. – Inquest Jan 26 '13 at 1:21
The material towards the end has a recurrence. One could reword it using conditional expectation. To me the logic is a little clearer written the way I did. – André Nicolas Jan 26 '13 at 1:33
I gave it some thought and this is brilliant Andre. How do you design your RVs when you encounter a problem? I feel for me that's what leads to failure. – Inquest Jan 26 '13 at 1:52
Hard to answer your question, have done this for so long that the process is a hybrid of thinking and remembering, usually more remembering than thinking. For expectations, expressing our random variable as a sum is often decisive. The linearity of expectation often lets us bypass painful detailed analysis of probabilities. – André Nicolas Jan 26 '13 at 2:00