# Defining the states when we roll one single die repeatedly

We roll a single die and the game stops as soon as the sum of two successive rolls is either 5 or 7. We want to find the probability that the game stops at a sum of 5.

It seems like Markov chain with first-step analysis.

To find the transition matrix, I first need to define the states.

They way I define it is that if we have (1,2) then next state should be (2,x) for x=1,2,3,4,5,6.

And (1,2) is different from (2,1).

So, there must be 36 states?

For brevity, I'm going to say "we win" if the game stops with a sum of $5$, and "we lose" if the game stops with a sum of $7$. Note that (with probability $1$) either we win or we lose, that is, the game does not continue forever, because on every additional two rolls there is at least a $5/18$ probability of ending the game (in particular, those two rolls could have a total of $5$ or $7$) independent of any rolls that came before them.

Let $p_k$ be the probability that we win, given that the first roll is $k$.

Suppose we roll a $1$ and then a $2$. After the $2$, the probability that we will win is $p_2$; that is, all that matters after that roll is that we last rolled a $2$ and have not yet won or lost.

Consider all six possible second rolls when the first roll is $1$:

• roll $1$, in which case we win with probability $p_1$;
• roll $2$, in which case we win with probability $p_2$;
• roll $3$, in which case we win with probability $p_3$;
• roll $4$, in which case we win with probability $1$;
• roll $5$, in which case we win with probability $p_5$;
• roll $6$, in which case we win with probability $0$ (that is, we lose).

Since each of these second rolls has $1/6$ chance to occur, the overall probability to win when the first roll is $1$ is $$p_1 = \tfrac16(p_1 + p_2 + p_3 + 1 + p_5 + 0).$$

An equivalent statement is, $$5p_1 - p_2 - p_3 - p_5 = 1.$$

Applying similar reasoning to each possible first roll, we get a system of simultaneous linear equations in the variables $p_1, \ldots, p_6$. In matrix form, we can write $$M = \begin{pmatrix} 5 & -1 & -1 & 0 & -1 & 0 \\ -1 & 5 & 0 & -1 & 0 & -1 \\ -1 & 0 & 5 & 0 & -1 & -1 \\ 0 & -1 & 0 & 5 & -1 & -1 \\ -1 & 0 & -1 & -1 & 5 & -1 \\ 0 & -1 & -1 & -1 & -1 & 5 \end{pmatrix}, \quad x = \begin{pmatrix} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \\ p_6 \end{pmatrix}, \quad Mx = \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix}.$$

The matrix $M$ is invertible, $$M^{-1} = \frac{1}{8619} \begin{pmatrix} 2117 & 587 & 660 & 354 & 719 & 464 \\ 587 & 2117 & 354 & 660 & 464 & 719 \\ 660 & 354 & 2160 & 375 & 786 & 735 \\ 354 & 660 & 375 & 2160 & 735 & 786 \\ 719 & 464 & 786 & 735 & 2345 & 866 \\ 464 & 719 & 735 & 786 & 866 & 2345 \end{pmatrix},$$ and therefore $$x = M^{-1} \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 22/51 \\ 22/51 \\ 7/17 \\ 7/17 \\ 16/51 \\ 16/51 \end{pmatrix}.$$ At the start of the game, having made no rolls yet, the probability of winning is therefore $$p = \tfrac16(p_1 + p_2 + p_3 + p_4 + p_5 + p_6) = 59/153 \approx 0.385620915.$$

I approached this as a relatively direct calculation of probabilities, making the assumption that the probabilities exist. I was not particularly thinking of it in terms of Markov chains. Considering the game as a Markov process, however, the eight variables $p_1, p_2, p_3, p_4, p_5, p_6$ on the left of the system of equations and the two values $1, 0$ on the right correspond respectively to the six possible states of having last rolled the number $k$ ($1 \leq k \leq 6$) and not yet having won or lost, the state of having won, and the state of having lost. In other words, the same states as in Christian Blatter's answer.

• "This does not use Markov chains at all" Actually this is entirely based on the (simple) Markov property after one step. – Did Feb 5 '16 at 20:08
• This is not about speculating on the solution the OP expected but about recognizing that each relation such as $p_1 = \tfrac16(p_1 + p_2 + p_3 + 1 + p_5 + 0)$ uses the Markov property. – Did Feb 5 '16 at 21:32
• The exact values are $$p_1=p_2={22\over51}, \quad p_3=p_4={7\over17},\quad p_5=p_6={16\over51}\ ,$$ which then leads to $$p={59\over153}\ .$$ – Christian Blatter Feb 6 '16 at 9:00
• You need to justify that the probability of continuing forever is zero, otherwise the method is wrong. – user21820 Feb 15 '16 at 3:10
• @DavidK: Right. It might be obvious to you. But many people don't realize it, since almost no one bothers to justify that. That's why I said you should add the justification into your answer, even if it is only one line. I'm not just saying this to nitpick, because I know some university lecturers who weren't even aware of the logical pitfall until I told them. They never knew because nobody told them and they didn't have the proper foundation in logic to identify the gap themselves. – user21820 Feb 15 '16 at 5:11

I'd consider $8$ states, namely for $1\leq k\leq 6$ the states $s_k:\$"last roll was $k\>$, but game is not yet over", and the two end states $e_5$ and $e_7$. Denote by $x(n)$ the $(1\times8)$ row vector giving the probabilities that after $n$ rolls we are in the state $s_1$, $s_2$, $\ldots\$, $s_6$, $e_5$, $e_7$ respectively. It follows that $$x(1)=\left(h,h,h,h,h,h,0,0\right)\ ,$$ where I have written ${1\over6}=:h$ for typographical simplification. Let $P$ be the transition matrix. Then $p_{ik}$ denotes the probability that when in state $i$ the next roll will move us into state $k$. One then has $x(n+1)=x(n)P$. The matrix $P$ looks as follows (note that when we are in one of the end states we stay there): $$P=\left[\matrix{ h&h&h&0&h&0&h&h\cr h&h&0&h&0&h&h&h\cr h&0&h&0&h&h&h&h\cr 0&h&0&h&h&h&h&h\cr h&0&h&h&h&h&0&h\cr 0&h&h&h&h&h&0&h\cr 0&0&0&0&0&0&1&0\cr 0&0&0&0&0&0&0&1\cr}\right]\quad.$$ Computing $x(100)=x(1)P^{99}$ leads to the conjecture that the limiting probabilities for the end states $e_5$ and $e_7$ are ${59\over153}$ and ${94\over153}$.

• Hi, when defining valid transition matrix, I think sum of each row must be 1? – jessie Feb 5 '16 at 15:58
• My matrix acts on the left on the column vectors $x(n)$. Therefore its columns have sum $1$. – Christian Blatter Feb 5 '16 at 16:05
• Oh I see, could you explain again how you defined the states, I am confused – jessie Feb 5 '16 at 16:09
• If I get 1 on the die, then the game ends with 2 possible cases, (if we get 4 or 6), and continues with 4 possible cases. I do not see why your column has 6 h's and 2 0's – jessie Feb 5 '16 at 16:26
• I have transposed everything in oder to adopt the usual conventions. The result remains the same. – Christian Blatter Feb 5 '16 at 17:10