# Markov Chain Reach One State Before Another

I'm stumped on a problem. Here's my transition matrix:

$$P = \begin{bmatrix} \frac{3}{4}&\frac{1}{4}&0&0&0&0&0 \\\\ \frac{1}{2}&\frac{1}{4}&\frac{1}{4}&0&0&0&0 \\\\ \frac{1}{4}&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&0&0&0 \\\\ \frac{1}{4}&0&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&0&0 \\\\ \frac{1}{4}&0&0&\frac{1}{4}&\frac{1}{4}&\frac{1}{4}&0 \\\\ \frac{1}{4}&0&0&0&\frac{1}{4}&\frac{1}{4}&\frac{1}{4} \\\\ \frac{1}{4}&0&0&0&0&\frac{1}{4}&\frac{1}{2}\end{bmatrix}$$

where the state space is {0, 1, 2, 3, 4, 5, 6}. I actually have two questions, one of which I've already answered and the other I cannot figure out. Here's the one I've already answered:

Suppose the chain has been running for a long time and we start watching the chain. What is the probability that the next three states will be $4$, $5$, $0$ in that order?

For this problem, I found the invariant probability vector $\pi$. I then computed

$$\pi(4) * p(4, 5) * p(5, 0) = .013 * \frac{1}{4} * \frac{1}{4} = .0008125.$$

Did I take the right approach to this question? If not, I would appreciate being pointed in the right direction.

The problem I cannot figure out reads:

Suppose the chain starts in state $1$. What is the probability that it reaches state $6$ before reaching state $0$?

I get the feeling that I will have to compute the $Q$ matrix treating $0$ as an absorbing state, but beyond that, I can't think of what I would do. Any advice?

-

This is exercise 1.10 in the second edition of Introduction to Stochastic Processes by Gregory Lawler. To solve it, use the method described starting in the middle of page 29. You need to consider both states $0$ and $6$ as absorbing, and use both the $Q$-matrix of transition probabilities from $\{1,2,3,4,5\}$ to itself, and the $S$ matrix of transition probabilities from $\{1,2,3,4,5\}$ to $\{0,6\}$.

That is, we have $$Q=\pmatrix{1/4&1/4&0&0&0\cr 1/4&1/4&1/4&0&0\cr 0&1/4&1/4&1/4&0\cr 0&0&1/4&1/4&1/4\cr 0&0&0&1/4&1/4\cr}$$ and $$S=\pmatrix{1/2&0\cr 1/4&0\cr 1/4&0\cr 1/4&0\cr 1/4&1/4\cr}.$$

The probability you want is the $(1,6)$ entry in the matrix $$(I-Q)^{-1}S=\pmatrix{143/144&1/144\cr 47/48&1/48\cr 17/18&1/18\cr 41/48&7/48\cr 89/144&55/144}.$$ The columns of this matrix are labelled $0,6$ while the rows are labelled $1,2,3,4,5$. The required probability is $1/144$.

-
Thanks, Byron. That's exactly what I was looking for. Incidentally I was able to figure it out when I needed it, but thanks anyway! – jrad Sep 24 '12 at 23:38
Could you explain why this works? – mb7744 Jan 23 '15 at 16:35

For the first question, I feel like what it's asking is slightly more complicated. What it seems to be asking is, suppose I let this chain run for a while, and then I observe it to be in a state $x$. What is the chance that immediately after this, the chain consecutively visits 4,5 and then 0, in that order. So I would condition on seeing the chain in state $x$, and then sum over the state space. In other words,

$\sum_{x=0}^6\pi(x)*p(x,4)p(4,5)p(5,0)$

This should simplify nicely and you might find a surprise in the answer.

For the second question, let $f(x)$ be the probability a markov chain starting at $x$, hit 6 before 0. In other words, you are interested in $f(0)$. We can come up with the following set of equations:

$\forall x\neq 0,6: \ f(x)=p(x,6)+(1-p(x,6)-p(x,0))\sum_{z\neq \{0,6\}}f(z)$

$f(0)=0$

$f(6)=1$

which gives you a system of six equations for six unknowns (well, two are immediate). Solving this will give you what you desire.

-