Easy way to determine the stationary distribution for Markov chain?

Question

Suppose we have the following Markov chain with $S=\{a,b,c,d,e,f,g\}$

With the given transition matrix

$ P=\begin{pmatrix} 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1/6 & 1/6 & 0 & 1/6 & 1/2 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1/3 & 0 & 0 & 1/3 & 1/3 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix} $

The stationary distribution is given by

$$\pi P=\pi$$

For our case we have

$$(x_1,\ldots,x_7)\cdot P=(x_1,\ldots,x_7)$$

with $\sum_{i=1}^7x_i=1 \ \ \ \text{(1.0)}$

That would mean we have a large system of linear equations with a constraint (1.0). That would be hard to calculate it. Is there an easy way to this.

Answer 1

This Markov chain is reversible, as is any finite Markov chain whose underlying graph is a tree; like all reversible finite Markov chains, it can be viewed as random walk on a weighted graph.

If you give the edges $\{e,c\}$, $\{e,f\}$, $\{e,g\}$ each weight $3$, and the other edges weight $1$, then at each step the walker is choosing from the neighbors of its current state with probability proportional to the weight on that edge.

For a random walk on a weighted graph, the stationary distribution at a vertex is proportional to the sum of the weights of the edges at that vertex (loops only count once, but there aren't any in this example). Here we get $$\frac{1}{24}(1,1,6,1,9,3,3)$$ Note that $24$ is twice the sum of the edge weights.

Page 63 of Aldous-Fill writes this down in general (as, I'm sure, does your textbook).

Answer 2

Just to indicate another interpretation to the answer above, consider that the given Transition Matrix actually consists of three blocks
- A) $x_1, x_2, x_4 \; \to \; x_3$ with probability $1$, and from $x_3$ back to $x_1, x_2, x_4$ with the same probability of $1/6$ for each passage;
- B) $x_6, x_7 \; \to \; x_5$ with probability $1$, and from $x_5$ back to $x_6, x_7$ with the same probability of $1/3$ for each passage;
- C) a transition between block $A)$ and block $B)$ above, which occurs through the elements $x_3, x_5$, and which has a transition matrix given by $$ {\bf M} = \left( {\matrix{ {1/2} & {1/2} \cr {1/3} & {2/3} \cr } } \right) $$

Then it is clear that in block $C$ we will have an equilibrium at $x_3/x_5= 2/3$.
In block $A$ the equilibrium will mean $x_1 /x_3= x_2 /x_3=x_4 /x_3=1/6$,
and in block $B$ the equilibrium will mean $x_6 /x_5= x_7 /x_5=1/3$.

That means that the equilibrium vector will be $$(1,1,6,1,9,3,3)/24$$ which is in fact the (left) eigenvector of the transition matrix corresponding to the eigenvalue $1$.

Answer 3

It’s not that hard to calculate directly. The stationary distributions are left eigenvectors of $1$, i.e., (transposed) elements of the null space of $$(I-P)^T = \begin{bmatrix} 1&0&-\frac16&0&0&0&0 \\ 0&1&-\frac16&0&0&0&0 \\ -1&-1&1&-1&-\frac13&0&0 \\ 0&0&-\frac16&1&0&0&0 \\ 0&0&-\frac12&0&1&-1&-1 \\ 0&0&0&0&-\frac13&1&0 \\ 0&0&0&0&-\frac13&0&1 \end{bmatrix}.$$ This matrix is quite sparse and has $1$s running down its main diagonal, so row-reduction proceeds pretty quickly, resulting in $$\begin{bmatrix}1&0&0&0&0&0&-\frac13 \\ 0&1&0&0&0&0&-\frac13 \\ 0&0&1&0&0&0&-2 \\ 0&0&0&1&0&0&-\frac13 \\ 0&0&0&0&1&0&-3 \\ 0&0&0&0&0&1&-1 \\ 0&0&0&0&0&0&0 \end{bmatrix},$$ from which we find that the null space is the span of $\left(\frac13,\frac13,2,\frac13,3,1,1\right)^T$, which normalizes to the stationary distribution $\frac1{24}(1,1,6,1,9,3,3)$.