Defining the states when we roll one single die repeatedly

Question

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?

Answer 1

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}$.

Answer 2

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.