Skip to content
Tutorials Center
My learning

Topics

Lesson 40 of 62 ยท Eigenvalues and Decompositions

Markov Chains and Stochastic Matrices

See how stochastic matrices model Markov chains, find the steady state as the eigenvector for eigenvalue 1, measure convergence speed and handle absorbing chains in Python.

Tomorrow's weather depends on today's. A web surfer's next page depends on the page she is on. A customer is subscribed this month, or cancelled, with probabilities that depend on last month's status. In all of these, the future depends on the present state only, not on the whole history. Such a process is a Markov chain, and linear algebra describes it perfectly: the probabilities of moving between states form a matrix, and one step of the chain is one matrix-vector product.

The big question is "what happens in the long run?" The answer is an eigenvector. This lesson builds the transition matrix, shows why it always has the eigenvalue 1, computes the steady state three different ways, explains how fast the chain converges, and ends with absorbing chains. It builds on matrix multiplication and eigenvalues and eigenvectors, and it prepares you for the PageRank project.

The transition matrix

Suppose a system has n states. Let P[i][j] be the probability of moving to state i from state j. We use this "column" convention so that a probability vector x (non-negative entries that sum to 1) evolves by

x_(t+1) = P @ x_t.

Each column of P lists where one state goes next, so every column sums to 1. A matrix with non-negative entries and column sums equal to 1 is called a column-stochastic matrix. (Many probability books use the transpose, with rows summing to 1 and x as a row vector. The mathematics is identical; just transpose everything.)

A weather model with two states, sunny and rainy: a sunny day is followed by a sunny day with probability 0.9, and a rainy day is followed by a sunny day with probability 0.5. Then

P = [[0.9, 0.5], [0.1, 0.5]].

Start sunny, x_0 = (1, 0). After one day x_1 = (0.9, 0.1). After two: x_2 = P @ x_1 = (0.9*0.9 + 0.5*0.1, 0.1*0.9 + 0.5*0.1) = (0.86, 0.14). And P**k gives the k-step transition probabilities: x_k = P**k @ x_0.

Python Evolve a distribution with P

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that the two different starting points end up at the same distribution. That limit is the steady state.

Why eigenvalue 1 always exists

A column-stochastic matrix always has eigenvalue 1. The reason is a one-line trick: the row vector of all ones, 1^T = (1, 1, ..., 1), satisfies 1^T @ P = 1^T, because each column sums to 1. So 1 is an eigenvector of P^T with eigenvalue 1. A matrix and its transpose have the same eigenvalues, so P has eigenvalue 1 too.

All other eigenvalues satisfy |lambda| <= 1: a probability vector can neither grow nor oscillate with bigger amplitude, because its entries always sum to 1 and stay non-negative.

The Perron-Frobenius theorem sharpens this. If P is regular (some power of P has all entries strictly positive: from any state you can eventually reach any other), then:

  1. The eigenvalue 1 is simple, with an eigenvector whose entries are all positive.
  2. Every other eigenvalue has |lambda| < 1.
  3. For any starting distribution x_0, P**k @ x_0 converges to the unique probability eigenvector pi with P @ pi = pi.
flowchart LR
    A["transition matrix P<br/>columns sum to 1"] --> B["eigenvalue 1 exists"]
    B --> C["P pi = pi<br/>steady state pi"]
    A --> D["other |lambda| < 1<br/>(regular chain)"]
    D --> E["P^k x0 converges to pi"]

The steady state is the eigenvector for eigenvalue 1; the other eigenvalues fade away.

Finding the steady state

The steady state pi solves P @ pi = pi, equivalently (P - I) @ pi = 0 with sum(pi) = 1. For the weather chain the equation is 0.9*pi_1 + 0.5*pi_2 = pi_1, so 0.5*pi_2 = 0.1*pi_1, giving pi_1 = 5*pi_2. With pi_1 + pi_2 = 1: pi = (5/6, 1/6), about (0.8333, 0.1667). In the long run it is sunny five days out of six.

There are three practical methods. The program below uses a 3-state chain.

  1. Eigenvector. Use np.linalg.eig, pick the eigenvalue closest to 1, and rescale the eigenvector to sum to 1.
  2. Linear system. Replace one equation of (P - I) @ pi = 0 by sum(pi) = 1 and solve.
  3. Power iteration. Keep multiplying a start vector by P. This is exactly how PageRank is computed on huge matrices.
Python Three ways to get the steady state

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

How fast does it converge?

