5.9 Markov chains

Big idea

Split a population into a few states and describe it by the fraction in each: a column of nonnegative numbers adding to $1$. Suppose that in each period, a fixed proportion of the members of each state moves to each other state. Those proportions form a matrix, and one multiplication advances the whole population by one period.

That is a Markov chain, and it is a discrete dynamical system with two extra features. Every column of the matrix adds to $1$, since everybody who leaves a state has to arrive somewhere. And no entry is negative. Those two conditions force the matrix to have $1$ as an eigenvalue and forbid any eigenvalue larger than $1$ in size.

The consequences are strong. Nothing grows without bound, the eigenvector for $1$ is a distribution that never changes, and under a mild extra condition every starting distribution converges to it. The long-run answer does not depend on where the chain started, and finding it means solving one homogeneous system rather than iterating.

Decoder

If $P$ is a regular stochastic matrix, then $P$ has a unique steady-state vector $\mathbf{q}$, and for any initial probability vector $\mathbf{x}_0$ the chain $\mathbf{x}_{k+1} = P\mathbf{x}_k$ converges to $\mathbf{q}$.

Word by word. “Stochastic” means nonnegative entries and columns summing to $1$. “Regular” means some power of $P$ has every entry strictly positive, that is, after enough steps every state can be reached from every state. “Steady-state vector” means a probability vector $\mathbf{q}$ with $P\mathbf{q} = \mathbf{q}$, so it is an eigenvector for the eigenvalue $1$, normalized to sum to $1$. “Unique” and “for any $\mathbf{x}_0$” together say the starting point is forgotten.

Definitions and results

Probability vector. A vector with nonnegative entries that sum to $1$. Its entries are read as the fractions of a population, or the probabilities of being in each state.

Stochastic matrix. A square matrix whose columns are probability vectors. Column $j$ tells you where the contents of state $j$ go in one step, and it sums to $1$ because nothing is lost.

Markov chain. A sequence of probability vectors with $\mathbf{x}_{k+1} = P\mathbf{x}_k$ for a stochastic $P$. The vector $\mathbf{x}_k$ is the state vector after $k$ steps, and $\mathbf{x}_k = P^k\mathbf{x}_0$.

Stochastic times probability stays probability. If $P$ is stochastic and $\mathbf{x}$ is a probability vector, so is $P\mathbf{x}$. The entries stay nonnegative because nothing negative is involved, and the total stays $1$ because each column contributes its whole weight. So the chain never leaves the set of probability vectors.

One is always an eigenvalue. Columns of $P$ summing to $1$ means the rows of $P^{T}$ sum to $1$, so $P^{T}$ maps the all-ones vector to itself. A matrix and its transpose have the same characteristic polynomial, so $1$ is an eigenvalue of $P$ too. The eigenvector of $P$ for $1$ is generally not the all-ones vector; it has to be computed.

No eigenvalue is larger than one. Every eigenvalue of a stochastic matrix satisfies $|\lambda| \le 1$. Combined with the previous fact, $1$ is always a dominant eigenvalue, which is why the chain settles rather than exploding.

Steady-state vector. A probability vector $\mathbf{q}$ with $P\mathbf{q} = \mathbf{q}$. Find it by solving $(P - I)\mathbf{x} = \mathbf{0}$ for the eigenspace, then scaling the answer so its entries sum to $1$. The scaling step is what makes it a distribution rather than a direction, and forgetting it is the most common mistake here.

Regular stochastic matrix. One with some power having all entries strictly positive. A matrix with all entries positive is regular immediately. A matrix with zeros can still be regular, as long as enough steps connect every state to every other.

Convergence. For a regular stochastic $P$: the steady-state vector is unique, every chain converges to it regardless of $\mathbf{x}_0$, and the powers $P^k$ converge to the matrix with $\mathbf{q}$ in every column. That last statement is the first one in disguise, since column $j$ of $P^k$ is where a population starting entirely in state $j$ ends up.

Regularity is not decoration. The identity matrix is stochastic but not regular, and under it nothing ever moves: every probability vector is a steady state and no starting point is forgotten. Without regularity the theorem’s conclusions can all fail at once.

Speed of convergence. The second largest eigenvalue in absolute value controls how fast the chain settles. With eigenvalues $1$ and $\lambda_2$, the distance to the steady state shrinks by roughly a factor of $|\lambda_2|$ per step.

Worked examples

A two-state chain

Two shops split a town’s customers. Each month, $80$ percent of the first shop’s customers return and $20$ percent switch; $30$ percent of the second shop’s customers switch to the first and $70$ percent stay. Take the state vector as the fractions at the two shops:

$$ P = \begin{bmatrix} 0.8 & 0.3 \\ 0.2 & 0.7 \end{bmatrix} $$

Each column sums to $1$ and every entry is positive, so $P$ is stochastic and regular.

