0

Suppose we have $3$ different types of coupons $C_1,C_2,C_3$, and the probability we draw each coupon is $p_1,p_2$ and $p_3$ for $C_1,C_2$ and $C_3$ accordingly. How many times in average will we have to draw until we get a coupon of each type?

I said the following: Observe the last coupon drawn. With probability $p_1$ it is $C_1$. Now observe the first coupon drawn, it must be different than $C_1$ since otherwise the trial wouldn't have ended. With probability $p_2$ it was $C_2$, and in the middle we would've needed to draw $C_3$ once, and for that to happen we would need $\frac{1}{p_3}$ draws. Doing the same logic for all possibilities of last coupon drawn, we get that the average number of draws is:

$p_1 \cdot (1 + p_2 \cdot (1 + \frac{1}{p_3})) + p_1 \cdot (1 + p_3 \cdot (1 + \frac{1}{p_2})) + p_2 \cdot (1 + p_3 \cdot (1 + \frac{1}{p_1})) + p_2 \cdot (1 + p_1 \cdot (1 + \frac{1}{p_3})) + p_3 \cdot (1 + p_1 \cdot (1 + \frac{1}{p_2})) + p_3 \cdot (1 + p_2 \cdot (1 + \frac{1}{p_1}))$

However, I feel that something is off with this. Any guidance towards whether this is correct or where a mistake has been made?

TheNotMe
  • 4,841
  • Why is the probability that $C_1$ is drawn last equal to $p_1$? If $p_1$ is very near $1$ then it is highly unlikely that $C_1$ is drawn last. – lulu Jan 14 '18 at 21:50
  • I'd do it with states. Index the states according to which coupons have been seen. Thus $S[1,3]$ refers to the state in which $C_1,C_3$ have been seen (and $C_2$ has not). Then proceed by backwards induction. – lulu Jan 14 '18 at 21:52
  • You're right. That doesn't make sense. However, I still have no intuition regarding the way you suggest. Care to explain more? – TheNotMe Jan 14 '18 at 22:02
  • It's more a matter of computation then of intuition. If you are in $S[1,3]$ then you expect $\frac 1{p_2}$ trials before you are done. Similarly for $S[1,2],S[2,3]$. Now, the answer $E=E[\emptyset]=\sum p_i\times (E[i]+1)$ so all you need to do is to compute $E[1],E[2],E[3]$ (where, of course, $E[1]$ denotes the expectation from $S[1]$ and so on). – lulu Jan 14 '18 at 22:08
  • This is a very standard technique so it is worth your spending some time on it. Just focus on the transitions. $S[1]$ can only move to $S[1,2]$ or $S[1,3]$ (or stay in $S[1]$). What is the probability that it moves to $S[1,2]$? – lulu Jan 14 '18 at 22:09
  • Probability that $S[1]$ moves to $S[1,2]$ is the probability that we have drawn coupon $1$ any number of times after the first one and then have drawn coupon $2$, ie $p_1^{k} \cdot p_2$ for some $0 \leq k < \infty$ – TheNotMe Jan 15 '18 at 09:50
  • Well, no. The probability of that transition can't be a function of an unknown parameter like $k$. Think of it this way: If you are in $S[1]$ then drawing $C_1$ is irrelevant...the only relevant moves are drawing $C_2$ or $C_3$. So, ignore $C_1$ and focus on the the $p_2+p_3$ probability that you don't draw $C_1$. Of that, $p_2$ is explained by $C_2$ so the answer is $\frac {p_2}{p_2+p_3}$. – lulu Jan 15 '18 at 11:32
  • An another way to see it: Let $P$ denote the answer. Say you are in $S[1]$ and you draw a coupon. Three things can happen, according to which coupon you draw. If you get $C_2$ you win. If you get $C_3$ you lose. If you get $C_1$ you play again. Thus $P=p_2\times 1 +p_3\times 0+p_1\times P\implies (1-p_1)P=p_2\implies P=\frac {p_2}{1-p_1}=\frac {p_2}{p_2+p_3}$. – lulu Jan 15 '18 at 11:36
  • The idea behind the backwards induction I am proposing to solve your original problem is similar. I already computed the expected number from states like $S[1,2]$ (it is just $\frac 1{p_3}$). Let's get $E[1]$, the expected number from $S[1]$. Again, say you are in $S[1]$ and you draw a coupon. three things can happen and we see that $E[1]=p_1(E[1]+1)+p_2(E[1,2]+1)+p_3(E[1,3]+1)$. Recursively, the only unknown there is $E[1]$ so you can solve for it. – lulu Jan 15 '18 at 11:49

