Coupon Collecting Problem: $4$ coupons with $p_1 = p_2 = \frac{1}{8}$ and $p_3 = p_4 = \frac{3}{8}$

Question

This is from Ross.

I know how to solve everything but (d).

The book answer is $\frac{123}{35}$.

There are $4$ different types of coupons, the first $2$ of which compose one group and the second $2$ another group. Each new coupon obtained is type $i$ with probability $p_i$, where $p_1 = p_2 = 1/8$ and $p_3 = p_4 = 3/8$. Find the expected number of coupons that one must obtain to have at least one of

(a) all 4 types; (b) all the types of the first group; (c) all the types of the second group;

(d) all the types of either group.

My attempt

Let $X =$ number of coupons needed to collect all the types of either group.

Let's number the coupons $1$ through $4$ where $1$ and $2$ are part of the first group and $3$ and $4$ are part of the second. Let's say that the notation $4132$ represents the order of newest types seen. For example if you observe $44111332$ then the order of newest types seen was $4132$.

To get the $E[X]$ I'll condition on every arrangements where the game stops once you have all the types of either group.

$$E[X] = E[X \mid 12]P(12) + E[X \mid 132]P(132) + E[X \mid 134]P(134) + E[X \mid 142]P(142) + E[X \mid 143]P(143) + E[X \mid 21]P(21) + E[X \mid 231]P(231) + E[X \mid 234]P(234) + E[X \mid 241]P(241) + E[X \mid 243]P(243) + E[X \mid 312]P(312) + E[X \mid 314]P(314) + E[X \mid 321]P(321) + E[X \mid 324]P(324) + E[X \mid 34]P(34) + E[X \mid 412]P(412) + E[X \mid 413]P(413) + E[X \mid 421]P(421) + E[X \mid 423]P(423) + E[X \mid 43]P(43)$$

For example to get the first term, $E[X \mid 12] = 1 + \frac{2}{1}$ where the logic is given that you know the coupon types will appear as $12$, the number of coupons needed to get $1$ must be one and then to get $2$ it's the expected value of a geometric RV with $p=\frac{1/8}{1/8+1/8} = \frac{1}{2}$.

To get $P(12)$ we use the multiplication rule. $P(12) = P(1) P(1 \mid 2) = \frac{1}{8} \frac{1}{7} = \frac{1}{56}$. So $E[X \mid 12]P(12) = (1 + \frac{2}{1}) \frac{1}{56}$.

To get the second term, $E[X \mid 132] = 1 + \frac{4}{3} + \frac{4}{1}$ where you know the number of coupons needed to collect $1$ and $2$ is one and to get the middle it's a geometric RV with $p = \frac{3/8}{3/8+1/8} = 3/4$.

To get $P(132) = P(1) P(3 \mid 1) P(2 \mid 13) = \frac{1}{8} \frac{3}{7} \frac{1}{4}$.

Next put it in a python script and get the answer.

Unfortunately I get $3.4 \neq \frac{123}{35} = 3.51428$.

My questions

Can you point out where I'm going wrong? Also, what is the more elegant approach? Thanks.

Answer 1

I would say there are five states, $a,b,c,d,e$, where $a$ has no coupons, $b$ has one coupon from group $1$ and none from group $2$, $c$ has one coupon from group $2$ and none from group $1$, $d$ has one coupon from each group, and $e$ has two coupons from one group and is final.

If you are in state $d$ you finish with probability $\frac 12$ so the expected number of draws from $d$ is $2$.

If you are in state $c$ you finish with probability $\frac 38$, go to $d$ with probability $\frac 14$ and stay in $c$ with probability $\frac 38$. The expected number of draws from $c$ is $$E(c)=1\cdot \frac38 + (1+E(d))\cdot \frac14 +(1+E(c))\cdot \frac 38\\ \frac 58E(c)=\frac 32\\E(c)=\frac {12}5$$ If you are in state $b$ you finish with probability $\frac 18$, go to $d$ with probability $\frac 34$ and stay in $b$ with probability $\frac 18$. The expected number of draws from $b$ is $$E(b)=1\cdot \frac 18+(1+E(d))\cdot \frac 34+(1+E(b))\frac 18\\ \frac 78E(b)=\frac 52\\E(b)=\frac {20}7$$ Finally from $a$ you go to $b$ with probability $\frac 14$ and to $c$ with probability $\frac 34$ so $$E(a)=(1+E(b))\frac 14+(1+E(c))\frac 34\\=\frac {27}{28}+\frac {51}{20}\\=\frac {123}{35}\approx 3.514$$

Answer 2

Let $N_1$, $N_2$, $N_\land$ and $N_\lor$ denote the numbers of coupons you need to draw to get all types of the first group, of the second group, of both groups and of either group, respectively. Then

\begin{eqnarray*} \mathsf E[N_\lor] &=& \sum_{n=0}^\infty\mathsf P(N_\lor\gt n) \\ &=& \sum_{n=0}^\infty\mathsf P(N_1\gt n\land N_2\gt n) \\ &=& \sum_{n=0}^\infty\left(\mathsf P(N_1\gt n)+\mathsf P(N_2\gt n)-\mathsf P(N_1\gt n\lor N_2\gt n)\right) \\ &=& \sum_{n=0}^\infty\left(\mathsf P(N_1\gt n)+\mathsf P(N_2\gt n)-\mathsf P(N_\land\gt n)\right) \\ &=& \mathsf E[N_1]+\mathsf E[N_2]-\mathsf E[N_\land]\;. \end{eqnarray*}

These are the results of parts (a) through (c) that you've already solved; the result is

$$\mathsf E[N_\lor]=12+4-\frac{437}{35}=\frac{123}{35}\;.$$