# Thinking about a probability question using Markov chains

The problem is part (b):

1.4.7. A pair of dice is cast until either the sum of seven or eigh appears.

(a) Show that the probability of a seven before an eight is 6/11.

(b) Next, this pair of dice is cast until a seven appears twice or until each of a six and eight has appeared at least once. Show that the probability of the six and eight occurring before two sevens is 0.546.

I would like to try to solve this problem using Markov chains, but I'm encountering a dilemma. To calculate the probability, I would need to multiply down the branches that lead to a terminating state, and then sum all of those branches. But I have loops in my diagram, so I'm not sure how to account for the fact that I could remain in a state for an indefinite number of rolls:

[I only drew the branches corresponding to rolling a 6, but there are of course the two other branches (and sub-branches) for rolling a 7 or 8.]

If that's hard to read, here is a higher resolution. This is my chain of reasoning: We start out in a state of not having a 6, 7, or 8 yet. We could stay here indefinitely. Rolling a 6 takes us to the next state. We could also stay here indefinitely, or roll an 8 and get an accept state. Or we could roll a 7. At that state, we could roll another 7 and get an accept state or roll and 8 or indefinitely roll a 6 (or any other number). All of those probabilities are noted in the transitions.

How do I account for these possibilities?

• Since you're not keeping track of the number of rolls, any roll that brings you back to the current state can be considered a no-op and ignored. You can freely assume that you'll eventually get out of the loop and completely disregard anything that doesn't change your state. This can get more complicated if you have loops of length $>1$ (try creating a diagram for a game of zilch sometime) but here it's simple. – genisage Sep 30 '14 at 21:49

Drawing a state diagram in terms of Markov chains will help in calculating the probabilities to some extent, and you are right in that we need to sum all the branches.

The scenario of an indefinite number of rolls can be dealt with by realising that we will end up with a sum to infinity of geometric progressions whose ratio is a positive number less than $1$ (as the ratios are simply probabilities). Thus, there will be a finite sum to infinity, which will correspond to the probability we wish to find.

To find the probability that a $6$ and $8$ occur before two $7$s, there are $4$ branches we need to add together:-

1. For $n\geq2$ rolls of the dice, we obtain at least one $6$ and $(n-2)$ sums which are not $6$,$7$ or $8$, and the final roll results in the sum of $8$.

2. For $n\geq3$ rolls of the dice, we roll and obtain at least one $6$ and $(n-3)$ dice sums which are not $6$,$7$ or $8$ and one $7$, and the final roll results in the sum of $8$.

3. For $n\geq2$ rolls of the dice, we obtain at least one $8$ and $(n-2)$ sums which are not $6$,$7$ or $8$, and the final roll results in the sum of $6$.

4. For $n\geq3$ rolls of the dice, we roll and obtain at least one $8$ and $(n-3)$ sums which are not $6$,$7$ or $8$ and one $7$, with the final roll resulting in the sum of $6$.

Next we need to evaluate the probability of each these four branches occurring, which is obtained by summing to $n\rightarrow\infty$ dice rolls for each branch.

Let us denote as $P(S=x)$ the probability that the sum of the two dice equals $2\leq x \leq 12$ for a particular roll of the dice.

There are a total of $36$ possible outcomes, of which $5$ correspond to the sums of $6$ and $8$, and $6$ outcomes correspond to the sum of $7$. This leads to $$P(S=6)=P(S=8)=\frac{5}{36},P(S=7)=\frac{6}{36}=\frac{1}{6}$$ There are $20$ outcomes which do not correspond to the sums of $6$,$7$ and $8$, so that $$P(S\notin \{6,7,8\} )=\frac{20}{36}=\frac{5}{9}$$

Let us consider the probability of Branch 1 occurring with $n$ rolls of the dice, which we denote as $P_1(n)$.

