Markov Chains

Learning Objectives

By the end of this section, you will be able to:

Where You'll Apply This: Search engine ranking (PageRank), text generation, speech recognition, financial modeling, queueing systems, MCMC for Bayesian inference, and reinforcement learning.

The Big Picture

A Markov chain is a mathematical framework for modeling systems that evolve randomly over time, where the future depends only on the present—not the past. This "memoryless" property makes Markov chains both mathematically tractable and surprisingly powerful for modeling real-world phenomena.

Historical Context

Real-World Motivation

Consider these scenarios where the Markov property naturally applies:

1. Weather Modeling: Tomorrow's weather depends primarily on today's weather, not on last week's. A simple model: P(rain tomorrow | sunny today) = 0.2.
2. Web Browsing: A user's next page click depends on the current page, not their browsing history. This insight powers PageRank.
3. Board Games: In Monopoly or Snakes and Ladders, your next position depends only on your current square and the dice roll.
4. Text Generation: In character-level models, the next character depends on recent characters—a Markov chain over the alphabet.

The Markov Property

Intuition: Memorylessness

The essence of a Markov chain is memorylessness: the system's future evolution depends only on its current state, not on how it arrived there. Think of it as the system having "amnesia"—it remembers only where it is now.

Formal Definition

Let $\{X_t\}_{t=0,1,2,\ldots}$ be a sequence of random variables taking values in a finite state space $S = \{1, 2, \ldots, n\}$. This sequence is a Markov chain if it satisfies:

We denote the transition probability from state $i$ to state $j$ as:

For a time-homogeneous Markov chain, these probabilities don't depend on time $t$—the rules of the game stay constant.

Transition Matrices

We collect all transition probabilities into a transition matrix $P$:

The transition matrix has two crucial properties:

