Markov Chains

Markov chains are one of the most beautiful applications of eigenvalues. The long-run behavior of any Markov chain is determined by a single eigenvector.

What is a Markov chain?

A Markov chain is a system that jumps between states over time. The key property: the next state depends only on the current state, not on the history.

The transitions are captured in a transition matrix T, where T[i,j] is the probability of going from state j to state i. Each column sums to 1.

Evolution over time

If the current distribution over states is a vector π, the distribution after one step is $T\boldsymbol{\pi}$. After k steps: $T^k \boldsymbol{\pi}$.

The stationary distribution

As k → ∞, the distribution converges to a fixed point $\boldsymbol{\pi}^*$ where:

This is exactly an eigenvector equation with eigenvalue 1. The stationary distribution is the eigenvector of T corresponding to λ = 1. Every column-stochastic matrix has exactly one such eigenvector (under mild conditions).

Speed of convergence

The second eigenvalue |λ₂| controls how fast the chain mixes. If |λ₂| is close to 1, convergence is slow (nearly reducible states). If |λ₂| is small, convergence is fast.

Try it

Set the transition probabilities and initial distribution. The bars show the distribution at each step converging toward the stationary distribution (dashed). "Slow mixing" has a large second eigenvalue — notice how many more steps it takes.

import numpy as np

T = np.array([[0.9, 0.2], [0.1, 0.8]])  # transition matrix (columns sum to 1)

# Stationary distribution = eigenvector with eigenvalue 1
eigenvalues, eigenvectors = np.linalg.eig(T)
idx = np.argmin(np.abs(eigenvalues - 1))
stationary = eigenvectors[:, idx]
stationary /= stationary.sum()  # normalize
print(stationary)  # [0.667, 0.333]

# Or: iterate until convergence
pi = np.array([0.5, 0.5])
for _ in range(100):
    pi = T @ pi
print(pi)  # same result