Markov chains

Our sampling-based guarantees so far mostly assumed independent draws. Many random processes are not like that, and their dependence unfolds in time: tomorrow’s weather depends on today’s, the next word on the previous ones, the next page a reader visits on the current page, the next state of a sampler on the current state. A Markov chain is the simplest model of such dependence: the future depends on the past only through the present. It is simple enough to analyse completely and rich enough to describe n-gram language models, web search and the samplers of the last two notes of the course.

Notation. $X_0, X_1, X_2, \dots$ take values in a finite set of states $\{1, \dots, K\}$. $P$ is the $K \times K$ transition matrix, $P_{ij} = P(X_{t+1} = j \mid X_t = i)$; each row sums to 1. A distribution over states is a row vector $\pi$.

The Markov property#

A sequence is a Markov chain if

$$P(X_{t+1} = j \mid X_t = i, X_{t-1}, \dots, X_0) = P(X_{t+1} = j \mid X_t = i) = P_{ij} .$$

The first equality is the Markov property: the present state contains everything about the past that matters for the future. The second is a separate assumption, time homogeneity: the transition rule $P_{ij}$ is the same at every time $t$. All chains in this note are finite and time-homogeneous. The reverse process that generates samples in a diffusion model is Markov but not homogeneous, since its transition rule changes from step to step (MCMC note). A three-state weather model, with sunny days followed by sunny days 70% of the time, is a Markov chain with

$$P = \begin{pmatrix} 0.7 & 0.2 & 0.1 \\ 0.3 & 0.4 & 0.3 \\ 0.2 & 0.3 & 0.5 \end{pmatrix}$$

(rows and columns: sunny, cloudy, rainy). By the law of total probability, the distribution of the next state is the current distribution times the matrix:

$$\pi_{t+1} = \pi_t P, \qquad \pi_t = \pi_0 P^t .$$

The entry $(P^t)_{ij}$ is the probability of being in $j$ after $t$ steps from $i$. Starting from a sunny day:

Figure

A Markov chain for the weather

Stationary distributions#

A distribution $\pi$ with

$$\pi P = \pi$$

is stationary: if the chain starts in it, it stays in it. It is a left eigenvector of $P$ with eigenvalue 1, normalized to sum to 1, and it can be found by solving the linear system $\pi P = \pi$, $\sum_i \pi_i = 1$. For the weather chain $\pi = (21/46, 13/46, 12/46) = (0.457, 0.283, 0.261)$: in the long run 46% of days are sunny.

The figure suggests more: from a sunny start the distribution approaches $\pi$ within ten days. That holds for every starting distribution under two conditions:

• Irreducible: every state can be reached from every other.
• Aperiodic: the chain does not cycle with a fixed period. A chain that alternates deterministically between two states has the stationary distribution $(1/2, 1/2)$ but never approaches it from a fixed start.

For a finite irreducible aperiodic chain, $\pi_t \to \pi$ from any start, and the ergodic theorem, the law of large numbers for Markov chains, says that the share of time the chain spends in each state converges to $\pi$ along a single long run. The speed is set by the second largest absolute eigenvalue of $P$: the distance to $\pi$ shrinks roughly like $\lvert \lambda_2 \rvert^t$, here $0.473^t$, so ten steps reduce it by a factor of about 1,800. The number of steps needed to get close is the mixing time, the central quantity for the samplers of the MCMC note.

Language models as Markov chains#

A bigram language model is a Markov chain whose states are words: $P_{ij}$ is the probability that word $j$ follows word $i$, estimated from counts. Generating text from it is running the chain. For a bigram chain fitted to one long text, the stationary distribution is approximately the unigram word frequency: each word is followed by a word, and preceded by one, as often as it occurs, except at the two ends of the text, so the unigram frequencies satisfy the stationarity equation up to these boundary terms. Text made of separate sentences needs an end-of-sentence token that leads back to a start state, or the chain stops. An n-gram model with $n > 2$ is a Markov chain whose states are contexts of $n - 1$ words; its stationary distribution is over contexts, and the unigram frequency is its marginal for a single position of the context. Shannon’s 1948 paper generated “English” this way, from letter and word chains of increasing order, and the n-gram language models note builds such models from data.

A transformer language model is a Markov chain too, but on a far larger state: the whole context window. The Markov property is a statement about what the state contains, and making the state richer is how sequence models acquire longer memory.

PageRank#

A reader who follows a random link from each page performs a random walk, a Markov chain on the pages. Pages that many walks visit often are important; their importance is the stationary distribution. Two fixes make the chain well defined, irreducible and aperiodic: with probability $0.15$ the reader jumps to a random page instead of following a link (and always jumps from a page without links). The stationary distribution of that chain is PageRank, the ranking signal behind the early Google search engine:

Figure

PageRank is the stationary distribution of a random walk

The example shows what distinguishes PageRank from counting links: a page is important if important pages link to it. C has the most incoming links, but A, with links from C and D, is almost as important, because C sends all its weight to A.

Hitting probabilities: the gambler’s ruin#

