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?
Best Answer
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$.