Efficient way to determine if a transition matrix for a Markov Chain is ergodic, regular, and/or absorbing

Question

If given a transition matrix, is there an easy and efficient method to determine if this matrix is absorbing, ergodic, and/or regular? I understand the definitions of all three terms, but if given a $2$ by $2$ or $3$ by $3$ transition matrix, I'm wondering if there's an intuitive way to determine if this transition matrix is absorbing, ergodic, and/or regular just by looking at the matrix and without performing any complex calculations.

Answer 1

Let $T = (t_{ij})$ be an $n \times n$ transition matrix (i.e., $t_{ij} = \mathbb{P}(X_n = j \mid X_{n-1} = i)$).

Let $G = (V, E)$ be the graph with vertex set $V = \{1, \ldots, n\}$ and edge set $E \subset V \times V$ such that $(i,j) \in E$ if and only if $t_{ij} \neq 0$.

Test if the Markov chain is ergodic

1. Run Tarjan's algorithm on $G$.
2. The Markov chain is ergodic if and only if there is exactly one connected component.

This algorithm requires $O(|V|+|E|)=O(n^2)$ operations (due to Tarjan's algorithm). If the transition matrix is sparse (in the sense that there are at most a constant number of nonzero entries per row), then the algorithm requires only $O(|V|+|E|)=O(n)$ operations.

Remark: you can run this algorithm on paper for a small matrix, though I do not suggest using Tarjan's algorithm to find the set of connected components. Find these by hand with a picture.

Test if the Markov chain is absorbing

1. Identify the set of all absorbing states $A \subset V$.
2. Let $G^\prime$ be the vertex contraction of $G$ on the set of vertices $A$. Call the new vertex in the vertex contraction $v_A$.
3. Let $G^{\prime\prime}$ be the graph $G^\prime$ with the direction of all of its edges reversed.
4. Run breadth-first search (BFS) to determine the set of vertices $W$ in $G^{\prime\prime}$ that are not reachable from $v_A$.
5. The Markov chain is absorbing if and only if $W$ is empty.

This algorithm requires $O(|V|+|E|)=O(n^2)$ operations (due to the BFS). If the transition matrix is sparse, then the algorithm requires only $O(|V|+|E|)=O(n)$ operations.

Remark: you can run this algorithm on paper for a small matrix.

Test if the Markov chain is regular

I'm not aware of a fast test to check if a Markov chain is regular, but I also haven't thought about this too hard.

Proposition [Theorem 2.18 of R. S. Varga, Matrix Iterative Analysis]: A nonnegative square matrix $A$ is primitive if and only if $A^m$ has only positive entries for some positive integer $m$.

Due to the above, it suffices to check if $T$ is primitive. $T$ being primitive is equivalent to $T^{n^2-2n+2}$ having only positive entries. Note that this requires $O(n^3 \log n)$ operations.

There is a better algorithm, however, that is $O(n^2)$ in the dense case and $O(n)$ in the sparse case. It is originally described in Denardo, Eric V. "Periods of connected networks and powers of nonnegative matrices." Mathematics of Operations Research 2.1 (1977): 20-24. There is also a nice exposition in Jarvis, J. P., and Douglas R. Shier. "Graph-theoretic analysis of finite Markov chains." Applied mathematical modeling: a multidisciplinary approach (1999).

I can, at least, summarize the algorithm below:

1. Pick an arbitrary vertex $v$ in $G$.
2. Run BFS to determine the distance $d(w)$ from $v$ to all other vertices $w$. Since BFS does not visit a node more than once, the edges traversed in BFS form a tree. Call this set of edges $T$.
3. Let $\operatorname{val}(i,j)=d(i)+d(j)-1$. Then, the period of $A$ is $\gcd\{\operatorname{val}(e)\colon e\notin T\}$.