Start with everyone at the first shop, $\mathbf{x}_0 = (1,0)$. Then $\mathbf{x}_1 = (0.8, 0.2)$. Next, $\mathbf{x}_2 = (0.8(0.8) + 0.3(0.2), \; 0.2(0.8) + 0.7(0.2)) = (0.64 + 0.06, \; 0.16 + 0.14) = (0.7, 0.3)$. Continuing gives $\mathbf{x}_3 = (0.65, 0.35)$ and $\mathbf{x}_4 = (0.625, 0.375)$. The entries are closing in on something.

Find the limit exactly. Solve $(P - I)\mathbf{x} = \mathbf{0}$:

$$ P - I = \begin{bmatrix} -0.2 & 0.3 \\ 0.2 & -0.3 \end{bmatrix} $$

The second row is minus the first, so the only condition is $0.2x_1 = 0.3x_2$, giving the eigenspace spanned by $(3,2)$. Scale to sum to $1$: $\mathbf{q} = (0.6, 0.4)$.

Check: $P\mathbf{q} = (0.8(0.6) + 0.3(0.4), \; 0.2(0.6) + 0.7(0.4)) = (0.48 + 0.12, \; 0.12 + 0.28) = (0.6, 0.4)$. It is fixed, and the iterates $0.8$, $0.7$, $0.65$, $0.625$ are indeed approaching $0.6$, halving their distance each step.

Powers converging to the steady state

Keep the same $P$. Its eigenvalues are $1$ and, from the trace $1.5$, also $0.5$. Diagonalizing and collecting terms gives the closed form

$$ P^k = \begin{bmatrix} 0.6 & 0.6 \\ 0.4 & 0.4 \end{bmatrix} + (0.5)^k\begin{bmatrix} 0.4 & -0.6 \\ -0.4 & 0.6 \end{bmatrix} $$

Check it at $k = 1$: the second matrix scaled by $0.5$ has entries $0.2, -0.3, -0.2, 0.3$, and adding gives $(0.8, 0.3; 0.2, 0.7)$, which is $P$. Check it at $k = 2$ against a direct multiplication. Squaring $P$ gives

$$ P^2 = \begin{bmatrix} 0.64 + 0.06 & 0.24 + 0.21 \\ 0.16 + 0.14 & 0.06 + 0.49 \end{bmatrix} = \begin{bmatrix} 0.7 & 0.45 \\ 0.3 & 0.55 \end{bmatrix} $$

and the formula at $k = 2$ gives the first matrix plus $0.25$ times the second, that is $(0.6 + 0.1, \; 0.6 - 0.15; \; 0.4 - 0.1, \; 0.4 + 0.15)$, the same matrix.

The $(0.5)^k$ term vanishes, so $P^k$ converges to the matrix with $\mathbf{q} = (0.6, 0.4)$ in both columns. At $k = 8$ the correction factor is $1/256$, and the columns already agree to two decimal places.

A three-state chain

Let

$$ P = \begin{bmatrix} 0.7 & 0.1 & 0.2 \\ 0.2 & 0.8 & 0.2 \\ 0.1 & 0.1 & 0.6 \end{bmatrix} $$

Every column sums to $1$ and every entry is positive, so $P$ is regular stochastic and a unique steady state exists.

Solve $(P - I)\mathbf{x} = \mathbf{0}$. Multiplying the shifted matrix by $10$ to clear decimals:

$$ 10(P - I) = \begin{bmatrix} -3 & 1 & 2 \\ 2 & -2 & 2 \\ 1 & 1 & -4 \end{bmatrix} $$

Divide the second row by $2$ to get $x_1 - x_2 + x_3 = 0$, so $x_1 = x_2 - x_3$. Substituting into the third row gives $(x_2 - x_3) + x_2 - 4x_3 = 0$, so $2x_2 = 5x_3$. Taking $x_3 = 2$ gives $x_2 = 5$ and $x_1 = 3$. The first row checks out: $-3(3) + 5 + 2(2) = -9 + 9 = 0$.

The entries sum to $10$, so $\mathbf{q} = (0.3, 0.5, 0.2)$.

Check by multiplying: the first entry of $P\mathbf{q}$ is $0.7(0.3) + 0.1(0.5) + 0.2(0.2) = 0.21 + 0.05 + 0.04 = 0.3$; the second is $0.2(0.3) + 0.8(0.5) + 0.2(0.2) = 0.06 + 0.40 + 0.04 = 0.5$; the third is $0.1(0.3) + 0.1(0.5) + 0.6(0.2) = 0.03 + 0.05 + 0.12 = 0.2$. The vector is fixed and its entries sum to $1$, so it is the steady state. In the long run half the population sits in the second state, whatever the starting split was.

Practice

One step of a chain is a matrix-vector product, so start there.

Several steps at once is a matrix power, and the pattern in those powers is the point.

The steady state is an eigenvector for the eigenvalue $1$, found by the usual null space computation and then rescaled to sum to $1$.

Videos

Watch for the argument that $1$ is always an eigenvalue of a stochastic matrix, and for the claim that the other eigenvalues are no larger in size. Those two facts are the reason a Markov chain settles instead of drifting.

Quiz

Six items on stochastic matrices, chain steps, powers, and steady-state vectors.