Calculating the probability of reaching each absorbing state in Markov Chain

Question

I'm starting with a Matrix that looks like this:

[[ 0 , 1/2, 0,  0 ,  0 , 1/2], 
 [4/9,  0 , 0, 3/9, 2/9,  0 ], 
 [ 0 ,  0 , 1,  0 ,  0 ,  0 ], 
 [ 0 ,  0 , 0,  1 ,  0 ,  0 ], 
 [ 0 ,  0 , 0,  0 ,  1 ,  0 ], 
 [ 0 ,  0 , 0,  0 ,  0 ,  1 ]]

And I'm being asked to calculate the probability of reaching each of the absorbing states C, D, E, and F starting from A. Obviously C is 0, and the other probabilities are given as:

A to D -> 3/14

A to E -> 1/7

A to F -> 9/14

but I don't know what steps or formulas I need to arrive at those values. I don't really know where to start with this so any help would be greatly appreciated!

Answer 1

The state transition diagram for the given problem is given by:

Consider transitions from A to D:

It could happen in several ways, as listed in the following. All these paths are mutually exclusive. Invoking the definition of of first passage time, we can obtain the required probability.

\begin{eqnarray*} A\rightarrow B \rightarrow D &=& p_{AB}\cdot p_{BD}\\ &=&\left(\frac{1}{2}\right)\left(\frac{3}{9}\right)=\frac{3}{18}\\ A\rightarrow B\rightarrow A\rightarrow B \rightarrow D &=& p_{AB}\cdot p_{BA}\cdot p_{AB}\cdot p_{BD}\\ &=&\left(\frac{1}{2}\right)\left(\frac{4}{9}\right)\left(\frac{1}{2}\right)\left(\frac{3}{9}\right)=\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)\left(\frac{3}{9}\right)\\ A\rightarrow B\rightarrow A\rightarrow B\rightarrow A\rightarrow B \rightarrow D &=& p_{AB}\cdot p_{BA}\cdot p_{AB}\cdot p_{BA}\cdot p_{AB}\cdot p_{BD}=p_{AB}\cdot \left(p_{BA}p_{AB}\right)^{2}\cdot p_{BD}\\ &=&\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)^{2}\left(\frac{3}{9}\right)\\ \end{eqnarray*} and several more such transitions. The probability of ever reaching from state A to D is obtained from the following probability:

\begin{eqnarray*} &&\frac{3}{18}+\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)\left(\frac{3}{9}\right)+\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)^{2}\left(\frac{3}{9}\right)+\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)^{3}\left(\frac{3}{9}\right)+\cdots\\ &=&\frac{3}{18}+\left(\frac{1}{2}\right)\left(\frac{2}{9}\right)\left(\frac{3}{9}\right)\left\{1+\frac{2}{9}+\left(\frac{2}{9}\right)^{2}+\cdots\right\}\\ &=&\frac{3}{18}+\frac{1}{3\times 9}\left\{\dfrac{1}{1-2/9}\right\}=\frac{27}{126}=\frac{3}{14} \end{eqnarray*} In a similar manner, we can find other probabilities.

Answer 2

If you have access to mathematical software like Python, you can solve it using the following trick.

The Eigendecomposition lets us split the matrix into

V x D x V^-1 where V is the eigenvector, and d is the eigenvalues.

the terminal states are then V x D ^ inf x V^-1, and we can find D ^ inf by looking at whether the values are >= or < 1.

Here is code that solves your problem.

import numpy as np
m = np.array(
    [
    [0, 1 / 2, 0, 0, 0, 1 / 2],
    [4 / 9, 0, 0, 3 / 9, 2 / 9, 0],
    [0, 0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0, 1],
    ]
)
d, v = np.linalg.eig(m)
v @ np.diag(d >= 1).astype(int) @ np.linalg.inv(v) 


[[0.        , 0.        , 0.        , 0.21428571, 0.14285714, 0.64285714],

   [0.        , 0.        , 0.        , 0.42857143, 0.28571429,   0.28571429],

   [0.        , 0.        , 1.        , 0.        , 0.        ,  0.        ],

   [0.        , 0.        , 0.        , 1.        , 0.        ,  0.        ],

   [0.        , 0.        , 0.        , 0.        , 1.        ,    0.       ],

   [0.        , 0.        , 0.        , 0.        , 0.        ,1.        ]]