The "M&M Sugar Rush" game

Question

Suppose I have in my possession a incredibly large (almost infinitely large!) bag of M&Ms containing a uniform distribution of the 6 M&M colors. I'm bored, so I decide to play a game:

I draw one M&M from the bag and place it on the table. I then continue to draw M&M's from the bag one at a time. If they are the same color as one already on the table, I eat both of them. Otherwise, I place it on the table with the others of different color. The game ends when I have all 6 distinct colors on the table.

How many M&M's should I expect to eat playing this game?

Answer 1

Let $S_n$ be the state where we have $n$ candies out on the table. We want to find the expected cost in eaten candies to advance from state $S_n$ to $S_{n+1}$. (This may, by chance, involve us having to move back by eating candies before moving forward again.) Let this expected value be $\Delta_n$.

$\Delta_0 = 0$ since from $S_0$ (0 candies out) you will always draw a single distinct candy out of the bag to get to $S_1$ and so no candies will be eaten.

Now assume we know $\Delta_{n-1}$, can we find $\Delta_n$? For this we want to know the expected cost to get from $S_n$ to $S_{n+1}$. Well there's a $\frac{n}{6}$ chance of drawing a match, eating 2 candies and moving back to state $S_{n-1}$. (The remaining fraction of the time there's no match and we advance to $S_{n+1}$ without eating a candy and so won't be needed for our calculations.) Now in state $S_{n-1}$ we know the expected cost to return to $S_{n}$ is $\Delta_{n-1}$ (assumed already calculated). This gives us the following equation: $$\begin{align*} &\Delta_n = \frac{n}{6} \times (2 + \Delta_{n-1} + \Delta_n)\\ \implies &6\Delta_n = n(2 + \Delta_{n-1}) + n\Delta_n\\ \implies &(6-n)\Delta_n = n(2 + \Delta_{n-1})\\ \implies &\Delta_n = \frac{n}{6-n}(2 + \Delta_{n-1}) \end{align*}$$ This formula now allows us to calculate the values for $\Delta_n$: $$\begin{alignat}{2} \Delta_0 &= 0 &=& 0\\ \Delta_1 &= \frac{1}{5}(2 + 0) &=& \frac{2}{5}\\ \Delta_2 &= \frac{2}{4}(2 + \frac{2}{5}) &=& \frac{6}{5}\\ \Delta_3 &= \frac{3}{3}(2 + \frac{6}{5}) &=& \frac{16}{5}\\ \Delta_4 &= \frac{4}{2}(2 + \frac{16}{5}) &=& \frac{52}{5}\\ \Delta_5 &= \frac{5}{1}(2 + \frac{52}{5}) &=& 62\\ \end{alignat}$$ The expected cost in candies eaten to get from $S_0$ (start state) to $S_6$ (terminal state) is: $$\begin{alignat}{2} &\Delta_0&+ &\Delta_1&+ &\Delta_2&+ &\Delta_3&+ &\Delta_4&+ &\Delta_5\\ = &0 &+ & \frac{2}{5} &+ & \frac{6}{5} &+ & \frac{16}{5} &+ & \frac{52}{5} &+ & 62 \end{alignat}$$ Which gives an expected number of candies eaten of 77.2.

Answer 2

This is a perfect opportunity to use the theory of Markov Chains.

The states are the number of candies currently on the table (either 0, 1, 2, 3, 4, 5, or 6 candies). If all 6 candies are present, then the game is over (this is called an "absorbing state"). Otherwise, if there are $n$ candies on the table, then the probability of matching one of them and thus having $n-1$ on the table at the next step is $n/6$, while the probability of drawing a new color and thus having $n+1$ candies on the table is $1 -n/6$. So the transition probabilities are described by the following $7\times 7$ matrix: $$ P = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 & 0 & 0\\ 1/6 & 0 & 5/6 & 0 & 0 & 0 & 0\\ 0 & 2/6 & 0 & 4/6 & 0 & 0 & 0\\ 0 & 0 & 3/6 & 0 & 3/6 & 0 & 0\\ 0 & 0 & 0 & 4/6 & 0 & 2/6 & 0\\ 0 & 0 & 0 & 0 & 5/6 & 0 & 1/6\\ 0 & 0 & 0 & 0 & 0 & 0 & 1\\ \end{pmatrix} $$ (Note that if there are $6$ candies on the table, then the game is over. You can never transition away from $6$ candies into restarting the game, so the absorbing state just steps to itself with probability $1$. This explains why there's a $1$ in the lower right corner of the matrix $P$; the last row and column of $P$ represent the absorbing state of $6$ candies.)

Now, we follow http://en.wikipedia.org/wiki/Absorbing_Markov_chain#Expected_number_of_steps and let $Q$ be the matrix $P$ excluding the absorbing states (so $Q$ is $P$ except for the last row and column). We calculate $N = (I-Q)^{-1}$, where $I$ is the $6\times 6$ identity matrix. The expected number of steps until absorption, starting at the "0 candies" state, will be the first entry of the vector $N Z$, where $Z$ is the length-6 column vector of all $1$'s.

It turns out that the expected number of steps until absorption is 83.2. At absorption, there are 6 candies left uneaten on the table, so that means you expect to eat 77.2 candies.

Answer 3

If there are six candies on the table, the expected number of additional candies to eat will be zero.

If there are five on the table, the expected number will be 5/6 of (two plus whatever the expected number would be with four), plus 1/6 of the expected number with six.

If there are four on the table, the expected number will be 4/6 of (two plus whatever the expected number would be with three) plus 2/6 of the expected number with five.

If there are three on the table, the expected number will be 3/6 of (two plus whatever the expected number would be with two) plus 3/6 of the expected number with four.

If there are two on the table, the expected number will be 2/6 of (two plus whatever the expected number would be with one) plus 4/6 of the expected number with three.

If there is one on the table, the expected number will be 1/6 of (two plus whatever the expected number would be with none) plus 5/6 of the expected number with two.

If there are none on the table, the expected number will be the same as the expected number with one

If one views the expected number of additional candies to eat when there are zero, one, two, etc. up to six candies on the table as being seven variables, the above will define a system of seven equations and seven unknowns (note that the "variable" for six is simply equal to zero, and the one for zero is equal to that of one, so if desired two variables and two equations may be omitted).

Using the above equations, it's easy to determine the number of candies that would need to be eaten with one candy on the table as being a linear function of the number of candies that would be consumed if there were two, then the determine the number with two as a linear function of the number that would be consumed if there were three, etc. up to five. Since the value at six is known (zero), that that means that the values for five, four, three, etc. can all be computed.