Irreducible Markov Chain

A Markov chain is irreducible if, for every pair of states $i,j\in S$, there exists some $n\ge 0$ such that $p_{ij}^{(n)}>0$, that is, $j$ is reachable from $i$ in a finite number of steps (and, by the same logic applied in reverse, $i$ is reachable from $j$). States satisfying this mutual-reachability condition are said to communicate, and communication is an equivalence relation partitioning the state space into communicating classes. A chain is irreducible exactly when it has a single communicating class, covering the entire state space. Irreducibility, combined with positive recurrence and aperiodicity, is the standard sufficient condition for a unique stationary distribution to exist and for the chain to be ergodic.

• Checking irreducibility is usually the very first step in analyzing any Markov chain, without it, the chain may have several disconnected 'sub-chains' each with its own separate long-run behavior, and speaking of 'the' stationary distribution stops making sense.
• A reducible chain can still be perfectly well-defined and useful, e.g. a chain with an absorbing state deliberately isn't irreducible, since once absorbed the chain can never return to reach other states, the property to check depends on what question is being asked.
• Irreducibility is checked directly from the transition matrix's structure (or, informally, the state-transition diagram): if the diagram, viewed as a directed graph, is strongly connected, the chain is irreducible.