40
$\begingroup$

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?

$\endgroup$
  • 25
    $\begingroup$ I'd like to test this with a practical experiment. Please pass me the almost-infinitely-large bag of M&Ms. :) $\endgroup$ – A E Jan 15 '15 at 17:43
  • 8
    $\begingroup$ My Monte Carlo with 100k infinite bags suggests the answer should be around 77. If I had a mathy reason for that I'd post an answer. $\endgroup$ – Set Big O Jan 15 '15 at 17:59
  • 3
    $\begingroup$ @Efrog Yea, I was confused by the "almost infinite" part. If it's infinite, then the remaining candies don't matter. If it's not infinite, then we have to know the size of the bag to get an exact probability. I don't know what "almost infinite" really means, so did my sim with infinite. $\endgroup$ – Set Big O Jan 15 '15 at 18:09
  • 3
    $\begingroup$ @EFrog The expected number will not be infinity even if the bag itself has an infinite number, as the eating will terminate after a while. $\endgroup$ – March Ho Jan 15 '15 at 18:09
  • 5
    $\begingroup$ I meant "almost infinite" to mean that the color distribution of M&Ms is constantly uniform (to simplify the problem). At the same time, I wanted to dodge all the questions and physical implications resulting from having an infinitely large bag :) $\endgroup$ – Scott M Jan 15 '15 at 22:28
34
$\begingroup$

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.

$\endgroup$
  • 6
    $\begingroup$ Matches my simulation pretty well :D $\endgroup$ – Set Big O Jan 15 '15 at 19:41
  • 1
    $\begingroup$ Can this be generalized for n distinct colors? $\endgroup$ – Luke Jan 15 '15 at 22:29
  • 2
    $\begingroup$ @Luke Looks like it. The original recurrence relation has $\frac n6$ because there are 6 colors - changing it to $\frac nm$ where $m$ is the number of colors should generalize it. $\endgroup$ – Aza Jan 15 '15 at 22:37
  • 1
    $\begingroup$ Fun Fact, this is the equivalent of eating 1.5 servings/packs of standard vending machine M&Ms. Or 45g of sugar, 9g of saturated fat, and 360 calories. $\endgroup$ – Compass Jan 16 '15 at 18:27
  • 1
    $\begingroup$ @Compass Yeah, but most people's actual recommended DV is more than 2000 Calories (you may notice that my estimate of 6 times a day gives 2160 Calories). And 270g$\approx$0.6lbs, that doesn't seem like that much. WolframAlpha gives the helpful comparison that this is about 3/4 of a can of soda ...in pure sugar... oh God... $\endgroup$ – KSmarts Jan 16 '15 at 18:43
31
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hi @mathmandan - what do the columns and row in the matrix represent? The columns are the states and the rows are the probabilities of drawing a new colour? Have I got that right? $\endgroup$ – A E Jan 16 '15 at 9:49
  • 1
    $\begingroup$ @AE In the transition matrix, the element in row $i$, column $j$ is the transition probability from $i$ to $j$, that is, the probability that the next state is $j$ given that the current state is $i$. As the states are "0,1,...,6 candies", this means that, for example, the probability of moving to state "1 candy" if we are now at state "2 candies" is given in third row, second column. $\endgroup$ – JiK Jan 16 '15 at 12:34
  • $\begingroup$ Thank you @JiK! I get it now. Although shouldn't m's answer say "At absorption, there are 5 candies left uneaten on the table" ... ? $\endgroup$ – A E Jan 16 '15 at 15:38
  • $\begingroup$ @AE: The winning state is when there are 6 candies on the table (all of different colors). Any less than that and you have to keep playing. (See OP: "The game ends when I have all 6 distinct colors on the table.") $\endgroup$ – mathmandan Jan 16 '15 at 17:33
  • $\begingroup$ Of course, you're right. :) $\endgroup$ – A E Jan 16 '15 at 17:55
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Writing this out as a system of simultaneous linear equations and solving (by hand or using your favourite equation solver) gives: $E(0)=E(1)=77.2$, $E(2)=76.8$, $E(3)=75.6$, $E(4)=72.4$, $E(5)=62$. I'm hoping there's a more elegant solution though. $\endgroup$ – theosza Jan 15 '15 at 18:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.