Spectral characterization of convergence of Markov chains

markov chainsprobability theory

Let $P$ be the transition matrix of a reversible and irreducible Markov chain (on a finite state space).
Then all eigenvalues of $P$ are real, and if $1=|\lambda_1|\geq|\lambda_2|\geq\cdots\geq |\lambda_n|$ are all the eigenvalues of $P$ with $|\lambda_1|>|\lambda_2|$, then it can be shown that the chain is aperiodic.

My question is if we can drop the reversibility condition in the above.
Then of course not all eigenvalues may be real.
But suppose we are still guaranteed that $|\lambda_1|>|\lambda_2|\geq \cdots \geq |\lambda_n|$, where the $\lambda_i$'s are all the complex eigenvalues of $P$, then can we say that the given irreducible chain is aperiodic?

(The proof in the reversible case that I have seen makes use of the spectral theorem which furnishes with an orthonormal basis of eigenvectors of $P$ (with a suitable inner product). The orthonormality is crucially used. In the general setup that I am interested in we lose orthonormlaity. In fact, we may not even have a basis of eigenvectors since $P$ may not be diagonalizable.)

Best Answer

But suppose we are still guaranteed that $\big \vert \lambda_1\big \vert \gt \big \vert \lambda_2\big \vert \geq \ldots \geq \big \vert \lambda_n\big \vert$ where the $\lambda_i$'s are all the complex eigenvalues of $P$, then can we say that the given irreducible chain is aperiodic

Yes. This is a basic spectral result, or if you prefer a basic Perron Frobenius theory result. Since we know $\lambda_1 = 1$, i.e. the Perron root, suppose you look at your transition matrix $P$ and 'remove' the perron vectors, i.e. consider the matrix $B := P- \mathbf {1\pi}^{\top}$. The matrix $B$ is what determines the difference between the distribution in your chain and the stationary distribution.

$B$ has maximal modulus eigenvalue $\big \vert \lambda_2 \big \vert \lt 1$. So $\lim_{k \to \infty} B^k \to \mathbf 0$ and $\lim_{k \to \infty} P^k =\mathbf {1\pi}^{\top}$. This limit cannot exist if $P$ is periodic. So $P$ is aperiodic. Finite state chains always have at least one positive recurrent class, with an associated stationary distribution; so the non-existence of a limit is equivalent to a given chain having periodicity.

Equivalently a finite state (time homogenous) markov chain with a single communicating class is periodic iff it only has one eigenvalue on the unit circle.

Addendum
here is a sketch of a different route to the above result, one which relies on some probabilistic and analytic results and very little linear algebra. Everything below assumes there is a single communicating class.

1.) Prove that for any Markov chain with at least one non-zero entry on the diagonal of the n x n transition matrix $A$, you have $A^k \gt 0$ for all $k \geq K$ -- where this inequality is interpreted component-wise -- i.e. all components of $A^k$ are strictly positive. You can tighten the bound but an easy proof would be to select say $K = 5 n^2$ -- all that matters is K is some constant that depends only on $n$.

2.) Since looking at the diagonal gives useful information, consider that
$\text{trace}\big(P^r\big)$
$ = \lambda_1^r + \lambda_2^r + ... +\lambda_n^r $
$= 1 + \sum_{j=2}^n \lambda_j^r $
$= \big \vert 1 + \sum_{j=2}^n \lambda_j^r \big \vert$
$\geq \Big \vert \big \vert 1\big \vert -\big \vert \sum_{j=2}^n \lambda_j^r \big \vert \Big \vert $
$\geq 1 -\big \vert \sum_{j=2}^n \lambda_j^r \big \vert $
$\geq 1- \sum_{j=2}^n \big \vert\lambda_j \big \vert^r $
$\geq 1- (n-1)\cdot \big \vert\lambda_2\big \vert^r$
by application of triangle inequality
and for large enough $r$ we have
$\text{trace}\big(P^r\big) \geq 1- (n-1)\cdot \big \vert\lambda_2\big \vert^r \gt 0$, i.e. $P^r$ has at least one positive component on its diagonal for all $r\geq R$.

In combination with (1) this implies that $P^m \gt 0$ for all $m \geq M$.

3.) Since for large enough powers of $P$, the transition matrix is strictly positive, we can show that $P^m \to \mathbf {1\pi}^{\top}$. For several different elementary takes consider section 11.4 Fundamental Limit Theorem for Regular Chains in the free book by Grinstead and Snell
-- in particular (i) the main proof that starts the section, (ii) the Doeblin Proof, and (iii) the exercise 9 suggested by Doyle. All three are quite nice.

https://math.dartmouth.edu/~prob/prob/prob.pdf

Related Question