Consider a discrete time Markov chain with state space $S = [1, 2, 3, 4, 5, 6]$ and transition matrix $$P = \begin{pmatrix}
.8 & 0 & 0 & .2 & 0 & 0\\
0 & .5 & 0 & 0 & .5 & 0\\
0 & 0 & .3 & .4 & .2 & .1\\
.1 & 0 & 0 & .9 & 0 & 0\\
0 & .2 & 0 & 0 & .8 & 0\\
.1 & 0 & .4 & 0 & 0 & .5\\
\end{pmatrix}$$
$…$
- Find the probability that starting from 6, 4 will be visited before 1, 2, or 5.
- Find the probability that starting from 6, 4 will be visited before 1.
- Find the probability that starting from 6, 4 will be visited before 2.
For part 4, my idea is to make 1, 2, 4, and 5 absorbing states, because once we've reached one of them we're done. Thus, we can create the matrix $F = (i – P_{T, T})^{-1} P_{T, R}$, where $T$ are transient states and $R$ are recurrent states. I get the following matrix: $$F = \begin{pmatrix}
.0323 & 0 & .645 & .323\\
.226 & 0 & .516 & .258\\
\end{pmatrix}$$
where the two rows represent 3 and 6, and the columns represent 1, 2, 4, and 5 (respectively). Thus, for number 4, the answer would be the (6, 4) entry in $F$, $.516$.
However, number 5 is a bit trickier. We know that if we enter states 2 or 5, we can never reach 4 or 1. Thus, we should not consider this probabilities, right? My idea for 5 is to compute $$\frac{F(6, 4)}{F(6, 4) + F(6, 1)}$$because we only care about the relative probabilities of entering 4 and 1, since entering 5 and 2 makes this probability meaningless.
Number 6 follows a similar structure; if we enter state 5, we are guaranteed to enter state 2 before 4. Likewise, if we enter state 1 we are guaranteed to enter state 4 before 2. Thus, this probability would be $$\frac{F(6, 4) + F(6, 1)}{F(6, 4) + F(6, 1) + F(6, 2) + F(6, 5)} = F(6, 4) + F(6, 1) = .742$$
Am I correct in my methods here? Thanks in advance!
Best Answer
Your idea to use a conditional probability derived from the computed absorption probabilities seems good at first glance: we only care about states 1 and 4, so we throw out the probabilities for 2 and 5. However, the system will never reach 1 or 4 if it enters 5, so you’ve effectively added the condition that the system never visit 5 on its way to the states of interest. That’s not a condition that’s understood in “starting from 6, 4 will be visited before 1.”
Mechanically, if you use the same method that you used to solve part 4, you end up with the same matrix $P_{T,T}$: neither state 2 nor state 5 is a transient state. If you do include them, you’ll find that $I-P_{T,T}$ is singular.
Drilling down a bit, these matrix manipulations compute the solution to a system of linear equations. Ian has a nice summary of them in this answer. We can compare the systems for questions 4 and 5 to see why the answer is the same for both.
For question 4, let $u(x)$ be the probability that, starting from state $x$, 4 is visited before any of $\{1,2,5\}$. Conditioning on the first step as usual, we get the system $$\begin{align} u(1) &= 0 \\ u(2) &= 0 \\ u(3) &= P_{3,3}\,u(3)+P_{3,4}\,u(4)+P_{3,5}u(5)+P_{3,6}\,u(6) = P_{3,3}\,u(3)+P_{3,6}\,u(6)+P_{3,4} \\ u(4) &= 1 \\ u(5) &= 0 \\ u(6) &= P_{6,1}\,u(1)+P_{6,3}\,u(3)+P_{6,6}\,u(6) = P_{6,3}\,u(3)+P_{6,6}\,u(6). \end{align}$$
Solving this system gives $u(6)\approx0.516$.
For question 5, we let $u(x)$ be the probability of visiting 4 before 1, starting at $x$. The system of equations is similar, but has fewer zeros to begin with: $$\begin{align} u(1) &= 0 \\ u(2) &= P_{2,2}\,u(2)+P_{2,5}\,u(5) \\ u(3) &= P_{3,3}\,u(3)+P_{3,4}\,u(4)+P_{3,5}\,u(5)+P_{3,6}\,u(6) = P_{3,3}\,u(3)+P_{3,5}\,u(5)+P_{3,6}\,u(6)+P_{3,4} \\ u(4) &= 1 \\ u(5) &= P_{5,2}\,u(2)+P_{5,5}\,u(5) \\ u(6) &= P_{6,1}\,u(1)+P_{6,3}\,u(3)+P_{6,6}\,u(6) = P_{6,3}\,u(3)+P_{6,6}\,u(6). \end{align}$$ If you solve this system, you end up with either $u(5)$ or $u(2)$ as a free variable. However, $\{2,5\}$ is a recurrent class that traps the system: once it hits 5 it never leaves this class, which means that $\Pr(X_k=4 \mid X_{<k}\in\{2,5\})=\Pr(X_k=4 \mid X_0\in\{2,5\})=0$, and so $u(5)=u(2)=0$, giving the same system of equations as before.
Your method happens to work for question 6 because keeping 2 as an absorbing state makes 5 transient, so it doesn’t “bleed off” any of the probability as it does in the previous question. You can, of course verify your computation by using the same method that you used for question 4.