40

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?

Scott M
  • 511
  • 4
  • 5
  • 25
    I'd like to test this with a practical experiment. Please pass me the almost-infinitely-large bag of M&Ms. :) – A E Jan 15 '15 at 17:43
  • 8
    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. – Set Big O Jan 15 '15 at 17:59
  • 1
    @ Geobits I suspect that in a bag of infinite size, that program could theoretically go on infinitely. The question says that the bag is almost infinitely large, which I'm assuming means finite. Therefore, each time a candy is taken out of the bag, the chances of pulling that color again should diminish. If not, and the bag is infinite, I think you're just as likely to get them all on the first try as you are to eat M&Ms for the rest of your life. – EFrog Jan 15 '15 at 18:08
  • 3
    @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. – Set Big O Jan 15 '15 at 18:09
  • 3
    @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. – March Ho Jan 15 '15 at 18:09
  • @MarchHo You mean terminate because he's full or because he will successfully have gotten out all six colors? I started writing out (and talking through) a solution in an answer, but it ends up looping to the point that it's a rotation of odds from 6/6, 5/6, 4/6, 3/6, 2/6, and 1/6. – EFrog Jan 15 '15 at 18:13
  • Terminate because of getting the 6 colours. Each case must terminate after a non-infinite time, and therefore the mean of it must therefore also be finite. – March Ho Jan 15 '15 at 18:14
  • 1
    Or terminate because he's full (or dead). One cannot continue to eat M&Ms for an incredibly large (even if non-infinite) time. Even if one eats them very slowly (e.g. 1/day) this process will eventually end. Only if the M&M-eating task can be passed to one's assigned heirs could it continue indefinitely - and even then we have the heat death of the universe to think about. – A E Jan 15 '15 at 18:16
  • 5
    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 :) – Scott M Jan 15 '15 at 22:28
  • 2
    Now do it using the actual M&M distribution: http://joshmadison.com/2007/12/02/mms-color-distribution-analysis/ – Thane Brimhall Jan 16 '15 at 18:52

3 Answers3

34

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.

theosza
  • 1,275
  • 10
  • 12
  • 6
    Matches my simulation pretty well :D – Set Big O Jan 15 '15 at 19:41
  • @Geobits, mine too, now I've *finally* remembered that we're meant to be counting the number of candies eaten rather than the number of candies drawn from the bag. – A E Jan 15 '15 at 19:53
  • @AE How else would you know you've eaten over 250 calories of junk? ;) – Set Big O Jan 15 '15 at 20:03
  • Awesome writeup. I had no idea how to account for moving backwards when pulling a similar color, but you explained it beautifully. Is there any way to figure out a range of M&Ms consumed for a given confidence interval? (For example, 75% of the time you will eat between X and Y M&Ms) – Scott M Jan 15 '15 at 22:23
  • 1
    Can this be generalized for n distinct colors? – Luke Willis Jan 15 '15 at 22:29
  • 2
    @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. –  Jan 15 '15 at 22:37
  • Can this be generalised for groups other than 2? E.g. I eat them when I have a group of 3 the same colour, I eat them when I have a group of 4 the same colour... Also, what if the bag is not unrealistically large, so that the distribution of M&Ms remaining in the bag does change as you take them out? – A E Jan 16 '15 at 09:36
  • 1
    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. – Compass Jan 16 '15 at 18:27
  • @Compass So I can expect to play this game at least 6 times a day without exceeding my recommended Caloric intake? Cool. – KSmarts Jan 16 '15 at 18:30
  • @KSmarts You'd exceed the sat. fat intake real quick. Each bag is 30% DV. And 270g of sugar is A LOT OF SUGAR. – Compass Jan 16 '15 at 18:32
  • 1
    @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... – KSmarts Jan 16 '15 at 18:43
  • @KSmarts a better example - it's like eating 67 packets of sugar at the table, assuming they're 4 grams apiece. – Compass Jan 16 '15 at 19:01
  • It amazes me how this approach and the Markov Chain approach give the same answer. I've never seen your method before though, and I would like to ask: why can you add up the expected cost going from state to state? Is there a proof for that? I get that expected costs obey linearity properties for random variables, but I've never heard it could be applied from $S_n$ to $S_{n+1}$ before. – koifish Aug 04 '19 at 00:55
31

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.

mathmandan
  • 1,053
  • 8
  • 15
  • 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? – A E Jan 16 '15 at 09:49
  • 1
    @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. – JiK Jan 16 '15 at 12:34
  • 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" ... ? – A E Jan 16 '15 at 15:38
  • @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.") – mathmandan Jan 16 '15 at 17:33
  • Of course, you're right. :) – A E Jan 16 '15 at 17:55
  • Thanks for introducing Markov Chains to me. Great answer to a "puzzle" which is tiny bit too much pure maths for this site - for my taste ;c) – BmyGuest Jan 27 '15 at 23:08
4

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.

supercat
  • 2,235
  • 9
  • 22
  • 1
    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. – theosza Jan 15 '15 at 18:38