Stochastic Processes – Probability a Chain Enters State $5$ Before State $3$

markov chainsstochastic-processes

Given transition matrix $P$ = $\begin{pmatrix} 0 & 0.5 & 0.5& 0 & 0 \\
0 & 0 & 0 & 0.2& 0.8 \\ 0 & 0 & 0 & 0.4 & 0.6 \\ 1 & 0 & 0 & 0 & 0 \\
0.5 & 0 & 0 & 0 & 0.5 \end{pmatrix}$, how can we compute the probability that the chain will enter state $5$ before it enters state $3$ $?$

$$g(1)=0.5g(2), g(2)=0.8+0.2g(4), g(4)=g(1),$$ then I get $g(1)= {4\over 9}$, is it correct$?$ Actually, I do not very understand this one-step analysis mean$?$ Any help is Appreciated!

Best Answer

The general recipe: the probability to hit a set $A$ before hitting a set $B$ starting at a point $x$ is a function $u(x)$ which satisfies the system of equations

$$(Lu)(x)=0, \quad x \not \in A \cup B \\ u(x)=1, \quad x \in A \\ u(x)=0, \quad x \in B$$

where $L=P-I$ and $P$ is the transition matrix (taken in the row-stochastic convention, which is the convention you are using). You can prove this using the total probability formula, by conditioning on the outcome of the first step. For instance, in your case, $A=\{ 5 \}$, $B=\{ 3 \}$, and the first equation is:

$$u(1)=u(2)/2+u(3)/2=u(2)/2+0=u(2)/2.$$

The $L$ here is usually called the generator of the chain. The solution $u$ is sometimes called the committor of the chain (with respect to $(A,B)$).

In discrete space this is just a system of $|S|$ linear equations in $|S|$ unknowns, where $S$ is the state space.

Related Question