1 Answers1

1

This solution steps through the process from beginning to end. As noted in the comments, you can also approach this recursively. The recursive approach is laid out here.

Definitions:

S[0] = starting point

S[1,2,3] = ending point

S[x,y] = state of having Cx and Cy, order you got there doesn't matter

Level 0 = S[0]

$L_1$ = S[1], S[2], and S[3]

$L_2$ = S[1,2], S[1,3], and S[2,3]

$L_3$ = S[1,2,3]

$E_x(L_y)$ = Expected number of steps to get from $L_x$ to $L_y$

Solution:

$E_0(L_1) = 1$

$E_1(L_2) = \frac{p1}{1-p1} + \frac{p2}{1-p2} + \frac{p3}{1-p3}$ (each term is probability times expected wait time)

If exiting S[1] the possible expected wait times at next level are:

$\frac1{p2}$ with probability $\frac{p3}{p2+p3} = \frac{p3}{1-p1}$ if you step to S[1,3], and

$\frac{1}{p3}$ with probability $\frac{p2}{p2+p3} = \frac{p2}{1-p1}$ if you step to S[1,2]

Similarly for exiting S[2] and S[3].

Weighting the three possible $\frac1{p_x}$ $L_2$ to $L_3$ waiting times by the ways of getting to the various S[x,y]

$$\begin{align} E_2(L_3) &= \frac1{p_1} \cdot ({p_2}\cdot \frac{p_3}{1-p_2} + {p_3}\cdot \frac{p_2}{1-p_3}) \\&+ \frac1{p_2} \cdot ({p_1}\cdot \frac{p_3}{1-p1} + {p_3}\cdot \frac{p_1}{1-p_3}) \\&+ \frac1{p_3} \cdot ({p_1}\cdot \frac{p_2}{1-p_1} + {p_2}\cdot \frac{p_1}{1-p_2}) \end{align} $$

Combining all $E_x(L_y)$ above gives

$$\begin{align}E_0(L_3) &= E_0(L_1) + E_1(L_2) + E_2(L_3) \\&=1 + \frac{p_1}{1-p_1} + \frac{p_2}{1-p_2} + \frac{p_3}{1-p_3} \\&+ \frac1{p_1} \cdot ({p_2}\cdot \frac{p_3}{1-p_2} + {p_3}\cdot \frac{p_2}{1-p_3}) \\&+ \frac1{p_2} \cdot ({p_1}\cdot \frac{p_3}{1-p_1} + {p_3}\cdot \frac{p_1}{1-p_3}) \\&+ \frac1{p_3} \cdot ({p_1}\cdot \frac{p_2}{1-p_1} + {p_2}\cdot \frac{p_1}{1-p_2}) \\&= 1+\frac{p_1}{1-p_1}\cdot(1 +\frac{p_2}{p_3} + \frac{p_3}{p_2}) + \frac{p_2}{1-p_2}\cdot(1 +\frac{p_1}{p_3} + \frac{p_3}{p_1}) + \frac{p_3}{1-p_3}\cdot(1 +\frac{p1}{p_2} +\frac{p_2}{p1}) \end{align}$$

For $p_1=p_2=p_3=0.33$ the result is 5.5

GHx
  • 171