Irreducible Markov chain

Topic of Classes, recurrence, and reversibility, part of Stochastic processes · Also in Markov chains

Irreducible Markov chain

Type Topic
Taught in Classes, recurrence, and reversibility · Markov chains
Part Stochastic processes · Probability
Questions using it 4

A chain is irreducible when every state can be reached from every other, so that all states form one communicating class. A finite irreducible chain has a unique stationary distribution; with aperiodicity added, P^n converges to it from any start.

In Classes, recurrence, and reversibility

From Classes, recurrence, and reversibility

State j is accessible from i, written i\to j, when p_{ij}^{(n)}>0 for some n\ge 0. The case n=0 counts: every state is accessible from itself. States i and j communicate when each is accessible from the other. Communication is an equivalence relation, so it partitions S into classes. A class is closed when no transition leaves it. A chain with a single communicating class is irreducible. An absorbing state is a closed class of one state, with p_{ii}=1.

In Markov chains

From Markov chains

Theorem 1 (Limiting distribution) Suppose P is the transition matrix of an irreducible aperiodic chain on a finite set. Then there is a unique probability row vector \boldsymbol\pi with \boldsymbol\pi=\boldsymbol\pi P, and for every start i and every state j,

\lim_{n\to\infty}(P^n)_{ij}=\pi_j.

Every row of P^n converges to \boldsymbol\pi. The equations \boldsymbol\pi=\boldsymbol\pi P together with \sum_j \pi_j=1 determine \boldsymbol\pi.

Article: Limiting distribution →

The vector \boldsymbol\pi is the distribution that is unchanged by one more step. Irreducibility keeps the chain from getting stuck in a subset of states. Aperiodicity keeps the distribution from oscillating between two or more patterns; a deterministic two-cycle is irreducible and has no limiting distribution, even though it has a stationary one.

On a small state space the linear system (P^\top-I)\boldsymbol\pi^\top=\mathbf{0} is solved directly, and the solution is scaled so that its entries sum to 1. A null-space routine does the same arithmetic. For the stepping stones this is the vector found above.

Example 1 (A two-state weather chain) Each day is dry or wet. A dry day is followed by a dry day with probability 0.8, and a wet day by a wet day with probability 0.6.

Question. Find the limiting distribution, and the probability that it is dry two days after a wet day.

Solution. With the states in the order dry, wet,

P=\begin{pmatrix}0.8&0.2\\0.4&0.6\end{pmatrix}.

The balance equation for the dry state is \pi_1=0.8\pi_1+0.4\pi_2, so 0.2\pi_1=0.4\pi_2 and \pi_1=2\pi_2. With \pi_1+\pi_2=1, \boldsymbol\pi=(2/3,1/3): in the long run two days in three are dry. Two days after a wet day, the probability of a dry day is the (wet, dry) entry of P^2,

0.4\times0.8+0.6\times0.4=0.56.

For any two-state chain with switching probabilities a (dry to wet) and b (wet to dry), the limit is (b,a)/(a+b), and P^n approaches it geometrically fast, at rate (1-a-b)^n. Here 1-a-b=0.4, so after a week the starting state has almost no influence.

The limiting distribution also describes a single long path. For an irreducible chain on a finite set, the fraction of the first n steps spent in state j converges to \pi_j with probability one, whatever the start. This is a law of large numbers for a dependent sequence. It is what justifies estimating \pi by running one long simulation and counting visits, and it is the fact that Markov chain Monte Carlo rests on.

Figure 1: A simulated symmetric random walk on the integers, p=q=1/2, for 500 steps. It wanders far from zero and returns, with no tendency to settle. On the integers the symmetric walk has no limiting distribution.

A random walk on the non-negative integers, with reflection at 0, shows when a limit exists on an infinite space. From 0 the walk steps to 1 with probability p and stays with probability q=1-p. From j\ge 1 it steps to j+1 with probability p and to j-1 with probability q. The balance equations \boldsymbol\pi=\boldsymbol\pi P give \pi_j=(p/q)^j \pi_0 for j\ge 0. These numbers can be scaled to sum to 1 if and only if p<q, in which case \pi_0=1-p/q and \pi_j=(1-p/q)(p/q)^j. If p\ge q the walk drifts to infinity and no probability vector satisfies the balance equations. The chain still has the Markov property. It simply has no limiting distribution.

Figure 2: The walk with a floor at 0. Top: its transition graph. Bottom: the limiting weights when p/q=1/2, which are \pi_j=(1/2)^{j+1}, a geometric distribution that sums to 1.
Key idea

The next state is drawn from a row of P that depends only on the current state. After many steps an irreducible aperiodic finite chain forgets where it started, and the probability of each state settles on the unique row vector \boldsymbol\pi=\boldsymbol\pi P.

Used in

See also

Communicating classes · Stationary distribution · Aperiodic Markov chain · Finite irreducible chains · Limiting distribution · Recurrence and period · Detailed balance · Return and period

Glossary and index