4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ "This does not use Markov chains at all" Actually this is entirely based on the (simple) Markov property after one step. $\endgroup$ – Did Feb 5 '16 at 20:08
  • $\begingroup$ 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. $\endgroup$ – Did Feb 5 '16 at 21:32
  • $\begingroup$ 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}\ .$$ $\endgroup$ – Christian Blatter Feb 6 '16 at 9:00
  • 1
    $\begingroup$ You need to justify that the probability of continuing forever is zero, otherwise the method is wrong. $\endgroup$ – user21820 Feb 15 '16 at 3:10
  • 1
    $\begingroup$ @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. $\endgroup$ – user21820 Feb 15 '16 at 5:11
1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Hi, when defining valid transition matrix, I think sum of each row must be 1? $\endgroup$ – jessie Feb 5 '16 at 15:58
  • $\begingroup$ My matrix acts on the left on the column vectors $x(n)$. Therefore its columns have sum $1$. $\endgroup$ – Christian Blatter Feb 5 '16 at 16:05
  • $\begingroup$ Oh I see, could you explain again how you defined the states, I am confused $\endgroup$ – jessie Feb 5 '16 at 16:09
  • $\begingroup$ 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 $\endgroup$ – jessie Feb 5 '16 at 16:26
  • $\begingroup$ I have transposed everything in oder to adopt the usual conventions. The result remains the same. $\endgroup$ – Christian Blatter Feb 5 '16 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.