Irreducibility Means Mutual Access
A Markov chain can move through its state space in many ways: some states may be reachable from one another, while other transitions may only lead in one direction. Irreducibility is the condition that rules out this separation. It says that every state can eventually reach every other state, though the required number of steps may depend on the pair.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with finite or countable nonempty state space \(S\), transition matrix \(P=(p_{ij})\), and initial distribution \(\mu\), written as a row vector. Each row of \(P\) sums to \(1\), and \(P^{(n)}=P^n\) denotes the \(n\)-step transition matrix. The communication properties below depend on \(P\), not on the choice of \(\mu\).
The allowance \(n=0\) gives \(p_{ii}^{(0)}=1\), so each state is accessible from itself even if it has no one-step self-transition. For distinct states, accessibility requires at least one step. By the Chapman–Kolmogorov equations, a positive \(n\)-step transition probability means there is a finite route of transitions with positive probability; the route need not have the same length for different ordered pairs.
Communication and Communicating Classes
A communicating class is a set of states that all communicate with one another, maximal in the sense that it cannot be enlarged while preserving that property. The classes give a partition of \(S\). The link between this partition and irreducibility is exact, rather than approximate or dependent on the initial distribution.
Proof. First, communication is an equivalence relation. It is reflexive because \(p_{ii}^{(0)}=1\), and it is symmetric by the definition of communication. To show transitivity, suppose \(i\leftrightarrow j\) and \(j\leftrightarrow k\). There are nonnegative integers \(m,n\) with \(p_{ij}^{(m)}>0\) and \(p_{jk}^{(n)}>0\). Chapman–Kolmogorov gives \(p_{ik}^{(m+n)}=\sum_{\ell\in S}p_{i\ell}^{(m)}p_{\ell k}^{(n)}\ge p_{ij}^{(m)}p_{jk}^{(n)}>0\). Thus \(k\) is accessible from \(i\). Applying the same argument to paths from \(k\) to \(j\) and from \(j\) to \(i\) shows that \(i\) is accessible from \(k\), so \(i\leftrightarrow k\). Equivalence classes therefore partition \(S\). If the chain is irreducible, every pair of states belongs to the same equivalence class, so there is exactly one class, \(S\). Conversely, if there is exactly one communicating class, every pair lies in that class and hence communicates; this is irreducibility. \(\square\)
For a singleton state space, the conclusion still holds: its only state communicates with itself using \(n=0\), so the chain is irreducible. In a larger state space, finding even one pair that does not communicate is enough to establish reducibility. Conversely, checking all pairs directly can be tedious, so the following equivalent test can be useful.
Proof. If the chain is irreducible, its definition gives \(i\leftrightarrow r\) for every \(i\in S\). For the reverse direction, suppose every \(i\) communicates with \(r\). For any \(i,j\in S\), there is a finite positive-probability route from \(i\) to \(r\), and there is one from \(r\) to \(j\). Concatenating the routes gives a positive-probability route from \(i\) to \(j\): if their lengths are \(m,n\), Chapman–Kolmogorov gives \(p_{ij}^{(m+n)}\ge p_{ir}^{(m)}p_{rj}^{(n)}>0\). Reversing the roles of \(i\) and \(j\) gives accessibility from \(j\) to \(i\). Thus \(i\leftrightarrow j\) for every pair, which is irreducibility. \(\square\)
Worked Example: A Two-State Chain That Alternates
Consider \(S=\{1,2\}\) with transition matrix \(P=\begin{bmatrix}0&1\\1&0\end{bmatrix}\) and any initial distribution \(\mu\). Each row sums to \(1\): \(0+1=1\) and \(1+0=1\).
In one step, state \(1\) reaches state \(2\) with probability \(p_{12}^{(1)}=1\), and state \(2\) reaches state \(1\) with probability \(p_{21}^{(1)}=1\). Each state communicates with itself at step \(0\), since \(p_{11}^{(0)}=p_{22}^{(0)}=1\). Thus all four ordered pairs communicate, and the chain is irreducible.
As a check using matrix powers,
For instance, the first diagonal entry is \(0\cdot0+1\cdot1=1\), and the first off-diagonal entry is \(0\cdot1+1\cdot0=0\); the second row gives the other two entries in the same way. Every row of \(P^2\) also sums to \(1\). This chain is irreducible even though a state cannot remain where it is after one step: self-communication does not require a one-step self-transition.
Worked Example: A Three-State Deterministic Cycle
Let \(S=\{1,2,3\}\), with transitions \(1\) to \(2\), \(2\) to \(3\), and \(3\) to \(1\), each with probability \(1\). Thus \(P=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\). The row sums are \(0+1+0=1\), \(0+0+1=1\), and \(1+0+0=1\).
The transition probabilities give a route \(1\to2\) in one step and \(1\to3\) in two steps. From state \(2\), there are routes \(2\to3\) in one step and \(2\to1\) in two steps. From state \(3\), there are routes \(3\to1\) in one step and \(3\to2\) in two steps. Each route has probability \(1\), because every transition along it has probability \(1\). Along with step \(0\) for each state communicating with itself, this verifies communication for every ordered pair.
The powers confirm the routes:
For \(P^2\), the only nonzero entry in row \(1\) is in column \(3\), from \(1\to2\to3\); row \(2\) gives \(2\to3\to1\), and row \(3\) gives \(3\to1\to2\). Multiplying once more returns each state to itself, giving \(P^3\). Each displayed row sums to \(1\). The cycle therefore has one communicating class, all of \(S\), and is irreducible.
Worked Example: One-Way Access Does Not Give Irreducibility
Take \(S=\{1,2,3\}\) and \(P=\begin{bmatrix}\tfrac12&\tfrac12&0\\0&\tfrac12&\tfrac12\\0&0&1\end{bmatrix}\). Each row sums to \(1\): \(\tfrac12+\tfrac12+0=1\), \(0+\tfrac12+\tfrac12=1\), and \(0+0+1=1\).
State \(1\) reaches state \(2\) in one step with probability \(\tfrac12\). State \(2\) reaches state \(3\) in one step with probability \(\tfrac12\), so the two-step route from \(1\) to \(3\) has probability \(\tfrac12\cdot\tfrac12=\tfrac14\). State indices never decrease along a transition: from \(1\) the next state is \(1\) or \(2\), from \(2\) it is \(2\) or \(3\), and from \(3\) it remains \(3\). Therefore no state with a larger index can reach one with a smaller index. In particular, \(3\) cannot reach \(1\) or \(2\), and \(2\) cannot reach \(1\). There are no mutually communicating distinct states, so the communicating classes are \(\{1\}\), \(\{2\}\), and \(\{3\}\). The chain is not irreducible.
For an additional check, direct multiplication gives
For example, the first row is \((\tfrac12,\tfrac12,0)P=(\tfrac14,\tfrac12,\tfrac14)\), and the second is \((0,\tfrac12,\tfrac12)P=(0,\tfrac14,\tfrac34)\). The third row remains \((0,0,1)\). Each row sums to \(1\): \(\tfrac14+\tfrac12+\tfrac14=1\), \(0+\tfrac14+\tfrac34=1\), and \(0+0+1=1\). The entry \(p_{13}^{(2)}=\tfrac14\) confirms the two-step route, while \(p_{31}^{(n)}=0\) for every \(n\ge0\) because state \(3\) never leaves \(3\).
What Irreducibility Does—and Does Not—Say
Irreducibility describes which states can communicate over some finite number of steps. It does not say that every transition is possible in one step, that all states have equal transition probabilities, or that the chain reaches a particular state at a prescribed time. For example, in the alternating two-state chain, \(p_{12}^{(1)}=1\) but \(p_{12}^{(2)}=0\); nevertheless the states communicate. The relevant question is whether there exists a suitable finite step count for each direction.
Because an irreducible chain has only one communicating class, its entire state space is that class. In particular, there is no state in the chain outside that class. This statement concerns communication and makes no claim here about return-time behavior or limiting distributions. Those require additional properties and separate analysis.
Common mistake: treating accessibility as communication. In the three-state example above, it is incorrect to argue that \(1\) and \(3\) communicate because \(p_{13}^{(2)}=\tfrac14>0\). That calculation proves only that \(3\) is accessible from \(1\). Communication also requires a route back. But \(p_{31}^{(n)}=0\) for every \(n\ge0\), since the chain started at \(3\) stays there. Thus \(1\not\leftrightarrow3\). A correct irreducibility check must establish access in both directions for every pair, or use the fixed-reference-state criterion proved above.
Check Your Understanding
Use the definitions of accessibility, communication, and communicating class to answer each question.
- In the two-state alternating chain, why does the absence of one-step self-transitions not prevent irreducibility?
- For the three-state deterministic cycle, give a positive-probability route from state \(3\) to state \(2\), and state its length and probability.
- In the one-way chain, which ordered pair has \(p_{13}^{(2)}=\tfrac14\), and why does that not establish communication?
- State the fixed-reference-state criterion for irreducibility and identify the role of transitivity in its proof.
- What is the communicating class of a chain whose state space consists of one state, and which step count establishes self-accessibility?