# 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, 2013 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? Jan 26, 2013 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. Jan 26, 2013 at 3:47
• As @MikeSpivey said.
– Did
Jan 26, 2013 at 5:05

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}$$.

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. Jan 26, 2013 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. Jan 26, 2013 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. Jan 26, 2013 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. Jan 26, 2013 at 2:00

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$

I wanted to use recursion to solve this problem at first too. That's a little tricky though since once you get a new coupon, the problem doesn't really start over in the same way since the probability of getting the next new coupon is lower.

An easier way to solve this is to let $Y = 1+X_2+X_3 +\ldots + X_{10}$, where $X_i$ is the number of times it takes from receiving the $i-1^{th}$ new coupon to to the next new coupon. The probability of seeing the $i^{th}$ new coupon is the number of coupons not yet seen over the total number of coupons: $[10-(i-1)]/10$.

Notice that $$X_2,X_3, \ldots, X_{10} \sim Geom\left(\frac{10-(i-1)}{10}\right),$$ where $X_2,X_3, \ldots, X_{10}$ are independent. Since for $X\sim Geom(p)$, $E[X] = 1/p$, the expected number of times it takes to see all coupons is thus: \begin{align}E[Y] &= 1+E[X_2]+E[X_3] +\ldots + E[X_{10}]\\ &=1 +\frac{10}{9}+\frac{10}{8}+\ldots+\frac{10}{2}+10. \end{align}