On showing the existence of a Markov chain's steady state distribution

164 Views Asked by At

I want to show that the Markov chain with such transition matrices written below has a unique stationary distribution $\mu$.

For a space dimension of 6 : $$\begin{equation} \Pi^{(6)} = \begin{pmatrix} a_1 & a_2 & a_3 & a_4 & a_5 & b_1 \\ a_1 & a_2 & a_3 & a_4 & a_5 & b_1 \\ a_1 & a_2 & a_3 & a_4 & a_5 & b_1 \\ 0 & a_1 & a_2 & a_3 & a_4 & b_2\\ 0 & 0 & a_1 & a_2 & a_3 & b_3\\ 0 & 0 & 0 & a_1 & a_2 & b_4\\ \end{pmatrix} \end{equation}$$ or for a space dimension equal to 7 : $$\begin{equation} \Pi^{(7)} = \begin{pmatrix} a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & b_1 \\ a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & b_1 \\ a_1 & a_2 & a_3 & a_4 & a_5 & a_6 & b_1 \\ 0 & a_1 & a_2 & a_3 & a_4 & a_5 & b_2 \\ 0 & 0 & a_1 & a_2 & a_3 & a_4 & b_3 \\ 0 & 0 & 0 & a_1 & a_2 & a_3 & b_4 \\ 0 & 0 & 0 & 0 & a_1 & a_2 & b_5 \\ \end{pmatrix} \end{equation}$$

with $\forall i \in \mathbb{N} \ 0 < a_i < 1$ and $\forall i \in \mathbb{N} \ 0 < b_i < 1$

I know I can solve the linear system $\Pi \mu = \mu$ in order to solve this problem.

However I would like to know if from the specific "structure" of this matrix, one can say if there is or not a steady distribution ? Is there a direct way to see that this Markov Chain is aperiodic and irreductible ?

Indeed, I would like to extend this to a greater space dimension Markov process with a similar transition matrix and therefore solving $\Pi \mu = \mu$ would lead to very long computations.

Thank you.

1

There are 1 best solutions below

8
On

Yes, you can view the transition matrix as a graph and analyze its connectivity. For a transition matrix $\Pi \in \mathbb{R}^{n \times n}$, let $G=(V,E)$ be the directed graph where $V = [n]$ and $E = \{(i,j) \in [n]^2 : \Pi(i,j) > 0\}$.

The Markov chain is irreducible if and only if $G$ has one strongly connected component. Again, there are linear-time algorithms for checking this condition. More simply for the matrix above, we can see that all nodes $i > 1$ can directly reach node $i-1$. Moreover, node $1$ can transition to any node. Therefore, the graph has one strongly connected component and thus is irreducible.

An irreducible Markov chain is aperiodic if and only if $G$ has a node with period 1. In this case, it is even easier because every node has a self-loop since $\Pi(i,i) > 0$ for all $i \in [n]$.

It follows from the fundamental theorem of Markov chains that $\Pi$ has a unique stationary distribution.