Efficient way to determine if a transition matrix for a Markov Chain is ergodic, regular, and/or absorbing 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.
 A: 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


*

*Run Tarjan's algorithm on $G$.

*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


*

*Identify the set of all absorbing states $A \subset V$.

*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$.

*Let $G^{\prime\prime}$ be the graph $G^\prime$ with the direction of all of its edges reversed.

*Run breadth-first search (BFS) to determine the set of vertices $W$ in $G^{\prime\prime}$ that are not reachable from $v_A$.

*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:


*

*Pick an arbitrary vertex $v$ in $G$.

*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$.

*Let $\operatorname{val}(i,j)=d(i)+d(j)-1$. Then, the period of $A$
is $\gcd\{\operatorname{val}(e)\colon e\notin T\}$.

