 Irreducible Markov chain

For a finite, time-homogeneous Discrete-time Markov chain with row-stochastic transition matrix $P$, irreducibility meansEquivalently, 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\}$ giveswhere $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 Hao Wu's MIT lecture 2, irreducibility and periods for the definitions.

Adding a holding probability of a Markov chain $\epsilon$ at each state, with $0<\epsilon <1$, givesThe arrows between the two states remain, so the Markov chain remains irreducible. A positive one-step return makes it an aperiodic Markov chain. At $\epsilon =1/2$, both rows are $(1/2,1/2)$ and $C_{1/2}^n=C_{1/2}$ for every $n\ge 1$: the initial state is forgotten after one step. At $\epsilon =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 }_0{P}^n\to \pi$ for every initial probability distribution; see 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.