Simple random walk on a disconnected graph

Question

Let's say that there is a disconnected graph with two disjoint components. How I do show that the graph has 2 distinct stationary distributions? I'm trying to prove that there is infinitely many stationary distributions by taking a linear combination of two distinct ones.

Answer 1

This post is specialized to (time homogenous) finite state markov chains.

For markov chains in the probability literature and most places, the transition matrix $P$ is row stochastic so $P\mathbf 1 = \mathbf 1$ and the steady state distribution is a left eigenvector of the transition matrix. So

$\mathbf \pi^T P = \mathbf \pi^T$
(though often the transpose symbol is omitted)

A basic underappreciated result is for markov chains is that the multiplicity of the perron root (i.e. $\lambda = 1$) counts the number of distinct recurrent classes in a markov chain. The Perron root is always semisimple, and it is simple (i.e. algebraic multiplicity of 1) iff the markov chain is irreducible -- i.e. one recurrent class. If a markov chain is not irreducible, then it is reducible.

For this problem we are told that the chain has a disconnected graph --i.e. it is reducible. Typically the simple random walk is done on a countably infinite state space, so some details are missing in this problem statement. (Further if the space was countably infinite the claim of at least 2 steady state distribution need not be true.) In any case we are told the chain is reducible and has finitely many states and hence up to graph isomorphism the transition matrix is block diagonal.

$P = \begin{bmatrix}P_1 & 0 \\ 0 & P_2 \end{bmatrix}$

every n state markov chain obeys $P\mathbf 1_n =\mathbf 1_n$. But the distinct communicating class contained in $P_1$ (where we say $P_1$ is r x r) must obey $P_1\mathbf 1_r = \mathbf 1_r$-- if it didn't then a quick check of blocked multiplication would show that $P\mathbf 1_n \neq \mathbf 1_n$ which would be a contradiction. This implies $\mathbf v_1 := \begin{bmatrix}\mathbf 1_r \\ \mathbf 0 \end{bmatrix}$ is an eigenvector for $P$ (again by blocked multiplication).

So $P\mathbf 1_n = \mathbf 1_n$ and $P\mathbf v_1 = \mathbf v_1$ and using linearity this implies
$\mathbf v_2 = \mathbf 1_n- \mathbf v_1$ is an eigenvector with eigenvalue 1 because
$P\mathbf v_2 = P\big(\mathbf 1_n- \mathbf v_1\big)= P\mathbf 1_n- P\mathbf v_1= \mathbf 1_n- \mathbf v_1 = \mathbf v_2$

similarly direct calculation tells us that
$P\mathbf v_2 = \mathbf v_2 \longrightarrow P_2 \mathbf 1_{n-r} = \mathbf 1_{n-r}$

so $\big(P_1 - I_r\big)$ has a nonzero vector in its nullspace as does $\big(P_2 - I_{n-r}\big)$.

Since row rank = column rank, in combination with rank-nullity, we know each $\big(P_1 - I_r\big)^T$ and $\big(P_2 - I_{n-r}\big)^T$ each have a non-zero vector in their nullspace. Perron Frobenius theory tells us that these vectors must be strictly positive and after rescaling to ensure they sum to one, they must be $\mathbf \pi_1 \text{ and }\mathbf \pi_2$ respectively. Since e.g. $\mathbf \pi_1^T P_1 = \mathbf \pi_1^T$, plugging this back into the original blocked structure tells us e.g. that

$\begin{bmatrix}\mathbf \pi_1 \\ \mathbf 0 \end{bmatrix}^T P =\begin{bmatrix}\mathbf \pi_1 \\ \mathbf 0 \end{bmatrix}^T$ and

$\begin{bmatrix}\mathbf 0 \\ \mathbf \pi_2 \end{bmatrix}^T P =\begin{bmatrix}\mathbf 0 \\ \mathbf \pi_2 \end{bmatrix}^T$

In a nutshell: a reducible chain implies (at least) 2 disjoint right eigenvectors with eigenvalue 1 which implies 2 disjoint left eigenvectors with eigenvalue 1. The standard approach is to then recurse on each smaller chain $P_1$ and $P_2$ and continue to apply the above techniques until the chain we are left working with is irreducible.