4
$\begingroup$

I was curious about how to apply the concept of Markov chains to the following problem:

Rolling a die, what is the probability that 1 followed by 2 will happen before two sixes in a row?

I have tried a model that has 15 states; however, this problem seems like it should be a lot easier.

Improve this question
$\endgroup$
4
  • $\begingroup$ You say, "will happen before", which strikes me as an unusual phrasing. How many rolls are there total, 4? Is the total number unconstrained? $\endgroup$
    – gung - Reinstate Monica
    Commented May 16, 2016 at 0:45
  • $\begingroup$ Hmm, the number is not constrained. I'm not sure how to better phrase the problem. Let me try though: The player rolls n times, the n + 1 roll is a 1 and the n + 2 roll is a 2. The game terminates here. Not once during the n rolls does a 6 follow a 6 Another possibility is that the player rolls m times with the last two rolls both be 6s. This would also terminate the game as 6, 6 arrived before 1, 2. is this clarifying it at all? $\endgroup$
    – user5590942
    Commented May 16, 2016 at 0:52
  • 1
    $\begingroup$ So you want the probability of getting a consecutive sequence of 1,2 without a consecutive sequence of 6,6 having occurred previously? I think there was a "where are there implicit parentheses in the problem statement" problem with the title and question as originally asked. $\endgroup$
    – Mark L. Stone
    Commented May 16, 2016 at 1:55
  • $\begingroup$ correct. My apologies for any confusion $\endgroup$
    – user5590942
    Commented May 16, 2016 at 2:04

2 Answers 2

Reset to default
7
$\begingroup$

We can solve this graphically. Only easy additions, multiplications, and divisions are required.

Constructing the Markov Chain

The question refers to just three faces of the die: the 1, the 2, and the 6. At the outset, none of these faces has been rolled. Let's call this state S (for "start"). The relevant states that can be reached from it are S (with probability $4/6$), 1, and 6 (each with probability $1/6$).

Continue building the Markov chain by considering what can be reached from the new states that were encountered, 1 and 6:

  • From 1, we may roll a 1 (staying in state 1), a 2 (ending the chain with the state 12, which is one of the states we are looking for), a 6 (thereby moving into state 6), or back to S otherwise. The chances are all $1/6$ for the first three moves, leaving a remainder $1-3\times 1/6=1/2$ for the chance of returning to S.

  • From 6, we may enter states 1, 66, or S with chances $1/6$, $1/6$, and (therefore) $2/3$, respectively.

The only new states to be considered are the terminal states 12 and 66. Thus, we have generated all the states of the chain (and computed their transition probabilities when we did so). Here is a graphical picture showing the states as nodes and the transitions as directed edges (or "pipes"), labeled by their probabilities.

Figure 1

Solving by Means of Graphical Reduction

Probability flows like a conserved fluid through this pipeline. (This is merely an intuitive way to restate the axioms of probability.) Ultimately we want to know what fraction of the fluid entering at point S will make it to 12 (and the remaining fraction will make it to 66). All we need to do is keep track of it. I will show how to do so by eliminating intermediate points and combining redundant pipes until the diagram is so simple we can read the answer directly from it.

We may eliminate the node S by noting that any "probability fluid" there will stick around for awhile (undergoing S to S transitions) but eventually will end up in either state 1 or state 6. The relative probabilities of those are the relative chances of the transitions, $1/6$ divided by $1/6+1/6$: each equals $1/2$. Thus, if we make a transition from 1 to S (which occurs with chance $3/6$), then half the time we will wind up right back at 1 and the other half of the time we will end at 6. Similar considerations cause two new pipes to be constructed in place of S to carry probability from 6 to 1 and 6 back to itself. These four new pipes are shown with dotted lines at the left of the next figure.

Figure 2

We may combine the probability flows between any two nodes that occur in multiple pipes: replace them by a single pipe with the sum of the flows. This is shown at the right. As a reminder of where the numbers originate, I haven't completely done all the arithmetic.

