expected number of balls in a box at the end of a game where balls of the same color are removed until all six distinct colors are on the table

Question

Imagine you have an empty box and an enormous bag filled with glass balls, each of them in one of six different colors distributed uniformly. You decide to play a game: you start by drawing a ball from the bag and placing it on the table. Then, you continue drawing balls one by one. If you draw a ball that has the same color as one already on the table, you put both balls into the box. Otherwise, you add the ball to the ones on the table, keeping the colors distinct. The game continues until you have balls of all six different colors on the table. At this point, the game ends. Now, the question is: what is the expected number of glass balls in the box when the game ends?

I initially considered the coupon collector's problem as a starting point for this particular problem, but I'm unsure whether this approach is appropriate or how to continue from here. Can someone offer insights or alternative methods for solving the problem?

Answer 1

We can consider this as a specific example of a non-uniform 1D random walk, where the only transitions allowed out of state $n \in \{0,1,2,3,\ldots\}$ are forward (to state $n+1$) with probability $p_n$, or backward (to state $n-1$) with probability $1-p_n$. (We must have $p_0=1$.) Let $T_{n}$ be the expected number of steps to reach state $n \ge 1$ starting at state $n-1$. Clearly $T_1=1$. More generally, once you're at state $n-1$, you either proceed directly to state $n$ in one step (with probability $p_{n-1}$), or else you regress to state $n-2$ in one step, then take an expected $T_{n-1}$ steps to get back to state $n-1$, and then try again (with probability $1-p_{n-1}$). This gives $$ T_n=p_{n-1}\cdot 1+(1-p_{n-1})\cdot(1+T_{n-1}+T_n), $$ or $$ T_n=\frac{p_{n-1}\cdot 1 + (1-p_{n-1})\cdot(1+T_{n-1})}{p_{n-1}}\\ =1+(T_{n-1}+1)\cdot\frac{1-p_{n-1}}{p_{n-1}}\\ =\frac{1}{p_{n-1}} + T_{n-1}\left(\frac{1}{p_{n-1}}-1\right). $$ In your case, $n$ is the number of balls on the table, and $p_n=1-n/6$... you decrease the number of balls on the table when you draw one of the $n$ colors already present (with probability $n/6$), and otherwise you increase the number. So $$ T_n=\frac{6 + (n-1)T_{n-1}}{7-n}, $$ leading to $$ \begin{eqnarray} T_1 &=& 1, \\ T_2 &=& (6+T_1)/5 = 7/5, \\ T_3 &=& (6+2T_2)/4 = 11/5, \\ T_4 &=& (6+3T_3)/3 = 2+T_3 = 21/5, \\ T_5 &=& (6+4T_4)/2 = 3+2T_4 = 57/5, \\ T_6 &=& 6+5T_5 = 63. \end{eqnarray} $$ So the expected number of steps to first reach the final state ($n=6$) is $$E=T_1+T_2+T_3+T_4+T_5+T_6=416/5,$$ at which point there are $E-6=386/5=77.2$ balls in the box.

Answer 2

I would use a discrete Markov chain to model the number of colors $X(N) \in \{0, 1, \ldots, 6\}$ for which there are an odd number of marbles drawn at step $N$. At step $0$, there are no colors with an odd number of marbles drawn. At each subsequent step, either the number of colors with an odd number of marbles goes up by one, or down by one. The stopping criterion is that $X(N) = 6$. So the transition matrix looks like this: $$\mathcal P = \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{6} & 0 & \frac{5}{6} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{3} & 0 & \frac{2}{3} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & 0 & \frac{5}{6} & 0 & \frac{1}{6} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}$$ and we can use properties of Markov chains to compute the mean number of steps to reach state $7$ from state $1$. Then the total number of marbles in the box is simply $N - 6$. Note that $N$ must be even, so we define the random variable $Y = (N-6)/2$. Then $\operatorname{E}[Y] = \frac{193}{5}$ for the case of $6$ colors, and the probability distribution of $Y$ obeys the following recursion:

$$\Pr[Y = y] = \frac{25}{18}\Pr[Y = y-1] - \frac{34}{81}\Pr[Y = y-2] + \frac{5}{324}\Pr[Y = y-3]$$ with the initial conditions $$\Pr[Y = -2] = \Pr[Y = -1] = 0, \quad \Pr[Y = 0] = \frac{5}{324}.$$ The ordinary generating function for $\Pr[Y = y]$ is $$\mathcal G(z) = (\tfrac{324}{5} - 90 z + \tfrac{136}{5} z^2 - z^3)^{-1},$$ from which we can also calculate the expectation of $Y$, since $\operatorname{E}[Y] = G'(1)$. The closed form of $\Pr[Y = y]$ does exist but it is extremely lengthy to write, so it is omitted.

The above is easy to generalize to $m$ colors but the resulting calculations get more complex.