5.5 Stochastic Matrices and the Steady State

The last section ended on a rule: an eigenvalue strictly larger in absolute value than every other decides the long run. Almost always that means growth without bound or decay to nothing. The interesting case is a dominant eigenvalue of exactly $1$, with every other eigenvalue smaller than $1$ in absolute value — the long run then goes somewhere and stays.

Model a system that is always in one of three states, and let the numbers $M_{ij}$ be the probability of moving to state $i$ given that you are currently in state $j$. Take

$$M = \begin{pmatrix} 0.6 & 0.3 & 0.2 \\ 0.4 & 0.5 & 0.2 \\ 0 & 0.2 & 0.6 \end{pmatrix}$$

Read the columns: from state 1, the chances of going to states 1, 2, 3 are $0.6$, $0.4$, $0$ — you never jump from state 1 to state 3 in a single step. Each column sums to $1$, because from wherever you are you must end up somewhere. A matrix with non-negative entries whose columns each sum to $1$ is called stochastic.

A distribution $\mathbf{x} = (x_1, x_2, x_3)$ records the probability of being in each state; its entries are non-negative and sum to $1$, so distributions form a triangle inside the plane $x + y + z = 1$. Applying $M$ advances the system one step, and the column condition is exactly what guarantees the result is another distribution — the entries of $M\mathbf{x}$ sum to $1$ whenever $\mathbf{x}$'s do.

Explore in 3D (opens in a new tab)

A small semi-transparent sloping triangle, the set of all probability distributions over three states, with a white line marking one edge of the triangle where the third probability is zero. A short green marker shows the chosen starting distribution, set by two independent sliders - it is a genuine distribution, and sits on the triangle, only while the two slider values sum to at most one; past that the third probability goes negative and the marker leaves the triangle. An amber segment runs from the green marker to where one step of the chain sends the start. A red dot marks the steady state at (0.4, 0.4, 0.2). Wherever the start is placed, the amber segment runs from the marker toward the red dot, and when the start is dialed onto the red dot the segment shrinks to nothing.

Explore the figure

1. At the defaults $s = 0.1$, $a = 0.1$ — a system almost certainly in state 3 — the amber segment is long. One step takes this start to $(0.25, 0.25, 0.5)$, a displacement of $(+0.15, +0.15, -0.30)$: probability is draining out of state 3 and splitting evenly between states 1 and 2.
2. Drag the sliders to $s = 0.4$, $a = 0.4$. The segment shrinks to nothing. That is the steady state: one step changes it not at all, which is what "steady" means.
3. Move several notches away from those values in any direction — try $s = 0.5$, $a = 0.4$. The segment reappears, running from the green marker back toward the red dot. Every start is pulled the same way.
4. Try a corner, $s = 1$, $a = 0$ — the system definitely in state 1. One step gives $(0.6, 0.4, 0)$, which is still on the edge where state 3 has probability zero: the segment runs along that white edge rather than into the interior, because $M$ has a $0$ in the row-3, column-1 position and you cannot reach state 3 from state 1 in a single step. Take a second step and the interior opens up; the destination is unchanged either way.

The steady state is an eigenvector

A distribution that a step leaves alone satisfies $M\boldsymbol\pi = \boldsymbol\pi$ — which is the eigenvector equation for eigenvalue $1$. Finding it means solving $(M - I)\boldsymbol\pi = \mathbf{0}$, so the steady state is simply the null space of $M - I$, with one extra condition to pin down the scale: its entries must sum to $1$.

Why should $\lambda = 1$ be available at all? Because the columns of $M$ each sum to $1$, the columns of $M - I$ each sum to $0$. That is a dependency among the rows: adding all three rows of $M - I$ gives the zero row. Dependent rows means a determinant of zero, which means $M - I$ is not invertible, which means its null space contains something other than $\mathbf{0}$. Every stochastic matrix has $1$ as an eigenvalue, and the argument used nothing about the particular numbers.

Be careful about what that buys. It produces a nonzero vector fixed by $M$, and no more. Nothing in the determinant forces that vector's entries to be non-negative, or even to sum to something other than zero so that it could be rescaled to sum to $1$ — and a fixed vector failing either test is not a distribution. That every stochastic matrix does in fact fix a genuine distribution is a separate and harder theorem (Perron–Frobenius), which this book takes on trust. What the argument above settles is the easy half: that there is something to look for.

That division is the last step: $$\boldsymbol\pi = \tfrac{1}{5}(2, 2, 1) = (0.4, 0.4, 0.2)$$, the red dot. Confirm it directly, since the check is short. The first coordinate of $M\boldsymbol\pi$ is $$0.6(0.4) + 0.3(0.4) + 0.2(0.2) = 0.24 + 0.12 + 0.04 = 0.4$$, and the other two work out the same way.

Why everything drifts there

Existence is not convergence. What makes step 3 of the exploration true — that every start is pulled in — is the rest of the spectrum. The eigenvalues of $M$ are $1$, $\tfrac12$ and $\tfrac15$. They are distinct, and eigenvectors belonging to distinct eigenvalues are always independent, so these three form a basis — which is exactly the situation the last section needed in order to write $A = PDP^{-1}$.

Write any starting distribution in that basis. Its $\lambda = 1$ component is some multiple of $\boldsymbol\pi$, and the other two components lie along the remaining eigenvectors. Applying $M$ a total of $k$ times multiplies those pieces by $1^k$, $(\tfrac12)^k$ and $(\tfrac15)^k$. The first piece never moves; the other two shrink by a factor of one half and one fifth at every step, vanishing as $k$ grows. Since the sums stay equal to $1$ throughout, the surviving piece must be $\boldsymbol\pi$ itself. So

$$M^k\mathbf{x} \longrightarrow \boldsymbol\pi \quad \text{for every starting distribution } \mathbf{x}$$

and the rate is governed by the second-largest eigenvalue, $\tfrac12$: in the long run the distance to the steady state roughly halves each step. That is why the amber segment is long far from the red dot and short near it.

An original work of XYZ Homework, built around interactive XYZ 3D figures. Chapters 1–6 follow the topic sequence of Interactive Linear Algebra (Margalit & Rabinoff, Georgia Tech, GNU FDL). Chapter 0's scope (its topics, their order, and the idea each figure shows) follows the Vectors chapter of Ximera's Linear Algebra: An Interactive Introduction. The prose, worked examples and figures were written for this book, which is not affiliated with or endorsed by the authors of either work. License: CC-BY-NC-SA-4.0.