The same idea applies to the self-transitions at nodes 1 and 6. For instance, any probability that reaches 1 will stay around at 1 for awhile, but eventually some of it will flow to node 6 and some of it will go to 12. The relative proportions are $1/6+3/12=5/12$ to node 6 and $1/6$ to node 12, in proportions $5:2$. After also eliminating the 6 to 6 transition we obtain this diagram:

Figure 3

At this juncture we may split the diagram into two parts, again by eliminating round trips. Starting at node 1, we may ask what proportion of the probability ends at 12. The graph shows that either the probability flows directly to 12, or else it flows to 6, at which point $3/4$ of it promptly returns. The remaining $1/4$ will end up forever at 66. After applying the same reasoning to node 6, to determine what proportion of its probability ends up at 66, we obtain these two separate partial graphs:

Figure 4

Finally eliminating the self-transitions as before, we literally see the following:

  • The flows with rates $2/7$ and $1/4\times 5/7$ out of 1 are in proportion $8:5$. Thus, $8/(8+5)=8/13$ of the probability at 1 ends up at 12. The remainder, $5/13$, must end up at 66.

  • The flows with rates $1/4$ and $2/7\times 3/4$ out of 6 are in proportion $7:6$, whence $7/13$ of the probability at 6 ends up at 66 and the remaining $6/13$ ends up at 12.

That's (obviously) as far as we can go in reducing the original graph. Recall, now, that all probability begins at S. When we eliminated it, we had to direct half the probability to 1 and half the probability to 6. Accordingly, the proportion that ends up at 12 is half the proportion reaching 12 from 1 plus half the proportion reaching 66 from 6:

$$\Pr(\text{12 is final state}) = \frac{1}{2}\times \frac{8}{13} + \frac{1}{2}\times \frac{6}{13} = \frac{7}{13}.$$

This is the answer: there is a $7/13\approx 0.53846$ chance that 12 is encountered before 66.

(Either by carrying out a parallel calculation, or noting that eventually all the probability reaches either 12 or 66, we conclude that $6/13$ of the time, 66 is the final state.)

Comments

Looking back at the original diagram of the Markov chain, we can now see why 12 is slightly favored. The graph is nearly symmetric (identifying 1 with 6 and 12 with 66), except that the self transition from 1 to 1 causes more probability to collect at, and reside in, node 1. Consequently slightly more of it flows to 12 (which can only be reached via 1) than flows to 66 (which can only be reached via 6).

Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 Nice way of showing the answer comes out to 7/13, as opposed to my methods just producing a decimal number which equals 7/13. I think my ways are more straightforward, and allow for a mechanical solution method - I have an initial state distribution and transition matrix - let them (via MATLAB or whatever) do the work, ha ha. My calculations also show the probability of having first gotten to 1,2 or having first gotten to 6,6 as of any desired number of die rolls, i.e., the transient behavior, so I think some of your logic would have to be aborted or modified to get all that. $\endgroup$
    – Mark L. Stone
    Commented May 16, 2016 at 19:47
  • 1
    $\begingroup$ @Mark That is all correct--but entirely tangential. In a comment you asked for "some simple calculation" to arrive at the answer $7/13$ and in another you pointed out the emphasis in the question on using Markov chains. I posted this answer to reply simultaneously to both challenges, as well as to (a) explain how to construct the Markov chain in the first place and (b) illustrate a method of thinking about Markov chains and computing some of their properties that has not been described at this site before (AFAIK). It does not require computing high powers of a matrix, either! $\endgroup$
    – whuber ♦
    Commented May 16, 2016 at 19:52
2
$\begingroup$

Define the states 1,2,3,4,5,6,2a,6a, where states 2a and 6a are absorbing, and all other states are non-absorbing. State 1 can transition equally likely to 1,2a,3,4,5,6. States 2,3,4,5 can transition equally likely to states 1,2,3,4,5,6. State 6 can transition equally likely to 1,2,3,4,5,6a. 2a only transitions to 2a and 6a only transitions to 6a. Edit (next two sentences added for further explanation): If state 2a is reached, "1,2" wins, and the game is over, with the chain forever staying in that state. If state 6a is reached, "6,6" wins, and the game is over, with the chain forever staying in that state.

