I was trying to do this question but with a recurrence relation for the Expected Values https://puzzling.stackexchange.com/questions/7900/the-mm-sugar-rush-game
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?
Right now the top answer is storing states $Δ =$ Expected MnM's eaten moving from n-1 to n
I attempted to write a recurrence relation and want to know why it is wrong. Let's define $E_x$ to be the # of MnM's we need to eat to get x on the board.
$E_x=\frac{n-1}{6}\cdot\left(E_x\ - E_{x-2} +\ 2\right)\ +\ \frac{6-(n-1)}{6}\left(E_{x-1}\right)$
Basically, we already have n-1 MnM types, so we have $\frac{6-(n-1)}{6}$ chance of not having to eat anymore than however many it took to get to $E_{x-1}$.
But if we get unlucky and draw one of the $n-1$ we already have then we will draw 1, then eat 2 MnMs, and be set back 1 MnM, so we have basically already drawn to $E_{x-2}$ but still need to pull until $E_{x}$.
This is largely undercounting compared to the answer, I assume it has something to do with the left side.
Example:
Say we are tying to get 5 on the Board, we have 4, we pull one of those 4, we eat two and get set back to 3.
It seems that $E_{3->5} != E_{5} -E_{3}$, anyone know if I can fix it?
It is true that $E_j - E_i$ gives you the expected number of M&Ms eaten to go from $i$ to $j$ M&M's on the table (when $i<j$).
The mistake is in the first term of the recurrence: it should be $$ E_n = \frac{n-1}{6}\Big(E_{n-1} + 2 + (E_n - E_{n-2})\Big) + \frac{6-(n-1)}{6}\Big(E_{n-1}\Big) $$ which I would actually write as $$ E_n = E_{n-1} + \frac{n-1}{6}(E_n - E_{n-2} + 2). $$ The idea is that to get to $n$, we have to get to $n-1$ no matter what, so both terms should have $E_{n-1}$ in them. Then, with probability $\frac{n-1}{6}$, we backtrack, eat $2$ M&Ms, and still have to get from $n-2$ to $n$.
Solving this from $E_0 = E_1 = 0$ gives us the same results as the answer on Puzzling StackExchange: $E_2 = 0.4$, $E_3 = 1.6$, $E_4 = 4.8$, $E_5 = 15.2$, and $E_6 = 77.2$.