Some chains have absorbing states that are never left, and the question is which one is reached first. A gambler with 3 coins bets one coin at a time on a fair game and stops at 0 or at 10. Let $h_a$ be the probability of reaching 10 from $a$; conditioning on the first bet gives $h_a = \frac12 h_{a+1} + \frac12 h_{a-1}$ with $h_0 = 0$, $h_{10} = 1$, so $h_a = a/10$ and $h_3 = 0.3$. The expected number of bets is $a(10 - a) = 21$. A slightly unfavourable game, winning each bet with probability $0.49$, lowers the chance to $0.259$; starting from 50 coins with a target of 100 it is only $0.119$, not one half: over a long game a small edge compounds. The same first-step equations give hitting times and absorption probabilities for any chain, from customer funnels to the expected length of a random walk.

What changed#

	Independent samples	Markov chains
Dependence	none	the next state depends on the current one: $P_{ij}$
Distribution over time	constant	$\pi_t = \pi_0 P^t$
Long run	the law of large numbers	stationary $\pi = \pi P$; the ergodic theorem for time averages
Speed	$1/\sqrt n$	also the mixing time, set by $\lvert \lambda_2 \rvert$
Examples		n-gram models, PageRank, random walks, MCMC

Limitations#

• The Markov property is a modelling choice. Real processes have longer memory; enlarging the state (the last $n$ words, the full context) restores the property at the cost of a much larger state space.
• Convergence can be slow. Chains with bottlenecks, such as two clusters of states joined by rare transitions, can take a very long time to mix, and a single run may show no sign of it.
• Finite states hide subtleties. Infinite or continuous state spaces need conditions (recurrence, positive recurrence) that the finite case gets for free.

What you should remember#

• Markov property: the future depends on the past only through the present; $P_{ij} = P(X_{t+1} = j \mid X_t = i)$.
• Distributions evolve by $\pi_{t+1} = \pi_t P$; $(P^t)_{ij}$ is the $t$-step transition probability.
• Stationary: $\pi P = \pi$. For finite irreducible aperiodic chains, $\pi_t \to \pi$ from any start and time averages converge to $\pi$.
• The second largest eigenvalue in absolute value sets the speed: distance to $\pi$ $\approx \lvert \lambda_2 \rvert^t$.
• n-gram models and PageRank are Markov chains; PageRank is the stationary distribution of a random surfer with teleportation.
• Absorption probabilities and hitting times solve first-step equations; in the fair gambler’s ruin with target $N$, $h_a = a/N$.

Code#

The weather chain, its stationary distribution and a long run, PageRank, and the gambler’s ruin:

import numpy as np

# the weather chain: distributions after 1, 2 and 10 days from a sunny start
P = np.array([[0.7, 0.2, 0.1], [0.3, 0.4, 0.3], [0.2, 0.3, 0.5]])
pi = np.array([1.0, 0.0, 0.0])
for t in range(11):
    if t in (1, 2, 10):
        print(t, pi.round(3))
    pi = pi @ P
# 1 [0.7 0.2 0.1] | 2 [0.57 0.25 0.18] | 10 [0.457 0.283 0.261]

# the stationary distribution solves pi P = pi with sum 1; the eigenvalues set the speed
A = np.vstack([P.T - np.eye(3), np.ones(3)])
stationary = np.linalg.lstsq(A, np.array([0, 0, 0, 1.0]), rcond=None)[0]
print(stationary.round(4), (np.array([21, 13, 12]) / 46).round(4))   # [0.4565 0.2826 0.2609] twice
print(np.sort(np.abs(np.linalg.eigvals(P))).round(3))                # [0.127 0.473 1.   ]

# the ergodic theorem: the share of days in each state along one long run
rng = np.random.default_rng(0)
x, counts = 0, np.zeros(3)
for _ in range(100_000):
    counts[x] += 1
    x = rng.choice(3, p=P[x])
print((counts / counts.sum()).round(3))                               # [0.459 0.281 0.259]

# PageRank of five pages by power iteration, damping 0.85
links = {0: [1, 2], 1: [2], 2: [0], 3: [0, 2], 4: [3, 2]}
M = np.zeros((5, 5))
for i, outs in links.items():
    M[i, outs] = 1 / len(outs)
G = 0.85 * M + 0.15 / 5
r = np.full(5, 0.2)
for _ in range(200):
    r = r @ G
print(r.round(3))                                                     # [0.367 0.186 0.375 0.043 0.03 ]

# gambler's ruin: the probability of reaching N before 0 from a, winning each bet with probability p
ruin = lambda p, a, N: a / N if p == 0.5 else (1 - ((1 - p) / p) ** a) / (1 - ((1 - p) / p) ** N)
print(ruin(0.5, 3, 10), round(ruin(0.49, 3, 10), 3), round(ruin(0.49, 50, 100), 3))   # 0.3 0.259 0.119

Next#

The ergodic theorem says that a long run of a chain samples its stationary distribution. Turned around, this is a way to sample from a distribution that cannot be sampled directly: build a chain whose stationary distribution is the target. Before that idea, the next note collects the direct methods of Monte Carlo: inverse transforms, rejection sampling and importance sampling, and the variance that decides whether they work.

References#

• J. R. Norris. Markov Chains. Cambridge University Press, 1997. Chapter 1 (discrete-time chains, hitting probabilities, stationary distributions, convergence, the ergodic theorem).
• D. A. Levin, Y. Peres, E. L. Wilmer. Markov Chains and Mixing Times, 2nd ed. American Mathematical Society, 2017. Chapters 1, 4 and 12 (stationary distributions, mixing, the spectral gap).
• C. E. Shannon. A Mathematical Theory of Communication. Bell System Technical Journal, 27(3), 1948. Markov approximations to English.
• S. Brin, L. Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30, 1998.