= Irreducible Markov chain
{wiki}
= Markov chain irreducibility
{c}
{synonym}
For a finite, time-homogeneous <Discrete-time Markov chain> with row-stochastic <transition matrix> $P$, irreducibility means
$$
\forall i,j\in S\quad\exists n\geq0:\quad(P^n)_{ij}>0.
$$
Equivalently, all states form one <communicating class>. The step count may depend on $i,j$; irreducibility does not require every one-step <transition probability> to be positive. Drawing an arrow $i\to j$ whenever $P_{ij}>0$ makes the condition exactly that of a <strongly connected directed graph>. It is a property of the entire chosen <state space>, independent of the initial <probability distribution>.
Irreducibility describes where the <Markov chain> can travel; <aperiodicity> describes the possible lengths of return paths. For example, restricting the second diagram in <communicating class> to its closed pair $\{c_1,c_2\}$ gives
$$
C=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad
C^{2k}=I,\qquad C^{2k+1}=C\quad(k\geq0),
$$
where $I$ is the <identity matrix>. This <Markov chain> is irreducible, but each state's <period of a state in a Markov chain> is two. Every destination is reachable, yet a given destination cannot be reached at every sufficiently large step count. Starting at $c_1$ produces alternating one-time <probability distributions>. See https://ocw.mit.edu/courses/18-445-introduction-to-stochastic-processes-spring-2015/2edaa8542469ce692226813a8bd1ec88_MIT18_445S15_lecture2.pdf[Hao Wu's MIT lecture 2, irreducibility and periods] for the definitions.
Adding a <holding probability of a Markov chain> $\varepsilon$ at each state, with $0<\varepsilon<1$, gives
$$
C_\varepsilon=\varepsilon I+(1-\varepsilon)C.
$$
The arrows between the two states remain, so the <Markov chain> remains irreducible. A positive one-step return makes it an <aperiodic Markov chain>. At $\varepsilon=1/2$, both rows are $(1/2,1/2)$ and $C_{1/2}^n=C_{1/2}$ for every $n\geq1$: the initial state is forgotten after one step. At $\varepsilon=1$, however, both states become <absorbing states>, giving two separate <communicating classes> and losing irreducibility.
For a <finite Markov chain>, irreducibility guarantees a unique <stationary distribution> with positive weight at every state. Adding <aperiodicity> guarantees convergence $\mu_0P^n\to\pi$ for every initial <probability distribution>; see https://ocw.mit.edu/courses/18-445-introduction-to-stochastic-processes-spring-2015/5bd4774f613aa28bd111c36f3a3beeed_MIT18_445S15_lecture4.pdf[Hao Wu's MIT lecture 4, convergence theorem]. The <Markov chain ergodic theorem> gives convergence of empirical visit frequencies even for an irreducible periodic <Markov chain>. These results explain why checking connectivity is a useful first step before studying equilibrium. Conversely, any <absorbing state> prevents irreducibility if there is another state: it cannot reach that state. The one-state <Markov chain> is the exception.
Back to article page