• Non-negativity: $p_{ij} \geq 0$ for all $i, j$ (probabilities can't be negative)
• Row-stochastic: $\sum_{j=1}^{n} p_{ij} = 1$ for all $i$ (from any state, you must go somewhere)

Interactive: Matrix Explorer

Explore different transition matrices and see how they affect the stationary distribution. Adjust probabilities and observe the chain's long-run behavior.

Interactive: Chain Simulator

Watch a Markov chain in action. The chain randomly transitions between states according to the transition probabilities. Edge thickness represents transition probability.

Multi-Step Transitions

What's the probability of going from state $i$ to state $j$ in exactly $n$ steps? This is called the n-step transition probability:

The beautiful result: these probabilities come from matrix powers.

Why does this work? Consider 2 steps: to go from $i$ to $j$ in 2 steps, you must pass through some intermediate state $k$:

This is exactly how matrix multiplication works! The pattern extends to any n.

Chapman-Kolmogorov Equation

The Chapman-Kolmogorov equation formalizes how to decompose multi-step transitions through intermediate states:

This equation says: to go from $i$ to $j$ in $m+n$ steps, sum over all possible intermediate states $k$ you could be in after $m$ steps.

Interactive: Chapman-Kolmogorov

Visualize the Chapman-Kolmogorov equation by decomposing multi-step transitions through intermediate states. See how direct computation matches the sum over all paths.

Classification of States

States in a Markov chain can be classified based on their long-run behavior. This classification determines the chain's convergence properties.

Stationary Distribution

A probability distribution $\boldsymbol{\pi} = (\pi_1, \pi_2, \ldots, \pi_n)$ over states is called a stationary distribution if it satisfies:

Breaking this down component-wise:

This is a left eigenvector equation: $\boldsymbol{\pi}$ is a left eigenvector of $P$ with eigenvalue 1.

Interactive: Convergence to Stationary Distribution

Watch how any initial distribution converges to the unique stationary distribution as we iterate. The total variation distance shows how quickly convergence occurs.

The Ergodic Theorem

For an ergodic (irreducible and aperiodic) Markov chain with stationary distribution $\boldsymbol{\pi}$:

Equivalently:

• Time-average interpretation: The fraction of time spent in state $j$ converges to $\pi_j$
• Matrix convergence: $P^n \to \mathbf{1}\boldsymbol{\pi}$ as $n \to \infty$, where each row equals $\boldsymbol{\pi}$
• Expected return time: $\pi_j = 1/\mathbb{E}[T_j]$ where $T_j$ is the return time to state $j$

Applications in Machine Learning

Markov chains are foundational to numerous ML techniques. Understanding them provides deep insight into algorithms you use every day.

PageRank Algorithm

Google's PageRank models web browsing as a Markov chain. A "random surfer" either follows a link on the current page (with probability $\alpha$, typically 0.85) or teleports to a random page (with probability $1-\alpha$).

where $L_{ij} = 1$ if page $i$ links to page $j$, and $\text{out}(i)$ is the number of outgoing links from page $i$.

The teleportation term $(1-\alpha)/n$ ensures the chain is irreducible and aperiodic, guaranteeing a unique stationary distribution. This stationary distribution is the PageRank—pages with high $\pi_j$ are considered more important.

Interactive: PageRank

Watch PageRank in action on a small web graph. Node sizes represent their current rank, and the algorithm converges to the stationary distribution of the random surfer model.

Connection to MCMC

Markov Chain Monte Carlo (MCMC) methods, which you studied in Chapter 19, construct Markov chains whose stationary distribution is a target distribution $\pi(x)$ we want to sample from.

Metropolis-Hastings achieves this by accepting/rejecting proposals based on the ratio $\pi(x')/\pi(x)$. Gibbs sampling uses conditional distributions. Both create Markov chains with the desired stationary distribution.

Python Implementation

Let's implement a Markov chain class from scratch. This implementation includes simulation, computing n-step transitions, and finding the stationary distribution.

If P[0] = [0.7, 0.2, 0.1], state 0 transitions to 0 with prob 0.7, to 1 with prob 0.2, to 2 with prob 0.1

1import numpy as np
2from typing import List, Optional
3
4class MarkovChain:
5    def __init__(self, transition_matrix: np.ndarray,
6                 state_labels: Optional[List[str]] = None):
7        self.P = np.array(transition_matrix)
8        self.n_states = len(self.P)
9        self.labels = state_labels or [str(i) for i in range(self.n_states)]
10
11        # Validate: each row must sum to 1
12        row_sums = self.P.sum(axis=1)
13        if not np.allclose(row_sums, 1.0):
14            raise ValueError("Each row must sum to 1")
15        if np.any(self.P < 0):
16            raise ValueError("Probabilities must be non-negative")
17
18    def step(self, current_state: int) -> int:
19        """Take one step from current state, return next state."""
20        # Sample from the transition probabilities
21        next_state = np.random.choice(
22            self.n_states,
23            p=self.P[current_state]
24        )
25        return next_state
26
27    def simulate(self, initial_state: int, n_steps: int) -> List[int]:
28        """Simulate the chain for n_steps."""
29        trajectory = [initial_state]
30        state = initial_state
31        for _ in range(n_steps):
32            state = self.step(state)
33            trajectory.append(state)
34        return trajectory
35
36    def n_step_transition(self, n: int) -> np.ndarray:
37        """Compute P^n (n-step transition matrix)."""
38        return np.linalg.matrix_power(self.P, n)
39
40    def stationary_distribution(self) -> np.ndarray:
41        """Compute the stationary distribution π where πP = π."""
42        # Find left eigenvector with eigenvalue 1
43        # πP = π ⟺ P^T π^T = π^T
44        eigenvalues, eigenvectors = np.linalg.eig(self.P.T)
45
46        # Find index of eigenvalue closest to 1
47        idx = np.argmin(np.abs(eigenvalues - 1))
48
49        # Get corresponding eigenvector and normalize
50        stationary = np.real(eigenvectors[:, idx])
51        stationary = np.abs(stationary)  # Handle numerical issues
52        stationary = stationary / stationary.sum()
53
54        return stationary
55
56    def empirical_distribution(self, n_steps: int = 10000) -> np.ndarray:
57        """Estimate stationary dist by long-run simulation."""
58        trajectory = self.simulate(0, n_steps)
59        counts = np.bincount(trajectory, minlength=self.n_states)
60        return counts / len(trajectory)

Knowledge Check

Test your understanding of Markov chains with these questions covering key concepts from this section:

Summary