So the one-step transition matrix, with states ordered 1,2,3,4,5,6,2a,6a, is

$P =$ 

    0.1667         0    0.1667    0.1667    0.1667    0.1667    0.1667         0
    0.1667    0.1667    0.1667    0.1667    0.1667    0.1667         0         0
    0.1667    0.1667    0.1667    0.1667    0.1667    0.1667         0         0
    0.1667    0.1667    0.1667    0.1667    0.1667    0.1667         0         0
    0.1667    0.1667    0.1667    0.1667    0.1667    0.1667         0         0
    0.1667    0.1667    0.1667    0.1667    0.1667         0         0    0.1667
         0         0         0         0         0         0    1.0000         0
         0         0         0         0         0         0         0    1.0000

The 0.1667 entries are actually 1/6, and evaluated to full double precision accuracy in my calculations below.

The initial state distribution (after one roll) can be taken as initial state s = [1/6 1/6 1/6 1/6 1/6 1/6 1/6 0 0]. Then look at the 2a and 6a entries of $s P^n$ for n large. Using n = 1000 is more than sufficient to get all the probability to 16 significant digits into the absorbing states, with the resulting $s P^{1000} = $ zeros for states 1,2,3,4,5,6, and 0.538461538461539 for state 2a, and 0.461538461538462 for state 6a. So the probability of getting consecutive 1,2 without previously getting consecutive 6,6 is 0.538461538461539.

You might intuitively think the answer should be 0.5, but that is wrong. It is indeed a 50 50 proposition between getting to 2a vs. 6a on the 1st transition. But starting by the 2nd transition, things start moving in favor of 2a. That is because if the chain is in state 1 and fails to directly transition to 2a, it can still get to 2a in two steps (by going to 1 then 2a). But if it fails to go directly from 6 to 6a, it requires at least 3 steps to get to 6a, because it must first go to one of states 1 to 5, and then only can make it to 6a in 2 more steps after that (6 then 6a).

Here are, in order, $P^2$, $P^3$, $P^4$, which shows 2a gaining an increasing advantage over 6a.

0.1389    0.1111    0.1389    0.1389    0.1389    0.1111    0.1944    0.0278
0.1667    0.1389    0.1667    0.1667    0.1667    0.1389    0.0278    0.0278
0.1667    0.1389    0.1667    0.1667    0.1667    0.1389    0.0278    0.0278
0.1667    0.1389    0.1667    0.1667    0.1667    0.1389    0.0278    0.0278
0.1667    0.1389    0.1667    0.1667    0.1667    0.1389    0.0278    0.0278
0.1389    0.1111    0.1389    0.1389    0.1389    0.1389    0.0278    0.1667
     0         0         0         0         0         0    1.0000         0
     0         0         0         0         0         0         0    1.0000


0.1296    0.1065    0.1296    0.1296    0.1296    0.1111    0.2176    0.0463
0.1574    0.1296    0.1574    0.1574    0.1574    0.1343    0.0556    0.0509
0.1574    0.1296    0.1574    0.1574    0.1574    0.1343    0.0556    0.0509
0.1574    0.1296    0.1574    0.1574    0.1574    0.1343    0.0556    0.0509
0.1574    0.1296    0.1574    0.1574    0.1574    0.1343    0.0556    0.0509
0.1343    0.1111    0.1343    0.1343    0.1343    0.1111    0.0509    0.1898
     0         0         0         0         0         0    1.0000         0
     0         0         0         0         0         0         0    1.0000


