Dice Rolls

Here is a much simpler approach.

Imagine that a gambler in a fair casino takes the following strategy: in the first round he (very boringly) bets $1 that a die will land on one of 1,2,3,4,5,6. He then takes his winnings ($1) and gambles that the next roll will be different to the first roll, which happens with probability $\frac{5}{6}$ . If he wins then he takes his winnings ( $\frac{6}{5}$ ) and gambles that the next number will be one of the four which have not come up, and so on. He keeps this going: staking all his winnings on an unmatched number coming up until a streak of 6 unmatched numbers has been observed. Of course whenever there is a repeat he will lose all his money.

Now what the gambler does is start such a sequence of bets at each roll taking a new $1 from his pocket. He gambles until there is a string of distinct rolls. At this point the money from his live bets well be $\frac{6}{5}\times\frac{6}{4}\times\frac{6}{3}\times\frac{6}{2}\times\frac{6}{1}=\frac{324}{5}$ from the six roll accumulator, plus $\frac{6}{5}\times\frac{6}{4}\times\frac{6}{3}\times\frac{6}{2}$ from the five roll accumulator, down to $\$1$ from the one roll accumulator. This gives him total winnings of $\$\frac{416}{5}$

However since the casino is fair this $\$\frac{416}{5}$ on average will equal the money he has put in from his fortune. Since he gambles $1 each round, we know that the average wait for 6 distinct rolls is just $\$\frac{416}{5}$

We can model this scenario by a Markov process as follows: at any given stage let $k$ be the largest integer such that "the last $k$ die rolls are distinct" holds, and let $S_0, S_1, \ldots, S_6$ be the states in which $k=0,1,\ldots, 6$ respectively (of course, $S_0$ only occurs at the beginning before any rolls). Note that the current state precisely determines the probability distribution for the state after one more roll: for instance, from state $S_4$ there is a $\tfrac26$ chance of advancing to $S_5$ by rolling differently from the previous 4 values, and there is a $\tfrac16$ chance of transitioning to each of $S_1, S_2, S_3, S_4$ by matching one of the previous 4 values.

Define $E_k$ to be the expected number of rolls required to reach state $S_6$ starting from $S_k$ . Then clearly $E_6 = 0$ , and we are looking for the value of $E_0 = 1 + E_1$ . The transitions between states now yield a system of equations for $E_k$ : for instance, $E_4 = 1 + \tfrac26 E_5 + \tfrac16 ( E_1 + E_2 + E_3 + E_4 )$ , reflecting that one roll after $S_4$ we could be in any one of $S_1, \ldots, S_5$ with the specified probabilities. Rearranging this gives the equation $- E_1 - E_2 - E_3 + 5E_4 - 2E_5 = 6$ .

Compiling these equations gives the linear system:

$\begin{pmatrix} 5 & -5 & 0 & 0 & 0 \\ -1 & 5 & -4 & 0 & 0 \\ -1 & -1 & 5 & -3 & 0 \\ -1 & -1 & -1 & 5 & -2 \\ -1 & -1 & -1 & -1 & 5 \end{pmatrix}\,\begin{pmatrix} E_1 \\ E_2 \\ E_3 \\ E_4 \\ E_5 \end{pmatrix} = \begin{pmatrix} 6 \\ 6 \\ 6 \\ 6 \\ 6 \end{pmatrix}$

We suppress the gory details of solving this system (but note that the last two rows give $E_4 = \tfrac76 E_5$ and the middle three rows give $-3E_1 + 3E_2 + 2E_4 - 2E_5 = 18$ , which combines with the first row to give $E_4 - E_5 = \tfrac{54}5$ . In the end we find that $(E_1, E_2, E_3, E_4, E_5) = \tfrac15 (411, 405, 396, 378, 324)$ , so that $\boxed{E_0 = 1 + E_1 = \tfrac{416}{5}}$ . Our final answer is $416+5 = 421$ .

We will keep track of the following states: S1: "streak" of 1 (e.g. your first flip, or you flip something that was the same as the one before). S2: "streak" of 2, S3, S4, S5 similarly. We have:

I'll use these S's as the expected number of flips to reach a state of 6 distinct flips.

$S_1 = 1 + S_1/6 + 5S_2/6$ $S_2 = 1 + S_1/6 + S_2/6 + 4S_3/6$ $S_3 = 1 + S_1/6 + S_2/6 + S_3/6 + 3S_4/6$ $S_4 = 1 + S_1/6 + S_2/6 + S_3/6 + S_4/6 + 2S_5/6$ $S_5 = 1 + S_1/6 + S_2/6 + S_3/6 + S_4/6 + S_5/6$

How did we get these equations? Note that if you are on a streak of x, then you have a (6-x)/6 chance of continuing the streak (6-x numbers remaining), and an x/6 chance of breaking it. For the x/6 chance, you have an equal chance of regressing back to one of the earlier streaks (including the streak you are on.) To illustrate this, consider a streak of 3, e.g. 1123. If you roll a 1, 2, or 3, you do not extend your streak. But they have different effects. If you roll a 1, you still have a streak of 3. If you roll a 2, it's a streak of 2 (232 => 32). If you roll a 3, you must start over at a streak of 1.

(The 1+ is due to the fact that we have increased the roll count by 1.)

Anyway. Now that we have explained that, let's now solve the above!

But not so fast. We can speed this up significantly by noting that the equations are quite similar to each other. And with that, subtracting consecutive equations sounds like a good idea. We get the following:

$S_1 - S_2 = 4S_2/6 - 4S_3/6$ $S_2 - S_3 = 3S_3/6 - 3S_4/6$ $S_3 - S_4 = 2S_4/6 - 2S_5/6$ $S_4 - S_5 = S_5/6$

We might as well solve for the first equation by itself to get $S_1 - S_2 = 6/5$ . From here, we can get the other differences quite easily: $S_2 - S_3 = 6/5 \cdot 6/4 = 9/5$ ; $S_3 - S_4 = 9/5 \cdot 6/3 = 18/5$ ; $S_4 - S_5 = 18/5 \cdot 6/2 = 54/5$ ; $S_5 = 54/5 \cdot 6 = 324/5$ . And we add it all up and get $S_1 = 324/5 + 54/5 + 18/5 + 9/5 + 6/5 = 411/5$ .

But we have forgotten to account for the first flip that lands us at a streak of 1 in the first place, so our answer is $\boxed{\frac{416}{5}} \rightarrow 416+5=421$ .