The probability of obtaining such a result, for $n\geq2$ rolls is given as (where $1\leq k\leq n$ are the number of outcomes where the sum of $6$ is obtained, and there are $n-1 \choose k$ ways of selecting $k$ 6's from $n-1$ rolls- the final roll will be the sum of $8$)

$$P_{1}(n)=P(S=8)\left(\sum_{k=1}^{n-1}{n-1\choose k}P(S=6)^kP(S\notin \{6,7,8\})^{n-1-k}\right)\\=P(S=8)\left(\color{blue}{\left[\sum_{k=0}^n{n-1\choose k}P(S=6)^kP(S\notin \{6,7,8\})^{n-1-k}\right]}-P(S\notin \{6,7,8\})^{n-1}\right)\\=P(S=8)(\color{blue}{(P(S=6)+P(S\notin\{6,7,8\}))^{n-1}}-P(S\notin \{6,7,8\})^{n-1})\\=\frac{5}{36}\left(\left(\frac{25}{36}\right)^{n-1}-\left(\frac{5}{9}\right)^{n-1}\right)$$ Thus the probability of branch $1$ occurring is the difference between two sum to infinities of geometric series $$P_1=\sum_{n=2}^{\infty}P_1(n)=\frac{5}{36}\sum_{n=2}^{\infty}\left(\left(\frac{25}{36}\right)^{n-1}-\left(\frac{5}{9}\right)^{n-1}\right)\\=\frac{5}{36}\left(\frac{25}{11}-\frac{5}{4}\right)$$

Next we consider branch 2, where at most one $7$ is obtained.

This is a more involved process, as we need to consider one $7$, one or more $6$'s and $(n-3)$ sums which are not $6$,$7$ or $8$, and the final $8$.

Maintaining consistency in notation, for $n\geq3$ rolls of the dice we have (the highlighted factor $(n-1)$ is due to the number of positions the single outcome of $7$ occurs). $$P_2(n)=P(S=8)\color{red}{(n-1)}P(S=7)\left(\sum_{k=1}^{n-2}{n-2\choose k}P(S=6)^kP(S\notin \{6,7,8\})^{n-2-k}\right)\\=\frac{5}{36}(n-1)\frac{1}{6}\left(\left(\frac{25}{36}\right)^{n-2}-\left(\frac{5}{9}\right)^{n-2}\right)$$ Thus the probability of branch $2$ occurring is $$P_2=\frac{5}{216}\sum_{n=3}^{\infty}(n-1)\left(\left(\frac{25}{36}\right)^{n-2}-\left(\frac{5}{9}\right)^{n-2}\right)$$ To evaluate the sum to infinity, note that the sum is a differential of the sum of a geometric series, where $$\sum_{n=3}^{\infty}(n-1)x^{(n-2)}=\frac{d}{dx}\left(\sum_{n=3}^{\infty}x^{n-1}\right)=\frac{d}{dx}\left(\frac{x^2}{1-x}\right)=\frac{x(2-x)}{(1-x)^2}$$ Using this result, and setting $x=\frac{25}{36}$ and $x=\frac{5}{9}$, we obtain $$P_2=\frac{5}{216}\left(\left(\frac{36}{11}\right)^2\left(\frac{25}{36}\right)\left(\frac{47}{36}\right)-\left(\frac{9}{4}\right)^2\left(\frac{5}{9}\right)\left(\frac{13}{9}\right)\right)$$

Having gone through the detailed process for branch 1, evaluation of branch 3 is done in a similar manner, whereby $$P_{3}(n)=P(S=6)\left(\sum_{k=1}^{n-1}{n-1\choose k}P(S=8)^kP(S\notin \{6,7,8\})^{n-1-k}\right)$$ noting that $P(S=8)=P(S=6)$, we have $P_3(n)=P_1(n)$, so that that $$P_3=P_1=\frac{5}{36}\left(\frac{25}{11}-\frac{5}{4}\right)$$

Evaluation of branch 4, where the single sum of $7$ has to be dealt with, results in $$P_4(n)=P(S=6)(n-1)P(S=7)\left(\sum_{k=1}^{n-2}{n-2\choose k}P(S=8)^kP(S\notin \{6,7,8\})^{n-2-k}\right)\\=\frac{5}{36}(n-1)\frac{1}{6}\left(\left(\frac{25}{36}\right)^{n-2}-\left(\frac{5}{9}\right)^{n-2}\right)$$ and exploiting the fact that $P(S=8)=P(S=6)$, we have $$P_4=P_2=\frac{5}{216}\left(\left(\frac{36}{11}\right)^2\left(\frac{25}{36}\right)\left(\frac{47}{36}\right)-\left(\frac{9}{4}\right)^2\left(\frac{5}{9}\right)\left(\frac{13}{9}\right)\right)$$

Having evaluated all four branches, the total probability is given by \begin{align}P =& P_1+P_2+P_3+P_4\\=&2(P_1+P_2)\\=&\frac{5}{36}\left(\frac{25}{11}-\frac{5}{4}\right)+\frac{5}{108}\left(\left(\frac{36}{11}\right)^2\left(\frac{25}{36}\right)\left(\frac{47}{36}\right)-\left(\frac{9}{4}\right)^2\left(\frac{5}{9}\right)\left(\frac{13}{9}\right)\right)\\\approx& 0.546 \end{align}

• This is overkill, see my answer. – Yuval Filmus Sep 30 '14 at 20:01
• Overkill yes, but just as correct. – Alijah Ahmed Sep 30 '14 at 20:08
• Thank you Alijah for your very detailed response. I also thought about the problem some more and arrived at the same answer using this method (2 pictures): imgur.com/S4I7aOC,01KiwIB – Joseph DiNatale Oct 2 '14 at 17:04
• Your welcome, Joseph. I had a look at your answer, and it is quite comprehensive and good. – Alijah Ahmed Oct 2 '14 at 19:17

We can think of the experiment as follows. At the start, we have a biased three-sided coin that outputs $6,7,8$ with probabilities $5/16,3/8,5/16$; we don't care about the other outcomes, so we can just ignore them. After we see $6$, we don't care about $6$, so the probabilities of $7,8$ are $6/11,5/11$.

Here are the possible runs of the game:

1. $6,8$ or $8,6$: probability $2\cdot 5/16 \cdot 5/11$.
2. $6,7,8$ or $8,7,6$: probability $2\cdot 5/16 \cdot 6/11 \cdot 5/11$.
3. $6,7,7$ or $8,7,7$: probability $2\cdot 5/16 \cdot 6/11 \cdot 6/11$.
4. $7,6,8$ or $7,8,6$: probability $2\cdot 3/8 \cdot 5/16 \cdot 5/11$.
5. $7,6,7$ or $7,8,7$: probability $2\cdot 3/8 \cdot 5/16 \cdot 6/11$.
6. $7,7$: probability $3/8\cdot 3/8$.

Summing up the relevant cases, the probability that both $6,8$ appear before $7$ appears twice is $4225/7744$.

Others have already given some excellent answers to this problem, and the original post was over two years ago. Nevertheless, I would like to show how the problem can be solved by using an exponential generating function.

We know the last number rolled must be a 6 or an 8, and by symmetry we know these two cases are equally likely, so let's suppose the last number is an 8 in order to simplify the problem a bit. Then an acceptable sequence of rolls starts with $$n >0$$ rolls consisting of no 8's, at least one 6, and at most one 7, followed by a final 8. Let $$a_n$$ be the probability of rolling the initial sequence (not including the final 8), for $$n \ge 0$$. Any acceptable initial sequence is the "labeled product" of

• any number of rolls which are not 6's, 7's, or 8's
• at least one roll of 6
• at most one roll of 7

so the exponential generating function for $$a_n$$ is \begin{align} f(x) &= \sum_{n=0}^{\infty} \frac{1}{n!} a_n x^n \\ &= \left(1 + qx + \frac{q^2}{2!} x^2 + \frac{q^3}{3!} x^3 + \dots \right) \left( p_6 x + \frac{p_6^2}{2!} x^2 + \frac{p_6^3}{3!} x^3 + \dots \right) (1 + p_7x) \\ &= e^{qx} (e^{p_6 x} -1) (1+ p_7 x) \end {align} where $$q$$ is the probability of rolling anything but a 6, 7, or 8, and $$p_k$$ is the probability of rolling a $$k$$. The numerical values are $$q = 20/36$$, $$p_6 = 5/36$$, and $$p_7 = 6/36$$.

The probability of rolling an acceptable initial sequence of length $$n$$ followed by an 8 is $$a_n p_8$$, so the total probability of any acceptable initial sequence followed by an 8 is $$p = \sum_{n=0}^{\infty} a_n p_8$$ We can use the following trick to extract this sum from $$f(x)$$. Since $$n! = \int_0^{\infty} e^{-x} x^n \; dx$$ we have $$p = \sum_{n=0}^{\infty} a_n p_8 = \int_0^{\infty} f(x) \; e^{-x} \; p_8 \; dx = \int_0^{\infty} e^{qx} (e^{p_6 x} -1) (1+ p_7 x) \; e^{-x} \; p_8 \; dx$$ Evaluating the integral yields $$p = \frac{4225}{15488}$$ which is the probability of an acceptable sequence of rolls ending in 8.

The answer to the original problem, where the final roll may be either a 6 or an 8, is then $$2p = \frac{4225}{7744}$$