0.1227    0.1011    0.1227    0.1227    0.1227    0.1042    0.2392    0.0648
0.1489    0.1227    0.1489    0.1489    0.1489    0.1265    0.0818    0.0733
0.1489    0.1227    0.1489    0.1489    0.1489    0.1265    0.0818    0.0733
0.1489    0.1227    0.1489    0.1489    0.1489    0.1265    0.0818    0.0733
0.1489    0.1227    0.1489    0.1489    0.1489    0.1265    0.0818    0.0733
0.1265    0.1042    0.1265    0.1265    0.1265    0.1080    0.0733    0.2083
     0         0         0         0         0         0    1.0000         0
     0         0         0         0         0         0         0    1.0000

This can be seen in terms of bottom line for 2a vs. 6a via the progression of $s P^n$, where it is shown in order below for n = 1,2,3,4.

0.1667    0.1389    0.1667    0.1667    0.1667    0.1389    0.0278    0.0278

0.1574    0.1296    0.1574    0.1574    0.1574    0.1343    0.0556    0.0509

0.1489    0.1227    0.1489    0.1489    0.1489    0.1265    0.0818    0.0733

0.1408    0.1160    0.1408    0.1408    0.1408    0.1197    0.1066    0.0944

Note that the number of states could be reduced by 2 by collapsing states 3,4,5 into a single state, with appropriate changes to P and initial state vector s.

Edit: In fact, the number of states can be reduced by 3, to a total of 5, by collapsing states 2 through 5 into a single state which I'll call "c". So the states are, in order, 1,c,6,2a,6a. The corresponding one state transition matrix is 

0.1667    0.5000    0.1667    0.1667         0
0.1667    0.6667    0.1667         0         0
0.1667    0.6667         0         0    0.1667
     0         0         0    1.0000         0
     0         0         0         0    1.0000

with initial state = [1/6 2/3 1/6 0 0].

And, ta dah, for any number of steps, the absorbing probabilities for 2a and 6a match exactly to the previous formulation, as of course they should, so I do not show the results again.

Improve this answer
$\endgroup$
10
  • $\begingroup$ Actually, I think the number of states can be reduced by 3, by collapsing states 2,3,4,5 into a single state, but the formulation might be a little more "unnatural". $\endgroup$
    – Mark L. Stone
    Commented May 16, 2016 at 4:09
  • $\begingroup$ Why would that abbreviated formulation be unnatural? Because the question refers only to values of 1, 2, and 6, its solution doesn't require states 3, 4, or 5. An advantage of using the question to guide the solution in this manner is that it easily generalizes to any process capable of producing two or more states. Since in most applications we have no interest in actual dice, but are using them only to help us reason about some other phenomenon, this generalization would appear to be more "natural" than a solution that is based on the properties of a standard six-faced die. $\endgroup$
    – whuber ♦
    Commented May 16, 2016 at 14:32
  • 1
    $\begingroup$ @whuber Perhaps "unnatural" was not the best choice of words, but slightly more "contorted" to write down the one step transition matrix for the 5 state formulation. Nevertheless, it is easy to do, and I edited my answer to show the 5 state formulation. Do note that I did not refer to the 6 state formulation, which retains state 2, and only collapses states 3 through 5, as being "unnatural", and that is the formulation which you actually addressed in your comment. $\endgroup$
    – Mark L. Stone
    Commented May 16, 2016 at 16:16
  • $\begingroup$ (+1) But isn't the initial state $(0,1,0)$ before the die has been rolled? Incidentally, your solution $0.538\ldots$ is much more simply expressed as $7/13$. $\endgroup$
    – whuber ♦
    Commented May 16, 2016 at 16:18
  • 2
    $\begingroup$ A simpler analysis (which, I agree, somewhat hides the Markov Chain formulation) recognizes this as a version of Penney's Game and applies the elementary solution methods described at stats.stackexchange.com/questions/12174. The $7:6$ ratio comes from the $1,2$ and $3,2$ minors, respectively, of the matrix $$\left( \begin{array}{ccc} 5 & -3 & -1 \\ -1 & 2 & -1 \\ -1 & -4 & 6 \\ \end{array} \right)$$ (whose rows and columns correspond to your 1, c, and 6 states). $\endgroup$
    – whuber ♦
    Commented May 16, 2016 at 16:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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