Canonical decomposition of absorbing chains

1.1k Views Asked by At

An absorbing Markov chain on $n$ states for which $t$ states are transient and $n-t$ states are absorbing can be reordered in a canonical decomposition with transition matrix

$$\boldsymbol{P}= \left[ \begin{array}{c|c} \boldsymbol{Q} & \boldsymbol{R} \\ \hline \boldsymbol{0} & \boldsymbol{I} \end{array} \right]$$

where $\boldsymbol{Q}$ is a $t\times t$ matrix and $\boldsymbol{R}$ is a $t\times (n-t)$ matrix. As usual, $\boldsymbol{0}$ is a matrix of zeros and $\boldsymbol{I}$ is the identity matrix.

An example would be the transition matrix $$\boldsymbol{P'}=\begin{bmatrix} 0 & .6 & 0 & 0& .4 & 0\\ .4& 0& .6& 0& 0 &0 \\ 0& .4& 0& .6& 0 & 0\\ 0& 0& .4& 0& 0&.6 \\ 0& 0&0 & 0 & 1 &0 \\ 0& 0 &0 & 0 &0 & 1 \end{bmatrix}.$$

Now, using the fundamnetal matrix $\boldsymbol{F}=(\boldsymbol{I}-\boldsymbol{Q})^{-1}$, we can calculate absorbtion probabilities and expected times until absorption.

One example gives the doubly stochastic transition matrix

$$\boldsymbol{T} = \begin{bmatrix} .3 & .5 & .2\\ .2& .4 & .4\\ .5 & .1 & .4 \end{bmatrix}$$

and asks to find $E(S \mid X_0 =1)$ where $S$ is the first time that $X_n=3$. The fundamental matrix is used, and the solution defines

$$\boldsymbol{Q}=\begin{bmatrix} .3 & .5\\ .2& .4 \end{bmatrix}.$$

How does this make sense if the matrix is clearly not in its canonical form, and what is an efficient method to transform a matrix into its canonical form?

1

There are 1 best solutions below

0
On BEST ANSWER

Because we want to know the number of steps until we first reach state $3$, the transition probabilities out of state $3$ don't actually matter. Therefore we can replace the matrix $$\boldsymbol{T} = \begin{bmatrix} .3 & .5 & .2\\ .2& .4 & .4\\ .5 & .1 & .4 \end{bmatrix}$$ by the matrix $$\boldsymbol{T'} = \begin{bmatrix} .3 & .5 & .2\\ .2& .4 & .4\\ 0 & 0 & 1 \end{bmatrix}$$ which describes a similar but absorbing Markov chain: here, once you get to state $3$, you never leave.

Again, this is no longer the same Markov chain, but if all we want to know is the expected number of steps until we reach state $3$, the answer is going to be the same whether we use $\boldsymbol T$ or $\boldsymbol {T'}$, because it doesn't matter what happens after we're in state $3$. Moreover, it makes sense to switch to $\boldsymbol {T'}$, because then "number of steps until we reach state $3$" becomes "number of steps until absorption", which we know how to find by using the fundamental matrix.

But $\boldsymbol {T'}$ actually is in the canonical form $\left[ \begin{array}{c|c} \boldsymbol{Q} & \boldsymbol{R} \\ \hline \boldsymbol{0} & \boldsymbol{I} \end{array} \right]$with $\boldsymbol{Q}=\begin{bmatrix} .3 & .5\\ .2& .4 \end{bmatrix},$ so now we can proceed by using properties of this canonical form.