Testing Irreducibility with Exact Transition Matrices

Irreducibility as an Exact Matrix Test

A transition matrix records all one-step possibilities of a finite Markov chain. To test irreducibility, the key question is not whether every pair of states is connected in one step, but whether a sequence of positive-probability transitions can take the chain from each state to every other state. With rational entries, this can be checked exactly: a transition is possible precisely when its entry is greater than zero. No numerical tolerance or approximation is needed.

Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), with transition matrix \(P=(p_{ij})\). The entries are nonnegative and each row sums to \(1\). The chain is defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). A path of length \(n\) from \(i\) to \(j\) is a sequence \(i=i_0,i_1,\ldots,i_n=j\) for which each one-step probability \(p_{i_{r-1}i_r}\) is positive. Its probability, conditional on starting at \(i\), is the product of those one-step probabilities.

The definition concerns possible paths, not their eventual frequency or the size of their probabilities. A path with probability \(1/1000\) is still a positive-probability path. The matrix gives a direct way to check for one-step paths: there is a transition from \(i\) to \(j\) exactly when \(p_{ij}>0\). For longer paths, matrix multiplication combines one-step possibilities.

Proof. For \(n=1\), the claim is the definition of a path of length one: such a path exists exactly when \(p_{ij}>0\). Suppose the claim holds for \(n\). Matrix multiplication gives \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). Every term is nonnegative, so this sum is positive exactly when at least one term is positive. Such a term exists exactly when, for some \(k\), there is a length-\(n\) path from \(i\) to \(k\) and a positive one-step transition from \(k\) to \(j\). Joining those paths gives a length-\((n+1)\) path. Conversely, the last step of any length-\((n+1)\) path comes from some \(k\), giving a positive term in the sum. This proves the claim by induction. At \(n=0\), \(P^0\) is the identity, whose \(ij\) entry is positive exactly when \(i=j\), corresponding to a path of length zero. \(\square\)

A Finite Bound and a Testing Procedure

It is not necessary to check paths of unlimited length. Write \(m=|S|\). If \(j\) is accessible from \(i\) and \(i\ne j\), choose a path of shortest length. No state can occur twice on this path: if it did, the segment between two occurrences could be removed, leaving a shorter path with the same endpoints. Thus the path visits at most \(m\) distinct states and has length at most \(m-1\). When \(i=j\), the length-zero path already suffices. Therefore it is enough to test paths of lengths at most \(m-1\).

For a fixed starting state \(i\), the test can be done by keeping a set of states reached so far. Begin with \(R_0=\{i\}\). At each round, add every state \(j\) for which some state \(k\) already in the set has \(p_{kj}>0\). This traces paths using only exact comparisons with zero; it does not require computing powers of \(P\).

Proof. For each \(r\ge0\), let \(R_r\) be the set produced after \(r\) rounds from a starting state \(i\). We show by induction that \(R_r\) consists exactly of states reachable from \(i\) by a path of length at most \(r\). At \(r=0\), \(R_0=\{i\}\), which is exactly the set reachable by a length-zero path. For the induction step, the procedure retains all states already in \(R_r\), and adds a state \(j\) if there is a \(k\in R_r\) with \(p_{kj}>0\). By the induction hypothesis, such a \(k\) has a path of length at most \(r\); appending the transition from \(k\) to \(j\) gives a path of length at most \(r+1\). Conversely, any path of length at most \(r+1\) either has length at most \(r\), or has a final positive transition from a state reached within \(r\) steps. In either case its endpoint belongs to \(R_{r+1}\). The induction is proved. By the finite path-length bound, every accessible state is reached within \(m-1\) steps. Thus the procedure includes all states from each starting state exactly when every state is accessible from every other state, which is the definition of irreducibility. \(\square\)

Worked Tests with Exact Entries

Why Exactness Matters

Rational entries allow every test to be made without rounding: reduce or compare fractions exactly, and treat an entry as a possible transition if and only if its numerator is positive. The magnitude of a positive entry can make a path unlikely, but cannot make it impossible. This is especially important when a small transition is the only way to leave a state or to complete a route through the state space.

Common mistake: discarding a small positive entry. Consider the matrix on \(\{1,2,3\}\)

The row sums are \(\tfrac{999}{1000}+\tfrac1{1000}+0=1\), \(0+0+1=1\), and \(1+0+0=1\). The path \(1\to2\to3\to1\) has probability \(\tfrac1{1000}\cdot1\cdot1=\tfrac1{1000}>0\); following this cycle from each starting state reaches all three states. The chain is irreducible.

A mistaken numerical procedure might replace \(\tfrac1{1000}\) by zero because it is below a chosen tolerance. It would then conclude that state \(1\) has no transition to another state and classify the altered matrix as reducible. That conclusion is for a different matrix. For exact rational inputs, test \(p_{ij}>0\), not whether \(p_{ij}\) exceeds an arbitrary cutoff. Also, checking only the positive entries in \(P\) is insufficient: a path may require several steps, so trace transitions for all states until the reachable sets stop growing or the \(m-1\) bound is reached.