State probabilities of a markov chain with multiple absorbing states

Question

Consider a gambler who starts with a fortune of 1 dollar. He keeps flipping a coin and gets one more dollar if he gets heads and loses one dollar if he gets a tails. He stops playing if he either reaches 4\$ or goes bankrupt (0$). Hence, if we consider the money he has as a Markov chain, then 4 and 0 are absorbing states.

Here is the transition matrix where the first three states are the transient ones (1,2,3) and the last two ones are the absorbing states (0 and 4). Hence, the bottom-right 2x2 matrix is identity.

$M = \left({\begin{array}{cccccc} 0 & \frac 1 2 & 0 & \frac1 2 & 0\\ \frac1 2 & 0 & \frac 1 2 & 0 & 0\\ 0 & \frac1 2 & 0 & 0 & \frac 1 2 \\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{array}}\right)$

When we multiply this matrix with itself many times, we get the following:

$\lim_{n \to \infty}M^n =\left({\begin{array}{cccccc} 0 & 0 & 0 & \frac 3 4 & \frac 1 4\\ 0 & 0 & 0 & \frac 1 2 & \frac 1 2\\ 0 & 0 & 0 & \frac 1 4 & \frac 3 4 \\ 0 & 0 & 0 & 1 & 0\\ 0 & 0 & 0 & 0 & 1 \end{array}}\right)$

This suggests that when we start in state 1, the probabilities of landing in states 0 and 4 are $\frac 3 4$ and $\frac 1 4$ respectively (first row of result matrix).

Now, I got this matrix by multiplying it with itself many times. However, there must be a way to obtain it through solving a linear system of equations (in particular, the 2x3 sub-matrix on the top-right). My first thought was to take a vector $v$ with 0s for the first three transient states and unknown variables for the last two absorbing states.

Then, I thought solving $vM=v$ would do the trick. However, any vector $v$ that has 0's for its first three elements and non-zero entries for its last two will satisfy this equation.

Answer 1

If you are interested in the probabilities $u_{ij}$ that given some initial state $i$ you will get absorbed into an absorbing state $j$, you can calculate them using the following formula:

$$u = (I-Q)^{-1}R$$

where $I$ is the identity matrix, $Q$ is the square matrix corresponding to transition probabilities between transient states, and $R$ is the non-square matrix corresponding to transition probabilities from a transient state into an absorbing state.

The reasoning behind this equation is based on conditioning the absorption process from state $i$ to state $j$ based on what happens in the first transition: either the absorption happens in the first transition with probability $R_{ij}$, or a transition occurs into some other transient state $k$ with probability $Q_{ik}$ and from there transitions until eventually absorbed with probability $u_{kj}$. This can be expressed as the matrix equation

$$u = Qu + R$$

where solving for $u$ generates the original equation above.

Answer 2

@aghostinthefigures's answer is probably the most elegant way to solve this. Another approach did occur to me and wanted to post it.

We can do the eigen decomposition of $M$ and get:

$ME=E\Lambda$

This implies,

$$M=E\Lambda E^{-1}$$

and,

$$M^n = E\Lambda^nE^{-1}$$

Where $\Lambda$ has the eigen vectors along the diagonals and zeros on the non-diagonals. Now, the eigen values will be 1 corresponding to the absorbing states and less than 1 in magnitude for the transient states.

So, $\Lambda^n$ will have 1's along its diagonals for the absorbing states and zeros everywhere else as $n$ becomes large.

So to get $M^n$, we can simply set the eigen values corresponding to the transient states to 0 and multiply out the matrix.

If you want to get efficient, you can take the $\hat{E}$, the submatrix corresponding to transient -> absorbing and $\hat{F}$, the sub-matrix of $E^{-1}$ from absorbing to absorbing and multiply the two.

Answer 3

I'd like to fill in some of the steps in the answer by @aghostinthefigures to get the matrix equation since I find myself spending 20 minutes deriving it every few years.

Let's say we want to go from transient state $i$ to recurrent state, $j$. The probability of this happening is $u_{i,j}$. Now, we can either go directly from $i$ to $j$ with probability $R_{i,j}$. Or, we can go first to some transient state, $k$ and from there to $j$. This gives us the equation:

$$u_{i,j}=R_{i,j}+\sum\limits_{k}Q_{ik}.u_{kj}$$

So, we just took the dot product of the $j$-th row of $u$ and $i$-th column of $Q$. This is the very definition of matrix multiplication, leading to the equation:

$$u = R+Q.u$$