So far our randomness has been static. A stochastic process adds time: a sequence of random variables that evolve and depend on one another. The most important kind — the Markov chain — forgets everything but the present, yet is rich enough to model language, web surfing, and physical systems. Markov chains also power Markov chain Monte Carlo (MCMC), the algorithm that made Bayesian inference practical and that quietly underlies modern generative models.

Stochastic processes

A stochastic process is a collection of random variables \(\{X_t\}\) indexed by time \(t\). Examples: a random walk, the price of a stock, the sequence of words in a sentence, the state of a game.

Markov chains

A process has the Markov property if the future depends on the past only through the present: \[P(X_{t+1}\given X_t,X_{t-1},\dots,X_0)=P(X_{t+1}\given X_t).\] A Markov chain on a finite state space is specified by a transition matrix \(\mathbf{P}\) whose entry \(P_{ij}=P(X_{t+1}=j\given X_t=i)\); each row sums to \(1\).

“Memoryless” does not mean the past is irrelevant — it means the present state summarizes all relevant history. Where you go next depends only on where you are now, not the route that brought you. This is a modeling assumption (often approximate), and it is exactly the trade that makes the math tractable: one matrix \(\mathbf{P}\) captures the entire dynamics, and multiplying by it advances the distribution one step.

Stationary distributions and convergence

A distribution \(\boldsymbol{\pi}\) over states is stationary if it is unchanged by a transition: \(\boldsymbol{\pi}\mathbf{P}=\boldsymbol{\pi}\). It is the left eigenvector of \(\mathbf{P}\) with eigenvalue \(1\) — linear algebra reappearing.

For a well-behaved (irreducible, aperiodic) chain, the distribution over states converges to the stationary distribution \(\boldsymbol{\pi}\) regardless of where it started — the chain “forgets” its initial condition. This convergence is the magic that MCMC exploits: design a chain whose stationary distribution is the one you want to sample from, run it long enough, and its states become samples from that target. PageRank is exactly this — the stationary distribution of a random web-surfer’s Markov chain.

Monte Carlo and MCMC

Monte Carlo methods estimate quantities by random sampling: to approximate \(\E[g(X)]\), draw samples and average (justified by the LLN, Chapter [ch:limit]). But how do you sample from a complicated, high-dimensional distribution — like a Bayesian posterior whose normalizing evidence integral is intractable?

Markov chain Monte Carlo builds a Markov chain whose stationary distribution is the target \(p\), then uses the chain’s trajectory as (correlated) samples. The Metropolis–Hastings algorithm proposes a move and accepts it with a probability that depends only on a ratio \(p(x')/p(x)\) — so the intractable normalizing constant cancels. Gibbs sampling updates one coordinate at a time from its conditional.

The brilliance of Metropolis–Hastings is that you never need the normalizing constant — only ratios of densities, which you can compute. This is what made full Bayesian inference practical: you can sample from a posterior known only up to proportionality (likelihood \(\times\) prior), exactly the situation Chapter [ch:bayesian] left us in. Run the chain, discard an initial “burn-in,” and the remaining states approximate the posterior.

Markov chains and Monte Carlo are everywhere in modern AI. MCMC is the classical engine of Bayesian machine learning, sampling posteriors that have no closed form. Markov chains model sequences — the \(n\)-gram language models that preceded neural ones are literally Markov chains over words, and reinforcement learning formalizes the world as a Markov decision process. Most strikingly, diffusion models — today’s leading image generators — are Markov chains: a forward chain gradually adds Gaussian noise, and a learned reverse chain removes it step by step to generate samples. The “sampling” in a diffusion or autoregressive model is a Monte Carlo walk through a learned probability distribution.

import numpy as np
# Stationary distribution as the eigenvector of P^T with eigenvalue 1
P = np.array([[0.7, 0.3],
              [0.5, 0.5]])
vals, vecs = np.linalg.eig(P.T)
pi = np.real(vecs[:, np.argmin(np.abs(vals-1))]); pi = pi/pi.sum()
print(pi.round(3))                  # ~ [0.625, 0.375]

# Metropolis-Hastings sampling from an unnormalized target p(x) ∝ e^{-x^2/2}
logp = lambda x: -x**2/2            # only need it up to a constant!
x, samples = 0.0, []
for _ in range(200_000):
    xp = x + np.random.normal(0, 1)
    if np.log(np.random.rand()) < logp(xp) - logp(x):
        x = xp
    samples.append(x)
print(round(np.mean(samples), 2), round(np.std(samples), 2))   # ~0, ~1 (standard normal)

Chapter summary

  • A stochastic process is random variables evolving in time; a Markov chain depends on the past only through the present.

  • A chain is described by its transition matrix \(\mathbf{P}\); the stationary distribution solves \(\boldsymbol\pi\mathbf{P}=\boldsymbol\pi\).

  • Well-behaved chains converge to \(\boldsymbol\pi\) regardless of start — the basis of PageRank and MCMC.

  • Monte Carlo estimates expectations by sampling; MCMC (Metropolis–Hastings, Gibbs) samples hard distributions using only density ratios.

  • These power Bayesian posterior sampling, \(n\)-gram/RL/MDP models, and the forward/reverse chains of diffusion models.