Tiny Volt19. Markov matrices
The last two chapters ran on powers of a matrix: swings toward the eigenvector of the largest eigenvalue, which gave us power iteration and a closed form for the Fibonacci numbers. This chapter is about a family of matrices whose powers push probability distributions around: Markov matrices.
Suppose a particle hops between a fixed set of states at each tick of a clock, and where it goes next depends only on where it is now. This simple setup shows up everywhere: PageRank, text generation, queueing, board games. Linear algebra turns questions about its long-run behavior into questions about eigenvalues.
19.1 Markov process
You are given a particle and a fixed number of states state 1, state 2, ..., state n. At any time step t the particle is in exactly one state; call it . At time t+1 the state is random, and it depends only on , not on any earlier history. The sequence is then called a Markov process.
Here is a two-state example:
- If the particle is in
state 1:- it stays in
state 1with probability - it moves to
state 2with probability - we can pack these into an array , where entry is the probability of being in state at the next time step
- it stays in
- If the particle is in
state 2:- it moves to
state 1with probability - it stays in
state 2with probability - the array for this state is
- it moves to
So each state contributes one array of length equal to the number of states, holding non-negative values that sum to . Writing each array as a column, the whole process becomes a matrix:
This is a square n-by-n matrix where n is the number of states. Column holds the probabilities of the next state, given that the particle is currently in state . Every column sums to ; such a matrix is called a Markov matrix (or a stochastic matrix).
Different matrices give processes with very different personalities. Compare these three:
Under the particle keeps hopping back and forth at random. Under it alternates between the two states deterministically, forever. Under , once the particle enters state 2 it stays there forever: the second state is absorbing.
19.1.1 Stationary and limiting distributions
Instead of tracking a single particle, it is more revealing to track the whole probability distribution over states as time passes.
In the figures below:
- Each vertical column is the distribution at one time step, read left to right for
- Within a column, each stacked block is one state; the block's height is the probability of that state, and its color encodes the same probability (blue for through red for ), so two similar distributions look similar at a glance.
. After a few steps the columns stop changing: the distribution converges to a fixed set of values regardless of how long we keep going. and the distribution stays locked in place. When this happens, and the same values are reached from any starting distribution, we say the process has a limiting distribution.
Not every process has one. : the two blocks swap at every step and never settle, so no limiting distribution exists. But and nothing changes at all. That start is a stationary distribution of , a distribution the process leaves untouched, even though has no limiting distribution.
It is important to keep the two ideas apart:
- A limiting distribution, if it exists, does not depend on the initial state: the process eventually converges to it no matter where it began. A limiting distribution is always also stationary.
- A stationary distribution may depend on the initial state, as we just saw. Its existence does NOT imply that a limiting distribution exists.
If you prefer thinking about particles rather than probabilities: imagine releasing a large number of particles and letting each one hop independently. The proportion of particles in each state is a proxy for the probability of finding one particle in that state, and it gets more faithful as the number of particles grows.
19.2 Markov process as a matrix
Let's write the Markov matrix generically, with column holding the next-state probabilities out of state :
If the particle is currently in the first state, the probability of it being in the first state is and of any other state is . So the state itself can be written as a vector: . The probabilities at the next time step are then just a matrix-vector product:
Similarly, the probabilities two steps ahead are
In general, if the initial probabilities at t = 0 are given by the vector , the probabilities after steps are
Powers of a matrix again: the long-run behavior of a Markov process is the story of .
19.2.1 Markov matrix and stationary distribution
A stationary distribution is one the process leaves unchanged:
But says exactly that is an eigenvector of with eigenvalue . So a Markov process has a stationary distribution precisely when its matrix has an eigenvalue equal to , and the stationary probabilities are that eigenvector scaled so its entries sum to . (We will see below that a Markov matrix always has the eigenvalue .)
19.3 A Markov matrix preserves the sum of a vector
Each column of sums to . We can say the same thing in one equation: multiplying by a row of ones on the left adds up each column, so
Let's call this row vector , so that . You can think of as a function: feed it a vector and it returns the sum of the entries of , since .
Now take any vector and sum the entries of :
The sum of the entries of equals the sum of the entries of . Multiplying any vector by a Markov matrix preserves the sum of its values. (This is why is again a valid probability vector: the entries still sum to .)
For a 2-by-2 Markov matrix this means an input vector is mapped to another point on the line . We can watch this happen by transforming points on a circle and joining . Every joining segment is : multiplication by can only slide a point along the direction that keeps constant. and the output ellipse changes shape, but the segments stay parallel to that same line.
19.4 The product of two Markov matrices is a Markov matrix
Let and be Markov matrices and let . Since and , we get
The columns of sum to , and its entries are non-negative (sums of products of non-negative numbers), so is a Markov matrix. In particular every power of a Markov matrix is again a Markov matrix.
19.5 Eigenvalues and eigenvectors of a Markov matrix
A Markov matrix has largest eigenvalue equal to ; every other eigenvalue is at most in absolute value.
It is easy to see that is always an eigenvalue. We have , which transposes to , so is an eigenvalue of . And we saw earlier that a matrix and its transpose have the same eigenvalues, so has the eigenvalue too.
Why is it the largest? Suppose some eigenvalue had . We saw in the chapter on powers of a matrix that for large , along the dominant eigenvector, so would blow up in magnitude. But is itself a Markov matrix for every : its entries stay between and , so stays bounded. No blow-up is possible, hence for every eigenvalue, and is the largest.
The eigenvalue showed up here as the fixed point of a Markov process. Next we meet a family of matrices whose only eigenvalues are and : projection matrices, the workhorses behind least squares.