Write the start vector in the eigenbasis: x_0 = pi + c_2*v_2 + c_3*v_3 + .... Applying P k times multiplies each eigenvector component by lambda_i**k, so

P**k @ x_0 = pi + c_2*lambda_2**k * v_2 + c_3*lambda_3**k * v_3 + ...

All the terms except pi die out, and the slowest dying is the one with the second largest eigenvalue magnitude. The error shrinks roughly like |lambda_2|**k. For the weather chain, the eigenvalues are 1 and trace - 1 = 1.4 - 1 = 0.4, so the error shrinks by a factor of 0.4 each day: after 10 days it is about 0.4**10, roughly one ten-thousandth. A chain with |lambda_2| close to 1 mixes slowly; this is why a "bottleneck" in a network, such as two dense communities joined by one thin link, makes random walks slow to settle.

Python Convergence rate and the second eigenvalue

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error ratio settles at exactly 0.4 for the weather chain, as predicted. The slow chain needs hundreds of steps for the same accuracy.

Absorbing chains

Some states trap the chain forever: a customer who has cancelled, a gambler who is broke. A state with P[i][i] = 1 is absorbing. In an absorbing chain, split the states into transient ones and absorbing ones. Let Q hold the transitions among transient states. Then

N = (I - Q)**(-1)

is the fundamental matrix. Its entry N[i][j] is the expected number of visits to transient state i when starting from transient state j, and the column sums of N are the expected number of steps before absorption.

Example: a walker moves on positions 0, 1, 2, 3, stepping left or right with probability 1/2 each, and positions 0 and 3 are absorbing. The transient states are 1 and 2, with Q = [[0, 0.5], [0.5, 0]]. Then I - Q = [[1, -0.5], [-0.5, 1]], and N = [[4/3, 2/3], [2/3, 4/3]]. Each column sums to 2, so the expected time before being absorbed is 2 steps from either state. Moreover, the absorbing-state probabilities from state 1 are 2/3 for position 0 and 1/3 for position 3.

Python Absorbing random walk: expected steps and absorption probabilities

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Where Markov matrices are used

  • PageRank: the surfer chain on web pages, damped so the chain is regular. The ranking is the steady state.
  • Customer lifetime and churn models: an absorbing "cancelled" state.
  • Text and speech: n-gram and hidden Markov models.
  • Physics and chemistry: diffusion, reaction networks, and MCMC (Markov chain Monte Carlo), which designs a chain whose steady state is a target distribution.
  • Genetics, queueing, board games (the long-run frequency of landing on each square).

Common mistakes

  • Mixing the row and column conventions: whichever you choose, check which axis sums to 1.
  • Forgetting to normalize the eigenvector: np.linalg.eig returns a unit-length vector, not one summing to 1, and it may have a negative overall sign.
  • Assuming convergence for any chain. A chain that alternates between two states (period 2) has an eigenvalue -1 and oscillates forever, and a chain with disconnected parts has more than one steady state.
  • Picking the eigenvalue "1" by exact comparison with floating-point output; use the closest eigenvalue.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the column convention, what is true of every column of a stochastic matrix P?

    Column j lists the probabilities of moving from state j to each state, so the entries are non-negative and sum to 1.
  2. 2. How is the steady state pi characterized?

    pi is an eigenvector of P for the eigenvalue 1, scaled to be a probability vector.
  3. 3. A regular chain has eigenvalues 1, 0.8 and 0.1. Which one controls how quickly it approaches the steady state?

    The error shrinks like |lambda_2|^k where lambda_2 is the second-largest eigenvalue in magnitude, here 0.8.
  4. 4. What does the fundamental matrix N = (I - Q)^-1 of an absorbing chain give?

    N[i][j] is the expected number of visits to transient state i starting from transient state j. Column sums give the expected time to absorption.

Summary

  • A Markov chain with transition matrix P (columns summing to 1) evolves by x_(t+1) = P @ x_t; k steps use P**k.
  • Every stochastic matrix has eigenvalue 1; the steady state pi solves P @ pi = pi with sum(pi) = 1.
  • For regular chains (Perron-Frobenius) the steady state is unique and every start converges to it at rate |lambda_2|**k.
  • Compute pi by eigenvectors, by a linear solve with a normalization row, or by power iteration.
  • Absorbing chains use N = (I - Q)**(-1) for expected visits, expected absorption time and absorption probabilities.

Next: when a matrix refuses to diagonalize, use Jordan Normal Form and Schur Decomposition.