Markov Chains

A Markov chain is a stochastic process where the next state depends only on the current state, not on the history that led to it. The Markov property is the structural assumption underneath HMMs, MDPs, MCMC, n-gram language models, and most of probabilistic time-series modelling. Understanding the chain's stationary behaviour and convergence rate is the prerequisite for the rest.

The Markov property

A discrete-time stochastic process $\{X_t{\}}_{t\ge 0}$ over a state space $\mathcal{S}$ is a Markov chain if

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

For finite $\mathcal{S}$, the chain is fully described by the transition matrix $P$ with $P_{ij}=P(X_{t+1}=j\mid X_t=i)$. Each row sums to 1 — $P$ is a stochastic matrix.

Probability evolution is matrix multiplication: if ${\mathit{\pi }}_t\in {\mathbb{R}}^{|\mathcal{S}|}$ is the row-vector distribution of $X_t$, then ${\mathit{\pi }}_{t+1}={\mathit{\pi }}_{t}P$, and ${\mathit{\pi }}_{t+k}={\mathit{\pi }}_t{P}^k$.

Classifications

States have structure:

• Recurrent — the chain returns to it with probability 1.
• Transient — only visited finitely many times almost surely.
• Absorbing — once entered, never left ($P_{ii}=1$).
• Periodic — return times share a common divisor $>1$.

A chain is irreducible if every state can reach every other; aperiodic if no period $>1$. Irreducible aperiodic chains on a finite state space have a unique stationary distribution ${\mathit{\pi }}^{\ast }$ satisfying ${\mathit{\pi }}^{\ast }P={\mathit{\pi }}^{\ast }$, and they converge to it from any start.

Stationary distribution

The stationary ${\mathit{\pi }}^{\ast }$ is the left eigenvector of $P$ with eigenvalue 1. For finite state spaces it can be solved as a linear system ${\mathit{\pi }}^{\ast }(P-I)=0$ subject to $\sum _i{\pi }_i^{\ast }=1$.

A useful sufficient condition: if there exists $\mathit{\pi }$ with ${\pi }_i{P}_{ij}={\pi }_j{P}_{ji}$ for all $i,j$ (the detailed balance equation), then $\mathit{\pi }$ is stationary. Detailed balance gives reversible chains — the structural building block of MCMC.

Mixing time and the spectral gap

How fast does ${\mathit{\pi }}_t$ approach ${\mathit{\pi }}^{\ast }$? For irreducible aperiodic finite chains, convergence is geometric:

$$\parallel {\mathit{\pi }}_t-{\mathit{\pi }}^{\ast }{\parallel }_{\text{TV}}\le C{\lambda }_2^t,$$

where ${\lambda }_2$ is the second-largest eigenvalue of $P$ in absolute value. The spectral gap $1-|{\lambda }_2|$ is the rate of convergence; the mixing time $t_{\text{mix}}$ is roughly $\log (1/ϵ)/(1-|{\lambda }_2|)$.

The spectral gap is what determines whether MCMC inference is fast or slow. Multimodal target distributions typically produce small gaps and slow mixing; this is one of the central practical problems with MCMC.

MCMC: building chains for inference

Markov Chain Monte Carlo runs the logic in reverse: given a target distribution $\pi$ we want to sample from, construct a chain whose stationary distribution is $\pi$.

• Metropolis-Hastings — propose moves from a proposal distribution $q$, accept with probability $min(1,\pi ({\mathbf{x}}^{\prime })q(\mathbf{x}\mid {\mathbf{x}}^{\prime })/\pi (\mathbf{x})q({\mathbf{x}}^{\prime }\mid \mathbf{x}))$. Detailed balance gives stationarity.
• Gibbs sampling — sample each variable from its conditional given the others. Special case of MH with proposals that are always accepted.
• Hamiltonian MC — use gradient information to take long, low-rejection moves; fast mixing for continuous high-dim targets.

MCMC is the workhorse of Bayesian inference, posterior sampling, and any setting where you can evaluate $\pi$ up to a normalising constant but cannot sample directly.

Where Markov chains appear in ML

• Reinforcement learning — MDPs are Markov chains with actions and rewards.
• Hidden Markov Models — see HMM.
• n-gram language models — text as an order-$n$ Markov chain over tokens.
• MCMC inference — Bayesian posterior sampling.
• PageRank — Google's original ranking is the stationary distribution of a Markov chain on the web graph.
• Chain-of-thought reasoning at inference — autoregressive LM generation is a Markov chain over token sequences (the state being the prefix).

What to read next

• Hidden Markov Models — Markov chains with partial observation.
• MDPs & Bellman Equations — Markov chains with actions and rewards.
• Bayesian Networks — directed graphical models that subsume Markov chains.