Steady states of stochastic matrix with multiple eigenvalues

Question

Let $M$ be an aperiodic left stochastic matrix, i.e. a real $n\times n$ matrix with each column summing to $1$ whose only eigenvalue on the unit circle is $1$. Moreover we assume that the geometric multiplicity of the eigenvalue $1$ is $k>1$.

If $P$ is a steady state of the system, then it satisfies $P=MP$ and since the multiplicity is bigger than $1$ the steady state is not unique, any normalized linear combination of the eigenvalues of $1$ is valid.

Let us define $\mathbf{1} = (1,1,\dots,1)$ and $P_0 = \tfrac{1}{n}\mathbf{1}$. I am interested in the state $P_*=\lim_{n\to\infty}M^nP_0$.

Does $P_*$ have any non-trivial algebraic properties? What can we know about $P_*$ without computing it explicitely?

Example: Let's consider $$M=\begin{bmatrix} 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1/2 \\ 0 & 0 & 0 & 1/2 \\ 0 & 0 & 0 & 0 \end{bmatrix}.$$

This Markov chain can be represented as:

The eigenvectors of $M$ that correspond to eigenvalue $1$ are $(1,0,0,0)$ and $(0,1,0,0)$. Let $\tilde P_0$ be $4$-vector that sum up to $1$, then the limit $\tilde P_*=\lim_{n\to\infty}M^n\tilde P_0$ always exists and can be any vector of the form $(a,1-a,0,0)$, where $0\le a\le1$.

In this case the vector $P$ that I defined above is $(5/8,3/8,0,0)$. Could we have "guessed" anything about $P$ without explicitly computing it?

Answer 1

$\mathbf 1$ is an eigenvector of $M$ if and only if $M$ is doubly stochastic (i.e. the rows of $M$ also sum to $1$). In this case, we trivially find that $M^nP_0 \to \mathbf 1$.

Suppose that this is not the case. If $M$ is aperiodic, then the only eigenvalue of $M$ with magnitude $1$ is $1$. We can write $$ \mathbf 1 = \sum_{k} a_k v_k + \sum_k b_k w_k $$ where $v_k$ are the eigenvectors of $M$ associated with $\lambda = 1$, and $w_k$ are eigenvectors of $M$ associated with some $\lambda$ such that $|\lambda|<1$. In fact, we can select the eigenvectors $v_k$ such that each eigenvector has non-zero entries. In this case, we compute $$ \lim_{n \to \infty} M^n P_0 = \sum_{k} a_k v_k. $$ Normalizing $\sum_{k} a_k v_k$ will yield a certain steady-state distribution, but I don't know if there's anything interesting to be said besides that.

In other cases, I'm not sure what we can say. Note that in the case that $M$ fails to be aperiodic, we can no longer assume that the desired limit exists.

Answer 2

Assume that $P$ has no eigenvalues other than $1$ of modulus $1$ (which occurs if and only if $P$ is aperiodic), or that $\mathbf{1}$ has no component in the direction of all such eigenvectors. (An equivalent way of saying the latter is that $\mathbf{1}$ is orthogonal to the corresponding left eigenvectors). If this hypothesis is violated, then the desired limit doesn't exist.

In this case, the chain is reducible into communicating classes $\{ C_i \}_{i=1}^j$, the first $k$ of which are recurrent. The recurrent communicating classes have associated invariant distributions $\pi_i$, such that $\pi_i$ is concentrated on $C_i$. The steady state vector is a convex combination of these. If there are no transient states (or the initial distribution assigns no probability to any transient states), then the weights are determined by the initial probability assigned to the communicating class. In the case of the uniform initial distribution this is just the number of states in the communicating class divided by $n$.

If there are transient states, then they can effectively contribute to the weight assigned to more than one of the recurrent communicating classes, depending on the probability that the process winds up in each recurrent communicating class when starting at each transient state. In your example state 4 contributes to the weight of both of the recurrent communicating classes equally. These probabilities can be determined by analysis of what is in general a simplified chain where each recurrent communicating class is replaced by a single absorbing state; then you can find the associated absorption probabilities of this simplified chain. In this simple example this reduction doesn't do anything because the recurrent communicating classes are already singletons.