From transitions to directed paths
A transition matrix records which one-step moves are possible, but irreducibility asks a question about movement over any finite number of steps. A graph makes the direction of those moves visible: each positive transition becomes a directed edge. The key fact is that a directed path is exactly a sequence of possible transitions, and its probability is positive when every transition along it has positive probability.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\in S\). Write \(p_{ij}^{(n)}=(P^n)_{ij}\) for the \(n\)-step transition probability. A state \(j\) is accessible from \(i\) if \(p_{ij}^{(n)}>0\) for some integer \(n\ge0\). The chain is irreducible if every state is accessible from every other state.
Edges are directed: an edge \(i\to j\) says nothing by itself about whether \(j\to i\) is an edge. A self-loop \(i\to i\) is included when \(p_{ii}>0\), but it is not required to connect a vertex to itself because the length-zero path already does that. In particular, a graph with one vertex is strongly connected under this convention.
Why matrix powers encode graph paths
The link between paths and transition probabilities is expressed by the path expansion. For \(n\ge1\), each possible intermediate sequence contributes the product of its one-step transition probabilities. Since all terms are nonnegative, the total is positive precisely when at least one such sequence has all its transitions positive.
Proof. For \(n=1\), the sum has no intermediate states and consists of the single term \(p_{ij}\), so the identity holds. Suppose it holds for \(n\). Chapman–Kolmogorov gives \(p_{ij}^{(n+1)}=\sum_{k\in S}p_{ik}^{(n)}p_{kj}\). Substituting the expansion for \(p_{ik}^{(n)}\) gives a sum over all intermediate states \(i_1,\ldots,i_{n-1},k\), with each term equal to \(p_{i i_1}\cdots p_{i_{n-1}k}p_{kj}\). These are exactly the products for paths of length \(n+1\), proving the identity by induction. Each term is nonnegative. A finite sum of nonnegative terms is positive exactly when at least one term is positive; a product of transition probabilities is positive exactly when every factor is positive. Thus a positive \(n\)-step probability is equivalent to a directed path of length \(n\), as claimed. \(\square\)
Proof. Suppose first that the chain is irreducible. For any distinct states \(i,j\), irreducibility gives an integer \(n\ge0\) with \(p_{ij}^{(n)}>0\). Since \(i\ne j\), this \(n\) cannot be zero: \(P^0\) is the identity matrix and \(p_{ij}^{(0)}=0\). Therefore \(n\ge1\), and the path expansion gives a directed path from \(i\) to \(j\). For \(i=j\), the length-zero path suffices. Hence the graph is strongly connected. Conversely, suppose the graph is strongly connected. For distinct \(i,j\), choose a directed path from \(i\) to \(j\) of some length \(n\ge1\). Every edge on it has positive transition probability, so its product is positive. The path expansion says that this product is one of the nonnegative terms in \(p_{ij}^{(n)}\), and therefore \(p_{ij}^{(n)}>0\). For \(i=j\), \(p_{ii}^{(0)}=1\). Thus every state is accessible from every state, which is irreducibility. The argument also covers a one-state chain: its only ordered pair has the length-zero path and \(p_{ii}^{(0)}=1\). \(\square\)
This equivalence turns a question about all powers of \(P\) into a finite graph question. In a finite graph, one useful test is to choose a reference vertex \(r\): the graph is strongly connected exactly when every vertex can reach \(r\) and \(r\) can reach every vertex. Indeed, if the graph is strongly connected both properties hold. If both properties hold, then for any \(i,j\), concatenate a path from \(i\) to \(r\) with a path from \(r\) to \(j\); the result is a directed path from \(i\) to \(j\). This test is useful by hand and underlies standard graph-search procedures.
Worked graph tests
Worked Example: A Three-State Chain with a Self-Loop
Consider \(S=\{1,2,3\}\) and $$ P= \begin{bmatrix} 0&1&0\\ \tfrac13&\tfrac13&\tfrac13\\ 0&1&0 \end{bmatrix}. $$ Each row sums to \(1\): the row sums are \(0+1+0=1\), \(\tfrac13+\tfrac13+\tfrac13=1\), and \(0+1+0=1\). Determine whether the chain is irreducible.
The positive-transition edges are \(1\to2\), \(2\to1\), \(2\to2\), \(2\to3\), and \(3\to2\). Every state can reach state \(2\): state \(1\) has the one-edge path \(1\to2\), state \(2\) has the length-zero path, and state \(3\) has the one-edge path \(3\to2\). State \(2\) can reach state \(1\) along \(2\to1\), state \(3\) along \(2\to3\), and itself by a length-zero path. Concatenating these paths gives a path from any state to any other, so the graph is strongly connected and the chain is irreducible.
Check with two path probabilities: the path \(1\to2\to3\) has probability \(1\cdot\tfrac13=\tfrac13>0\), and \(3\to2\to1\) has probability \(1\cdot\tfrac13=\tfrac13>0\). Both agree with the graph test. The self-loop at state \(2\) is an edge, but it is not needed to establish connectivity.
Worked Example: One-Way Accessibility Is Not Enough
Let \(S=\{1,2,3\}\) and $$ P= \begin{bmatrix} 0&1&0\\ 0&0&1\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(0+1+0=1\), \(0+0+1=1\), and \(0+0+1=1\). Is the chain irreducible?
The edges are \(1\to2\), \(2\to3\), and \(3\to3\). From state \(1\), there is a path to every state: \(1\) to itself has length zero, \(1\to2\) reaches state \(2\), and \(1\to2\to3\) reaches state \(3\). But state \(3\) cannot reach state \(1\) or state \(2\); its only outgoing edge returns to \(3\). The graph is not strongly connected, so the chain is not irreducible.
Check by a transition probability: after starting at \(3\), the chain remains at \(3\) at every step. Thus \(p_{31}^{(n)}=0\) for every \(n\ge0\), including \(n=0\), since \(3\ne1\). This directly confirms failure of accessibility from \(3\) to \(1\). The example shows that having a state from which all others can be reached does not by itself establish irreducibility.
Worked Example: A Four-State Cycle with a Branch
Consider \(S=\{1,2,3,4\}\) and $$ P= \begin{bmatrix} 0&\tfrac12&\tfrac12&0\\ 0&0&\tfrac13&\tfrac23\\ \tfrac14&0&0&\tfrac34\\ 0&1&0&0 \end{bmatrix}. $$ Check the row sums: row \(1\) sums to \(0+\tfrac12+\tfrac12+0=1\); row \(2\) to \(0+0+\tfrac13+\tfrac23=1\); row \(3\) to \(\tfrac14+0+0+\tfrac34=1\); and row \(4\) to \(0+1+0+0=1\). Test irreducibility.
The edges include the cycle \(1\to2\to3\to1\), which connects states \(1,2,3\) in both directions by following the cycle. State \(2\) also has an edge to \(4\), and state \(4\) has an edge back to \(2\). Thus state \(4\) can be reached from the cycle, and the cycle can be reached from state \(4\); the graph is strongly connected.
For explicit checks, the path \(3\to4\to2\) has probability \(\tfrac34\cdot1=\tfrac34>0\), and the path \(4\to2\to3\to1\) has probability \(1\cdot\tfrac13\cdot\tfrac14=\tfrac1{12}>0\). Also \(1\to2\to4\) has probability \(\tfrac12\cdot\tfrac23=\tfrac13>0\). These paths verify travel into and out of the branch at state \(4\); together with the directed cycle, they establish communication among every pair of states.
Common mistake and practical interpretation
Common mistake: ignoring edge direction. In the second example, one might draw a line between \(1\) and \(2\), another between \(2\) and \(3\), and conclude that all three vertices are connected. That calculation silently treats directed edges as undirected. The actual edges are \(1\to2\) and \(2\to3\), not \(2\to1\) and \(3\to2\). In particular, there is no directed path from \(3\) to \(1\). The correction is to test ordered pairs: for irreducibility, movement from \(i\) to \(j\) must be possible in the directed graph for every choice of \(i\) and \(j\), not merely in one direction.
Another useful distinction is between a positive transition and a merely listed transition. Only entries with \(p_{ij}>0\) create edges. An entry equal to zero contributes no possible one-step move and cannot be used as part of a path. Conversely, the numerical size of a positive probability does not affect whether an edge exists: for this criterion, probabilities \(\tfrac1{100}\) and \(1\) both give edges. The graph answers a yes-or-no reachability question, not a question about how likely or how quickly a state is reached.
For a finite chain, the criterion is particularly practical because the graph has finitely many vertices and edges. One can list the positive entries in each row, choose a reference state, and trace directed paths both toward and away from it. If either direction fails for even one state, the chain is not irreducible. If every state can reach the reference state and the reference state can reach every state, concatenation proves that all ordered pairs communicate. No calculation of stationary distributions, return times, or periods is needed for this test.
Check Your Understanding
For each question, keep the edges directed and use only strictly positive transition probabilities.
- A graph has edges \(a\to b\), \(b\to c\), and \(c\to a\). Is it strongly connected? Give a directed route from \(c\) to \(b\).
- In a two-state chain, \(p_{12}>0\) and \(p_{21}=0\). Can the chain be irreducible? Explain using the graph criterion.
- Why does a positive \(n\)-step transition probability imply that at least one length-\(n\) path has only positive-probability edges?
- For a one-state Markov chain, does the graph need a self-loop to be strongly connected under the length-zero path convention?
- State the two reachability checks using a reference vertex \(r\) that suffice to establish strong connectivity.