Lesson overview | Lesson overview | Next part

Markov Chains: Part 1: Intuition to 9. ML Deep Dive

1. Intuition

1.1 What Is a Markov Chain?

A Markov chain is a sequence of random variables $X_0, X_1, X_2, \ldots$ taking values in a state space $\mathcal{S}$, where the future is independent of the past given the present. Formally, for every $n \geq 0$ and every state $j \in \mathcal{S}$:

$$P(X_{n+1} = j \mid X_0, X_1, \ldots, X_n) = P(X_{n+1} = j \mid X_n)$$

This is the Markov property: the current state $X_n$ is a sufficient statistic for predicting $X_{n+1}$. No matter how long the history, knowing only the present gives as much information about the future as knowing the entire past trajectory.

Why memorylessness is powerful. At first glance, the Markov property looks like a restriction - real systems do have memory. But three things make it useful:

1. Many systems genuinely satisfy it. A fair die, re-rolled at each step, is Markov (no memory). A chess position captures all relevant game state (Markov). An LLM's key-value cache provides sufficient statistics for the next token (Markov, given the KV cache).

2. Higher-order Markov chains reduce to first-order. A chain where $X_{n+1}$ depends on $X_n$ and $X_{n-1}$ can be converted to a first-order chain on the augmented state $(X_n, X_{n-1})$. So first-order is universal given a rich enough state space.

3. The mathematics is tractable. Transition probabilities only involve pairs of states, so the full dynamics are captured by a matrix rather than an exponentially large conditional probability table.

The mental picture: Imagine a particle hopping between states on a graph. At each step, it looks only at which node it currently occupies, then jumps to a neighbouring node with probability given by the edge weights. The history of how it got to the current node is irrelevant - only where it is now matters.

For AI: Every autoregressive language model generates tokens one at a time, each conditioned on all previous tokens. Given a context window of length $n$, the distribution over the next token is fully specified by the current state (the context). This is precisely the Markov property with state space = all possible contexts of length $\leq n$.

1.2 Everywhere in AI

Markov chains appear as the backbone of several major AI paradigms:

Language generation: GPT, LLaMA, and every autoregressive transformer generates text via a Markov chain. The state is the current context (the key-value cache), the transition is the softmax over the vocabulary, and the stationary distribution - if it exists - characterises what the model "talks about" at equilibrium.

PageRank: Google's original ranking algorithm computes the stationary distribution of a Markov chain on the web graph, where each page links to others. A page is important if the random surfer spends a lot of time there at stationarity. Power iteration on the transition matrix gives the PageRank vector.

Reinforcement learning: A Markov Decision Process (MDP) is a Markov chain with actions. The agent's policy induces a Markov chain over states, and the value function is the expected discounted return from each state - computable from the stationary properties of this chain. TD-learning, Q-learning, and policy gradient methods all exploit the Markov structure.

Bayesian inference via MCMC: When the posterior distribution $\pi(\theta | \mathcal{D})$ is intractable, MCMC constructs a Markov chain whose stationary distribution is exactly $\pi$. Running the chain for long enough generates samples that represent the posterior. Metropolis-Hastings and Gibbs sampling are the two canonical MCMC algorithms.

Speech and sequence modelling: Hidden Markov Models (HMMs) model sequences where the true state (e.g., phoneme) is latent. The forward-backward algorithm and Viterbi decoder exploit the Markov structure to perform efficient inference.

Diffusion models: The DDPM forward process $x_0 \to x_1 \to \cdots \to x_T$ is a Markov chain where each step adds Gaussian noise. The learned reverse process is a Markov chain running backwards in time. The SDE perspective (Section06 Stochastic Processes) gives the continuous-time version.

1.3 Historical Timeline

1.4 Taxonomy of Markov Chains

Markov chains are classified along two dimensions:

State space: Finite ($\mathcal{S} = \{1,\ldots,N\}$), countably infinite ($\mathcal{S} = \mathbb{Z}^+$), or continuous ($\mathcal{S} = \mathbb{R}^d$). Most of this section treats finite or countably infinite state spaces; MCMC typically targets continuous spaces.

Time: Discrete ($n = 0, 1, 2, \ldots$) or continuous ($t \geq 0$). Discrete-time chains are developed in Section2-Section6; continuous-time chains in Section7.

Time-homogeneous vs. inhomogeneous: If transition probabilities do not depend on $n$ - $P(X_{n+1}=j|X_n=i) = P_{ij}$ for all $n$ - the chain is time-homogeneous. Almost all chains in this section are time-homogeneous.

---

2. Formal Definitions

2.1 The Markov Property

Recall: Conditional independence $X \perp Y \mid Z$ was defined in Section03 Joint Distributions. The Markov property is conditional independence of the future from the past, given the present.

Definition (Discrete-Time Markov Chain). A sequence $\{X_n\}_{n \geq 0}$ of random variables on a measurable state space $(\mathcal{S}, \mathcal{B})$ is a (time-homogeneous) Markov chain if for all $n \geq 0$ and all measurable $B \subseteq \mathcal{S}$:

$$P(X_{n+1} \in B \mid X_0, X_1, \ldots, X_n) = P(X_{n+1} \in B \mid X_n) =: K(X_n, B)$$

The function $K : \mathcal{S} \times \mathcal{B} \to [0,1]$ is called the transition kernel or transition probability. For finite $\mathcal{S} = \{1,\ldots,N\}$, it is encoded by the $N \times N$ transition matrix $P$ with $P_{ij} = P(X_{n+1}=j \mid X_n=i)$.

Equivalent formulation via conditional independence: The Markov property is equivalent to:

$$X_{n+1} \perp (X_0, \ldots, X_{n-1}) \mid X_n$$

This is the cleanest statement: given the present $X_n$, the future $X_{n+1}$ is independent of the entire past $(X_0,\ldots,X_{n-1})$. More generally, the strong Markov property asserts this holds for stopping times: $X_{\tau+1} \perp \mathcal{F}_\tau \mid X_\tau$ for any stopping time $\tau$.

Initial distribution: The full law of the chain is specified by:

1. The initial distribution $\mu_0$ with $\mu_0(i) = P(X_0 = i)$
2. The transition matrix $P$ with $P_{ij} \geq 0$ and $\sum_j P_{ij} = 1$ for all $i$

Together, $(\mu_0, P)$ determines all finite-dimensional distributions.

2.2 Transition Matrix

For a finite state space $\mathcal{S} = \{1,\ldots,N\}$, the transition matrix $P$ is an $N \times N$ stochastic matrix: every row sums to 1, all entries are non-negative. The $(i,j)$ entry is the probability of jumping from state $i$ to state $j$ in one step.

Distribution at step $n$: If $\mu^{(n)}$ is the row vector of probabilities at step $n$, then:

$$\mu^{(n)} = \mu^{(0)} P^n$$

The distribution evolves by left-multiplying by $P$ at each step. In component form: $\mu^{(n+1)}_j = \sum_i \mu^{(n)}_i P_{ij}$.

$n$-step transition probabilities: The probability of going from $i$ to $j$ in exactly $n$ steps is the $(i,j)$ entry of $P^n$:

$$P^{(n)}_{ij} = P(X_n = j \mid X_0 = i) = (P^n)_{ij}$$

Computing $P^n$ via matrix exponentiation (eigendecomposition or repeated squaring) is the core computational task for Markov chains.

Non-example: A matrix with a row summing to more than 1, or with any negative entry, is NOT a valid transition matrix. A doubly-stochastic matrix (both rows and columns sum to 1) is a transition matrix, and its stationary distribution is uniform.

For AI: In a language model with vocabulary size $V$, the transition matrix $P$ has size $V \times V$ where $P_{ij}$ = probability of token $j$ following token $i$ (bigram model). Real LLMs use much richer state spaces (the context window), but the Markov structure is the same.

2.3 Chapman-Kolmogorov Equations

Theorem (Chapman-Kolmogorov). For any $m, n \geq 0$ and states $i, j$:

$$P^{(m+n)}_{ij} = \sum_{k \in \mathcal{S}} P^{(m)}_{ik} P^{(n)}_{kj}$$

In matrix form: $P^{m+n} = P^m P^n$. This is simply the rule for matrix multiplication - to go from $i$ to $j$ in $m+n$ steps, sum over all intermediate states $k$ at the midpoint.

Proof: By the law of total probability and the Markov property:

$$P(X_{m+n}=j \mid X_0=i) = \sum_k P(X_{m+n}=j \mid X_m=k) P(X_m=k \mid X_0=i) = \sum_k P^{(n)}_{kj} P^{(m)}_{ik}$$

Chapman-Kolmogorov is the reason matrix multiplication is the right operation for composing Markov chain transitions. It also says: to predict $n+m$ steps ahead, you can decompose the prediction at any intermediate time $m$.

2.4 Standard Examples

Example 1: Two-state chain (weather model)

$$P = \begin{pmatrix} 1-p & p \\ q & 1-q \end{pmatrix}$$

State 1 = sunny, state 2 = rainy. Sunny stays sunny with probability $1-p$, turns rainy with probability $p$. Rainy turns sunny with probability $q$. The stationary distribution is $\pi = (q/(p+q),\ p/(p+q))$.

Example 2: Simple Random Walk on $\{0,1,\ldots,N\}$ with reflecting barriers

$$P_{ij} = \begin{cases} 1/2 & |i-j|=1,\ 0 < i < N \\ 1 & i=0, j=1 \text{ or } i=N, j=N-1 \end{cases}$$

The particle bounces off the walls at 0 and $N$. Stationary distribution: uniform.

Example 3: PageRank chain

$$P_{ij} = \alpha \cdot \frac{A_{ij}}{\text{out-degree}(i)} + (1-\alpha) \cdot \frac{1}{N}$$

where $A$ is the web adjacency matrix and $\alpha \in (0,1)$ is the damping factor (usually $\alpha=0.85$). The teleportation term $(1-\alpha)/N$ ensures the chain is irreducible and aperiodic. The stationary distribution is the PageRank vector.

Example 4: Gibbs chain on $\{0,1\}^2$

For the Ising model on two spins, $P$ is a $4 \times 4$ matrix constructed by randomly updating one spin at a time conditional on the other. This is the simplest MCMC example.

---

3. Classification of States

3.1 Communicating Classes and Irreducibility

Definition. State $j$ is accessible from state $i$ (written $i \to j$) if there exists $n \geq 0$ such that $P^{(n)}_{ij} > 0$. States $i$ and $j$ communicate (written $i \leftrightarrow j$) if $i \to j$ and $j \to i$.

Communication is an equivalence relation, and its equivalence classes are called communicating classes. A communicating class $C$ is closed if no state outside $C$ is accessible from any state inside $C$: $i \in C$ and $i \to j$ implies $j \in C$.

Definition (Irreducible Chain). A Markov chain is irreducible if it has exactly one communicating class - every state communicates with every other. Equivalently, for every pair $(i,j)$, there exists $n$ with $P^{(n)}_{ij} > 0$.

Irreducibility is the "connectivity" condition for Markov chains. An irreducible chain cannot get trapped in a subset of states. Most of the theory (stationary distributions, convergence) requires irreducibility.

Decomposition theorem: Any finite Markov chain decomposes into transient states (a particle eventually leaves forever) and one or more closed communicating classes of recurrent states. Once the chain enters a closed class, it stays there forever.

For AI: A language model's transition matrix is nearly irreducible: any token sequence of sufficient length can be generated (in principle). Practical degeneracy (zero-probability transitions due to softmax temperatures -> 0) creates absorbing states.

3.2 Recurrence and Transience

Definition. Define the first return time to state $i$: $T_i = \min\{n \geq 1 : X_n = i\}$, with $T_i = \infty$ if the chain never returns. The return probability is:

$$f_i = P(T_i < \infty \mid X_0 = i)$$

• State $i$ is recurrent if $f_i = 1$ (return is certain)
• State $i$ is transient if $f_i < 1$ (positive probability of never returning)

Theorem (Recurrence criterion). State $i$ is recurrent if and only if $\sum_{n=0}^\infty P^{(n)}_{ii} = \infty$. It is transient if and only if $\sum_{n=0}^\infty P^{(n)}_{ii} < \infty$.

Proof sketch: Let $R_i = \sum_{n=1}^\infty \mathbf{1}[X_n=i]$ be the number of returns to $i$. Then $\mathbb{E}[R_i \mid X_0=i] = \sum_{n=1}^\infty P^{(n)}_{ii}$. If $f_i=1$, returns are geometrically distributed with mean $\infty$, so the sum diverges. If $f_i < 1$, the number of returns is geometric with finite mean, so the sum converges.

Positive vs. null recurrence: Among recurrent states, define the mean return time $\mu_i = \mathbb{E}[T_i \mid X_0=i]$.

• Positive recurrent: $f_i = 1$ and $\mu_i < \infty$ (returns in finite average time)
• Null recurrent: $f_i = 1$ but $\mu_i = \infty$ (certain to return, but takes forever on average)

All recurrent states in a finite irreducible chain are positive recurrent (finite chains cannot be null-recurrent). The simple random walk on $\mathbb{Z}$ is null-recurrent in 1D and 2D, transient in 3D and above (Polya's theorem).

For AI: In MCMC, we want the chain to be recurrent (it returns to every region of the posterior). A transient MCMC chain would drift away from the posterior, giving biased samples.

3.3 Periodicity

Definition. The period of state $i$ is:

$$d(i) = \gcd\{n \geq 1 : P^{(n)}_{ii} > 0\}$$

State $i$ is aperiodic if $d(i) = 1$; otherwise it is periodic with period $d(i)$.

Key facts:

1. All states in the same communicating class have the same period
2. A chain is called aperiodic if all states have period 1
3. If $P_{ii} > 0$ for some $i$, then $d(i) = 1$ (self-loops force aperiodicity)
4. An irreducible aperiodic chain converges to its stationary distribution (Section4.3)

Example: A two-state chain $0 \leftrightarrow 1$ with $P_{01}=P_{10}=1$ is periodic with period 2: the chain alternates 0,1,0,1,... and $P^{(n)}_{00} = 1$ only for even $n$.

Periodicity breaks convergence: If a chain has period $d > 1$, then $P^{(n)}_{ij}$ does not converge as $n \to \infty$ - it oscillates. Adding any self-loop probability $\varepsilon > 0$ makes the chain aperiodic.

For AI: Metropolis-Hastings with a symmetric proposal that includes the possibility of staying put is automatically aperiodic (self-loops happen when a proposal is rejected). This is why MCMC chains converge.

3.4 Absorbing States and Absorption Probabilities

Definition. State $i$ is absorbing if $P_{ii} = 1$ (the chain stays at $i$ forever once it arrives). A chain with at least one absorbing state is called absorbing.

Canonical form: For an absorbing chain with $r$ absorbing states and $t$ transient states, the transition matrix can be written in canonical form:

$$P = \begin{pmatrix} Q & R \\ 0 & I_r \end{pmatrix}$$

where $Q$ is the $t \times t$ sub-matrix of transitions among transient states, $R$ is the $t \times r$ matrix of transitions to absorbing states, and $I_r$ is the identity on absorbing states.

Fundamental matrix: $N = (I - Q)^{-1}$. The $(i,j)$ entry of $N$ is the expected number of times the chain visits transient state $j$ before absorption, starting from transient state $i$.

Absorption probabilities: $B = NR$ gives the probability of being absorbed into each absorbing state. The gambler's ruin formula $P(\text{reach } N \mid \text{start at } a) = a/N$ (derived via OST in Section06) follows directly from this formula.

3.5 Ergodic Chains

Definition (Ergodic Chain). A Markov chain is ergodic if it is:

1. Irreducible - every state communicates with every other
2. Positive recurrent - mean return time is finite for all states
3. Aperiodic - all states have period 1

Ergodic chains are the "nice" chains: they have a unique stationary distribution, and the chain converges to it from any starting state.

For finite chains: An irreducible chain on a finite state space is automatically positive recurrent. So for finite chains, ergodic = irreducible + aperiodic.

Ergodic theorem: For an ergodic chain, the time-average converges to the space-average:

$$\frac{1}{n}\sum_{k=0}^{n-1} f(X_k) \xrightarrow{n\to\infty} \sum_i \pi_i f(i) = \mathbb{E}_\pi[f] \quad \text{a.s.}$$

This is the Markov chain version of the law of large numbers. It is why MCMC works: time-averaging over the chain's trajectory approximates the posterior expectation.

---

4. Stationary Distributions

4.1 Definition and Existence

Definition (Stationary Distribution). A probability distribution $\pi$ on $\mathcal{S}$ is a stationary distribution (also called invariant distribution or steady-state distribution) for a Markov chain with transition matrix $P$ if:

$$\pi P = \pi \qquad \text{i.e.,} \qquad \pi_j = \sum_i \pi_i P_{ij} \text{ for all } j$$

Equivalently, $\pi$ is a left eigenvector of $P$ with eigenvalue 1. If the chain starts in distribution $\pi$, it stays in distribution $\pi$ for all time: $\mu^{(0)} = \pi \Rightarrow \mu^{(n)} = \pi$ for all $n$.

Interpretation: $\pi_i$ represents the long-run fraction of time the chain spends in state $i$. For PageRank, $\pi_i$ is the importance score of page $i$. For MCMC, $\pi$ is the target posterior distribution.

Existence: Every finite irreducible Markov chain has a unique stationary distribution $\pi$ with $\pi_i > 0$ for all $i$. For infinite chains, existence requires positive recurrence.

Non-uniqueness when reducible: A chain with multiple closed communicating classes has infinitely many stationary distributions - any convex combination of the stationary distributions within each closed class is stationary.

The mean return time formula: For a positive recurrent chain, $\pi_i = 1/\mu_i$ where $\mu_i = \mathbb{E}[T_i \mid X_0=i]$ is the mean return time. States visited more often (smaller $\mu_i$) get higher stationary probability.

4.2 Perron-Frobenius Theorem

The Perron-Frobenius theorem is the fundamental result guaranteeing existence and uniqueness of the stationary distribution.

Theorem (Perron-Frobenius for Stochastic Matrices). Let $P$ be an irreducible stochastic matrix. Then:

1. $\lambda = 1$ is an eigenvalue of $P$ (always true for stochastic matrices, since $P\mathbf{1}=\mathbf{1}$)
2. $|\lambda| \leq 1$ for all other eigenvalues $\lambda$
3. There exists a unique probability vector $\pi > 0$ (componentwise) with $\pi P = \pi$
4. $\pi$ is the unique (up to scaling) left eigenvector with eigenvalue 1

If additionally $P$ is primitive (irreducible and aperiodic), then $\lambda = 1$ is the unique eigenvalue on the unit circle, and $|\lambda_2| < 1$ strictly. This gap drives convergence.

Proof sketch (uniqueness): Suppose $\pi$ and $\nu$ are both stationary. Then $\mu = (\pi - \nu)$ satisfies $\mu P = \mu$ with $\sum_i \mu_i = 0$. If any $\mu_i \neq 0$, irreducibility implies all $\mu_i \neq 0$. But then $\pi - \nu$ cannot be a probability vector minus a probability vector with the right sign everywhere - contradiction.

For AI: PageRank power iteration converges because the damped PageRank matrix is primitive (the teleportation term makes it irreducible and the self-loops make it aperiodic). The dominant eigenvalue is 1, and all other eigenvalues are $< \alpha < 1$ in magnitude, guaranteeing geometric convergence.

4.3 Convergence to Stationarity

Theorem (Convergence for Ergodic Chains). Let $P$ be irreducible and aperiodic with stationary distribution $\pi$. Then for any initial distribution $\mu^{(0)}$:

$$\|\mu^{(0)} P^n - \pi\|_{\text{TV}} \xrightarrow{n\to\infty} 0$$

Moreover, for any starting state $i$: $P^{(n)}_{ij} \to \pi_j$ as $n \to \infty$ for all $j$.

Rate of convergence: For a reversible chain with eigenvalues $1 = \lambda_1 > \lambda_2 \geq \cdots \geq \lambda_N \geq -1$, the convergence rate is governed by $\lambda_* = \max(|\lambda_2|, |\lambda_N|)$:

$$\|P^n(i,\cdot) - \pi\|_{\text{TV}} \leq \frac{1}{2\sqrt{\pi_i}} \lambda_*^n$$

The rate $\lambda_*$ is called the second largest eigenvalue modulus (SLEM). The spectral gap is $1 - \lambda_*$; a large gap means fast convergence.

Periodic chains: If $P$ is irreducible but periodic with period $d$, then $P^{(n)}_{ij}$ does not converge - it cycles. However, $P^d$ (the $d$-step chain) is aperiodic and does converge. In practice, a small perturbation (adding laziness) kills periodicity.

The lazy chain: Replace $P$ with $(I + P)/2$. This halves the spectral gap but makes the chain aperiodic with all eigenvalues non-negative, ensuring monotone convergence.

4.4 Null-Recurrent Chains

The simple random walk on $\mathbb{Z}$ returns to the origin with probability 1 (recurrent) but takes infinitely long on average (null-recurrent). Such chains have no stationary probability distribution - the "stationary measure" $\pi_i$ is not normalisable.

The 1D random walk has $\pi_i = 1$ for all $i$, which gives infinite total mass $\sum_i \pi_i = \infty$. The chain visits every state infinitely often, but spends a vanishing fraction of time at any fixed state.

Implications for AI: Infinite-state chains that model text generation (treating the entire prefix as state) may be null-recurrent or transient. In practice, language models cap context length, making the state space finite and all states positive recurrent.

4.5 Computing Stationary Distributions

Method 1: Solve the linear system

$$\pi P = \pi, \quad \|\pi\|_1 = 1, \quad \pi_i \geq 0$$

This is an $(N+1)$-dimensional system (the normalisation replaces one of the $N$ redundant equations $\pi P = \pi$). For small $N$, direct linear algebra is exact.

Method 2: Power iteration

$$\pi^{(k+1)} = \pi^{(k)} P$$

Starting from any distribution $\pi^{(0)} > 0$, iterating converges to $\pi$ at rate $\lambda_*^k$. Power iteration is the PageRank algorithm.

Method 3: Eigendecomposition Compute the left eigenvector of $P$ corresponding to eigenvalue 1. For symmetric or reversible chains, this is equivalent to finding the dominant eigenvector.

Method 4: MCMC (for continuous state spaces) For distributions $\pi(x) \propto \exp(-f(x))$ on $\mathbb{R}^d$, construct a Markov chain with stationary distribution $\pi$ and run it - the empirical distribution of the chain approximates $\pi$ by the ergodic theorem.

---

5. Detailed Balance and Reversibility

5.1 Detailed Balance Equations

Definition (Detailed Balance). A distribution $\pi$ satisfies the detailed balance equations with respect to transition matrix $P$ if:

$$\pi_i P_{ij} = \pi_j P_{ji} \quad \text{for all } i, j \in \mathcal{S}$$

Detailed balance says: the probability flux from $i$ to $j$ at stationarity equals the flux from $j$ to $i$. This is a pointwise balance of probability flows, stronger than the global balance equations $\pi P = \pi$.

Theorem. If $\pi$ satisfies detailed balance with $P$, then $\pi$ is a stationary distribution for $P$.

Proof:

$$\sum_i \pi_i P_{ij} = \sum_i \pi_j P_{ji} = \pi_j \sum_i P_{ji} = \pi_j \cdot 1 = \pi_j$$

So $\pi P = \pi$. The converse is false - a stationary distribution need not satisfy detailed balance.

Significance: Detailed balance is easier to verify than stationarity (it's a pairwise condition rather than a global one), and it characterises reversible chains. All Metropolis-Hastings algorithms are constructed to satisfy detailed balance by design.

5.2 Reversible Markov Chains

Definition (Reversible Chain). A Markov chain is reversible (or time-reversible) with respect to distribution $\pi$ if it satisfies detailed balance. Equivalently, the chain running forwards in time has the same law as the chain running backwards.

The reversed chain: Given a stationary Markov chain with transition matrix $P$, define the time-reversed chain by $\hat{P}_{ij} = \pi_j P_{ji} / \pi_i$. The reversed chain is also a Markov chain, with the same stationary distribution. The original chain is reversible iff $\hat{P} = P$.

Symmetric Markov chains are reversible: If $P_{ij} = P_{ji}$ for all $i,j$ (symmetric transition matrix), then detailed balance holds with the uniform distribution $\pi_i = 1/N$. The symmetric random walk on a graph is reversible.

Non-reversible example: The chain $1 \to 2 \to 3 \to 1$ (cyclic with $P_{12}=P_{23}=P_{31}=1$) has uniform stationary distribution but is NOT reversible: it has a preferred direction of rotation.

For AI: Reversibility is a sufficient condition for correctness of MCMC algorithms. A Metropolis-Hastings chain with target $\pi$ satisfies detailed balance - it's reversible - and therefore has $\pi$ as stationary distribution. Non-reversible MCMC (e.g., lifting methods, HMC) can mix faster but is harder to analyse.

5.3 Birth-Death Chains

A birth-death chain is a Markov chain on $\{0,1,2,\ldots\}$ where only nearest-neighbour transitions are allowed:

$$P_{i,i+1} = p_i, \quad P_{i,i-1} = q_i = 1-p_i, \quad P_{ij} = 0 \text{ for } |i-j| > 1$$

Birth-death chains are automatically reversible, and their stationary distribution can be computed explicitly. The detailed balance equations $\pi_i p_i = \pi_{i+1} q_{i+1}$ give:

$$\pi_n = \pi_0 \prod_{k=0}^{n-1} \frac{p_k}{q_{k+1}}$$

Setting $\pi_0 = 1/Z$ (normalisation) gives the stationary distribution.

Queue models: An $M/M/1$ queue with arrival rate $\lambda < 1$ (service rate) is a birth-death chain. Stationary distribution: $\pi_n = (1-\rho)\rho^n$ where $\rho = \lambda$. The chain is stable (stationary distribution exists) iff $\lambda < 1$.

For AI: The queue length at an LLM serving system (number of pending requests) is approximately a birth-death chain. The stationary distribution under load $\rho = \lambda/\mu$ determines average latency: $\mathbb{E}[\text{queue length}] = \rho/(1-\rho)$.

5.4 Spectral Decomposition of Reversible Chains

For a reversible chain, the transition matrix $P$ has real eigenvalues $1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_N \geq -1$ and an orthonormal basis of eigenvectors (with respect to the $\pi$-weighted inner product).

Spectral decomposition:

$$P^n_{ij} = \pi_j \sum_{k=1}^N \lambda_k^n \phi_k(i) \phi_k(j)$$

where $\phi_k$ are the eigenfunctions (normalised in $L^2(\pi)$). As $n \to \infty$, only the $k=1$ term survives (since $|\lambda_k| < 1$ for $k \geq 2$), giving $P^n_{ij} \to \pi_j$. The rate of convergence is $|\lambda_2|^n$.

The spectral gap: $\text{gap} = 1 - \lambda_2$ measures how fast the chain forgets its initial state. A chain with spectral gap $\delta$ mixes in $O(1/\delta)$ steps. Bounding the spectral gap from below is the main technical challenge in proving MCMC convergence rates.

Dirichlet form: For reversible chains, the spectral gap equals:

$$\text{gap} = \min_{f \perp \mathbf{1}} \frac{\mathcal{E}(f,f)}{\text{Var}_\pi(f)}$$

where $\mathcal{E}(f,f) = \frac{1}{2}\sum_{i,j} \pi_i P_{ij}(f(j)-f(i))^2$ is the Dirichlet form. This variational characterisation is the basis for Poincare inequality methods.

---

6. Mixing Times and Convergence Rates

6.1 Total Variation Distance

Definition. The total variation (TV) distance between two probability distributions $\mu$ and $\nu$ on $\mathcal{S}$ is:

$$\|\mu - \nu\|_{\text{TV}} = \sup_{A \subseteq \mathcal{S}} |\mu(A) - \nu(A)| = \frac{1}{2}\sum_i |\mu_i - \nu_i|$$

TV distance measures how distinguishable two distributions are: it equals the maximum probability that any event $A$ has different probability under $\mu$ vs. $\nu$. The TV distance is 0 iff $\mu = \nu$, and 1 iff the distributions have disjoint support.

Coupling characterisation: $\|\mu - \nu\|_{\text{TV}} = \inf_{(X,Y)} P(X \neq Y)$ where the infimum is over all couplings $(X,Y)$ with marginals $\mu$ and $\nu$. This is the coupling inequality: any coupling gives an upper bound on TV distance.

For AI: TV distance is used to measure how far an MCMC chain is from stationarity, and to certify when the chain has "mixed" sufficiently to produce approximately independent samples from the posterior.

6.2 Mixing Time

Definition. The mixing time of a Markov chain with stationary distribution $\pi$ is:

$$t_{\text{mix}}(\varepsilon) = \min\left\{t \geq 0 : \max_{x \in \mathcal{S}} \|P^t(x,\cdot) - \pi\|_{\text{TV}} \leq \varepsilon\right\}$$

The standard mixing time is $t_{\text{mix}} = t_{\text{mix}}(1/4)$ (the default $\varepsilon = 1/4$ is conventional). Mixing time measures how long the chain must run before its distribution is $\varepsilon$-close to stationarity from the worst-case starting state.

Why the worst case? In applications, we often don't control the starting state. The worst-case mixing time certifies that regardless of initialisation, the chain has converged after $t_{\text{mix}}$ steps.

Submultiplicativity: $t_{\text{mix}}(2^{-k}/4) \leq k \cdot t_{\text{mix}}$. So to achieve $\varepsilon = 2^{-k}/4$ precision, it suffices to run for $k \cdot t_{\text{mix}}$ steps.

6.3 Spectral Gap

For a reversible ergodic chain, the spectral gap $\text{gap} = 1 - \lambda_2$ provides a bound on mixing time:

Theorem (Spectral Gap Bound):

$$t_{\text{mix}}(\varepsilon) \leq \left\lceil \frac{\log(1/(\varepsilon \pi_{\min}))}{\text{gap}} \right\rceil$$

where $\pi_{\min} = \min_i \pi_i$.

Proof sketch: From the spectral decomposition, $\|P^n(x,\cdot) - \pi\|_{\text{TV}} \leq \frac{1}{2\sqrt{\pi_x}} (1-\text{gap})^n$. Setting this $\leq \varepsilon$ and solving for $n$ gives the bound.

Lower bound: There is also a lower bound: $t_{\text{mix}} \geq \frac{1}{2\,\text{gap}}$. So the mixing time is $\Theta(1/\text{gap})$ for reversible chains.

Computing the spectral gap: For small matrices, compute eigenvalues of $P$ directly. For large chains, use the Cheeger inequality: $\text{gap}/2 \leq h \leq \sqrt{2\,\text{gap}}$ where $h$ is the Cheeger constant (conductance of the chain).

6.4 Coupling Arguments

Definition (Coupling). A coupling of two Markov chains with the same transition matrix $P$ but different initial distributions $\mu, \nu$ is a process $(X_t, Y_t)$ such that each marginal is a valid Markov chain with transition $P$, and once $X_t = Y_t$ they remain together (the coalescence or meeting time).

Coupling inequality: $\|P^t(\mu,\cdot) - P^t(\nu,\cdot)\|_{\text{TV}} \leq P(X_t \neq Y_t) \leq P(\tau_{\text{meet}} > t)$

where $\tau_{\text{meet}} = \min\{t : X_t = Y_t\}$ is the coupling time.

Grand coupling: For a finite ergodic chain, one can construct a single coupling $\{(X_t^x, X_t^y) : x, y \in \mathcal{S}\}$ of chains starting from all possible pairs $(x,y)$ simultaneously, such that $\tau_{\text{meet}}$ is the same for all pairs. The mixing time is then $t_{\text{mix}} = O(\mathbb{E}[\tau_{\text{meet}}])$.

Example: Random walk on hypercube. For a lazy random walk on $\{0,1\}^d$, couple two chains by updating the same coordinate at each step. When the coordinate is chosen, the two chains agree on that bit after the update. All $d$ bits agree after $O(d \log d)$ steps (coupon collector), giving $t_{\text{mix}} = O(d \log d)$.

6.5 AI Relevance: Fast Mixing and MCMC Warm Starts

Fast mixing in practice: For Bayesian inference in LLM fine-tuning (e.g., RLHF reward models), the posterior over model weights is a distribution on $\mathbb{R}^d$ with $d \sim 10^9$. Direct MCMC is intractable; approximate methods (Langevin dynamics, HMC) exploit gradient information to achieve better mixing.

Spectral gap and dimensionality: For a Gaussian target $\mathcal{N}(0, \Sigma)$, the Langevin SDE mixing time scales as $O(\kappa)$ where $\kappa = \lambda_{\max}/\lambda_{\min}$ is the condition number of $\Sigma$. Preconditioning (e.g., SGLD with adaptive learning rates, Adam-Langevin) improves the effective spectral gap.

Warm starts: If the initial distribution $\mu^{(0)}$ is already close to $\pi$ (e.g., from a previous MCMC run), the chain needs fewer steps to mix. In sequential Bayesian updating (fine-tuning an LLM on new data), the previous posterior serves as a warm start.

Temperature scheduling: Simulated annealing starts with a high-temperature chain (wide, fast-mixing distribution) and gradually cools toward the target. This exploits fast mixing at high temperature and accurate targeting at low temperature.

---

7. Continuous-Time Markov Chains

7.1 Generator Matrix

A continuous-time Markov chain (CTMC) $\{X_t\}_{t \geq 0}$ on a finite state space $\mathcal{S}$ satisfies the Markov property for continuous time:

$$P(X_{t+s}=j \mid X_u : u \leq s) = P(X_{t+s}=j \mid X_s)$$

The chain holds in each state for an exponentially distributed sojourn time, then jumps according to a discrete-time chain. The rate of leaving state $i$ is $q_i = \sum_{j \neq i} q_{ij}$ where $q_{ij} \geq 0$ are the jump rates from $i$ to $j$.

Definition (Generator Matrix / Q-Matrix). The generator (or Q-matrix) of a CTMC is the matrix $Q$ with:

$$Q_{ij} = \begin{cases} q_{ij} \geq 0 & i \neq j \quad \text{(jump rate from } i \text{ to } j\text{)} \\ -q_i = -\sum_{j \neq i} q_{ij} & i = j \quad \text{(holding rate)} \end{cases}$$

Key property: rows of $Q$ sum to zero ($Q \mathbf{1} = \mathbf{0}$). The diagonal entries are negative; off-diagonal entries are non-negative.

Transition matrix: The probability of being in state $j$ at time $t$ given state $i$ at time 0 is:

$$P(t) = e^{Qt} = \sum_{n=0}^\infty \frac{(Qt)^n}{n!}$$

This is the matrix exponential. Note $P(0) = I$ and $\lim_{t\to\infty} P(t) = \mathbf{1}\pi$ (convergence to stationarity for ergodic chains).

Embedded chain: The CTMC can be decomposed into (1) an embedded discrete-time Markov chain governing the sequence of states visited, and (2) exponential holding times in each state. Jump probabilities: $\tilde{P}_{ij} = q_{ij}/q_i$ for $i \neq j$.

7.2 Kolmogorov Equations

Forward Equation (Fokker-Planck):

$$\frac{d}{dt} P(t) = P(t) Q \quad \Rightarrow \quad P(t) = e^{Qt}$$

This equation describes how the distribution evolves forward in time: $\frac{d}{dt}\mu(t) = \mu(t) Q$ where $\mu(t) = \mu(0) e^{Qt}$.

Backward Equation:

$$\frac{d}{dt} P(t) = Q\, P(t)$$

The forward equation applies to the time-marginal distribution; the backward equation to the transition probabilities viewed as functions of the initial state.

Stationary distribution: $\pi$ is stationary if $\frac{d}{dt}\mu(t) = 0$ at $\mu = \pi$, i.e.:

$$\pi Q = \mathbf{0} \quad \text{(row vector)} \quad \Leftrightarrow \quad \sum_i \pi_i Q_{ij} = 0 \text{ for all } j$$

For an ergodic CTMC, the stationary distribution is unique.

7.3 Stationary Distribution of CTMCs

Detailed balance for CTMCs: A distribution $\pi$ satisfies detailed balance if $\pi_i Q_{ij} = \pi_j Q_{ji}$ for all $i \neq j$. Detailed balance implies stationarity ($\pi Q = 0$).

Computing the stationary distribution: Solve $\pi Q = 0$ with $\sum_i \pi_i = 1$. This is equivalent to finding the null space of $Q^T$ (right eigenvector with eigenvalue 0).

Birth-death CTMC: With birth rate $\lambda_n$ from state $n$ and death rate $\mu_n$, detailed balance gives $\pi_n \lambda_n = \pi_{n+1}\mu_{n+1}$, yielding:

$$\pi_n = \pi_0 \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}}$$

7.4 Poisson Process as CTMC

Recall from Section06 Stochastic Processes: The Poisson process $N_t$ counts arrivals up to time $t$ with independent Poisson increments. Inter-arrival times are $\text{Exp}(\lambda)$.

The Poisson process is the simplest CTMC: states $\{0,1,2,\ldots\}$, jump rates $q_{n,n+1} = \lambda$ (arrivals only), generator:

$$Q = \begin{pmatrix} -\lambda & \lambda & & \\ & -\lambda & \lambda & \\ & & \ddots & \ddots \end{pmatrix}$$

The Poisson process is transient - it drifts to $+\infty$ with no stationary distribution. An $M/M/1$ queue (arrivals at rate $\lambda$, service at rate $\mu > \lambda$) modifies the Poisson process by adding downward jumps (service completions), yielding a birth-death CTMC with geometric stationary distribution $\pi_n = (1-\rho)\rho^n$ where $\rho = \lambda/\mu$.

For AI: The Poisson process models token arrivals at an LLM serving endpoint. At high load ($\rho \to 1$), the queue length distribution becomes heavy-tailed, leading to high-percentile latency spikes. The M/M/1 formula $\mathbb{E}[\text{queue}] = \rho/(1-\rho)$ quantifies this: 90% utilisation means 9x the base queue length.

---

8. MCMC: Markov Chain Monte Carlo

8.1 The Sampling Problem

The challenge: In Bayesian inference, the posterior $\pi(\theta \mid \mathcal{D}) \propto p(\mathcal{D}\mid\theta)\,p(\theta)$ is analytically intractable for most models. Computing $\mathbb{E}_\pi[f(\theta)]$ requires integrating over a high-dimensional distribution we cannot normalise.

MCMC solution: Construct a Markov chain $\{\theta_t\}$ on the parameter space such that:

1. The chain is ergodic (irreducible, aperiodic, positive recurrent)
2. The stationary distribution equals the target $\pi$

By the ergodic theorem, time-averaging gives posterior expectations:

$$\frac{1}{T}\sum_{t=1}^T f(\theta_t) \xrightarrow{T\to\infty} \mathbb{E}_\pi[f(\theta)]$$

The key insight: we only need to know $\pi(\theta)$ up to a normalising constant. MCMC constructs the chain using only unnormalised evaluations $\tilde{\pi}(\theta) \propto \pi(\theta)$.

8.2 Metropolis-Hastings

Algorithm (Metropolis-Hastings). Given current state $\theta$, target $\pi$, proposal $q(\cdot \mid \theta)$:

1. Sample candidate $\theta' \sim q(\cdot \mid \theta)$
2. Compute acceptance ratio: $a = \min\left(1,\ \frac{\pi(\theta')\, q(\theta \mid \theta')}{\pi(\theta)\, q(\theta' \mid \theta)}\right)$
3. With probability $a$: accept $\theta_{t+1} = \theta'$; otherwise: $\theta_{t+1} = \theta$ (reject and stay)

Correctness: The Metropolis-Hastings chain satisfies detailed balance with respect to $\pi$:

$$\pi(\theta) q(\theta' \mid \theta) a(\theta, \theta') = \pi(\theta') q(\theta \mid \theta') a(\theta', \theta)$$

Proof: Without loss of generality, assume $\pi(\theta')q(\theta\mid\theta') \leq \pi(\theta)q(\theta'\mid\theta)$. Then $a(\theta,\theta')=\frac{\pi(\theta')q(\theta|\theta')}{\pi(\theta)q(\theta'|\theta)}$ and $a(\theta',\theta)=1$, so both sides equal $\pi(\theta')q(\theta|\theta')$.

Special cases:

• Metropolis algorithm: Symmetric proposal $q(\theta'\mid\theta) = q(\theta\mid\theta')$ simplifies acceptance to $a = \min(1, \pi(\theta')/\pi(\theta))$
• Independence sampler: Proposal $q(\theta'\mid\theta) = q(\theta')$ independent of current state; acceptance $a = \min(1, \pi(\theta')q(\theta)/(\pi(\theta)q(\theta')))$

Proposal tuning: For a Gaussian random walk proposal $q(\theta'\mid\theta) = \mathcal{N}(\theta, \sigma^2 I)$, the optimal $\sigma$ achieves acceptance rate ~23.4% in high dimensions (Roberts-Gelman-Gilks 1997). Too small $\sigma$: high acceptance but slow exploration; too large: low acceptance, inefficient.

For AI: MCMC is used for posterior inference in Bayesian neural networks, uncertainty quantification in LLM outputs, and sampling from energy-based models. In practice, Langevin dynamics (gradient-based MCMC) replaces vanilla MH for high-dimensional targets.

8.3 Gibbs Sampling

Algorithm (Gibbs Sampling). For target $\pi(\theta_1,\ldots,\theta_d)$, cycle through coordinates:

1. Sample $\theta_1^{(t+1)} \sim \pi(\theta_1 \mid \theta_2^{(t)}, \ldots, \theta_d^{(t)})$
2. Sample $\theta_2^{(t+1)} \sim \pi(\theta_2 \mid \theta_1^{(t+1)}, \theta_3^{(t)}, \ldots, \theta_d^{(t)})$
3. $\vdots$
4. Sample $\theta_d^{(t+1)} \sim \pi(\theta_d \mid \theta_1^{(t+1)}, \ldots, \theta_{d-1}^{(t+1)})$

Correctness: Gibbs sampling is a special case of Metropolis-Hastings where each coordinate update is a MH step with proposal equal to the full conditional. The acceptance ratio is always 1 - every proposal is accepted. This requires the ability to sample from full conditionals $\pi(\theta_k \mid \theta_{-k})$.

Block Gibbs: Instead of updating one coordinate at a time, update a block of coordinates jointly. More efficient when coordinates within a block are highly correlated.

For AI: Gibbs sampling is used in latent Dirichlet allocation (LDA) for topic modelling - the full conditionals for topic assignments are available in closed form. In RL, it can be used to sample from the Q-function distribution for exploration.

8.4 Convergence Diagnostics

Running an MCMC chain for a finite number of steps gives an approximate (not exact) sample from $\pi$. Practical convergence diagnostics:

Trace plots: Plot $\theta_t$ vs. $t$. A well-mixed chain looks like stationary noise. Trends, drifts, or stuck values indicate non-convergence.

$\hat{R}$ statistic (Gelman-Rubin): Run $M \geq 4$ chains from diverse starting points. Compute $\hat{R} = \sqrt{V_{\text{between}}/V_{\text{within}}}$. If $\hat{R} \leq 1.01$, chains have converged to the same distribution.

Effective sample size (ESS): Due to autocorrelation within the chain, $T$ MCMC samples give fewer independent samples than $T$ iid samples. $\text{ESS} = T / (1 + 2\sum_{k=1}^\infty \rho_k)$ where $\rho_k$ is the lag-$k$ autocorrelation. $\text{ESS}/T \ll 1$ indicates poor mixing.

Burn-in: The first $B$ samples (before the chain has mixed) are discarded. Typical burn-in is $10-50\%$ of total samples.

8.5 Hamiltonian Monte Carlo

Motivation: For distributions on $\mathbb{R}^d$, the random walk Metropolis-Hastings has step size $O(d^{-1/2})$ to achieve acceptable acceptance rates, giving diffusive mixing: $O(d)$ steps to traverse the distribution. Hamiltonian Monte Carlo (HMC) exploits gradient information to take large, high-acceptance steps.

Algorithm: Augment $\theta \in \mathbb{R}^d$ with momentum $p \sim \mathcal{N}(0, M)$. The Hamiltonian is $H(\theta,p) = -\log\pi(\theta) + \frac{1}{2}p^T M^{-1} p$. Propose a new state by simulating Hamiltonian dynamics using the leapfrog integrator for $L$ steps with step size $\varepsilon$, then accept/reject with MH ratio $e^{-\Delta H}$.

Why it works: Hamiltonian dynamics preserves the joint distribution $e^{-H(\theta,p)}$ on $(\theta,p)$. Marginalising out $p$ recovers $\pi(\theta)$. The leapfrog integrator introduces discretisation error, corrected by the MH accept/reject step.

Mixing time: HMC achieves $O(d^{1/4})$ gradient evaluations per independent sample (vs. $O(d)$ for random walk), making it scalable to high dimensions. NUTS (No-U-Turn Sampler) automates the choice of $L$ and $\varepsilon$.

For AI: HMC is the backbone of probabilistic programming systems like Stan and PyMC. In Bayesian deep learning, SGLD (stochastic gradient Langevin dynamics) adds Gaussian noise to SGD steps, yielding approximate Bayesian inference at scale.

---

9. ML Deep Dive

9.1 Language Model Generation

Every autoregressive language model - GPT, LLaMA, PaLM, Gemini - generates text as a Markov chain on the vocabulary. The state at step $n$ is the entire generated sequence $(w_1,\ldots,w_n)$ (treated as a single token in the KV cache), and the transition is:

$$P(w_{n+1} = v \mid w_1,\ldots,w_n) = \text{softmax}(\text{LM}(w_1,\ldots,w_n))_v$$

Temperature and the stationary distribution: At temperature $\tau$:

$$P_\tau(w_{n+1} = v \mid \text{context}) = \frac{\exp(\text{logit}_v / \tau)}{\sum_{v'} \exp(\text{logit}_{v'}/\tau)}$$

• $\tau \to 0$: greedy decoding (deterministic); $\tau = 1$: standard sampling; $\tau \to \infty$: uniform
• The generated sequence is a Markov chain; its stationary distribution (if the chain were infinite) would represent the model's "preferred" discourse

Mixing time of language models: For a well-trained LLM, the Markov chain mixes quickly - the model "forgets" its starting state within a few hundred tokens for most topics. This reflects the inductive bias toward coherent text: the chain has a large spectral gap.

Top-$k$ and nucleus sampling: Top-$k$ sampling restricts transitions to the $k$ highest-probability tokens; nucleus (top-$p$) sampling restricts to the minimal set of tokens whose cumulative probability exceeds $p$. Both modify the transition matrix to improve mixing (reduce probability of stuck low-quality loops).

Repetition and periodicity: Without repetition penalties, language model chains can enter periodic loops (mode collapse in generation: "the the the ..."). Adding a repetition penalty introduces a state-dependent transition modification that destroys the periodic structure.

9.2 PageRank

Setup: Represent the web as a directed graph with $N$ pages. The random surfer model: a user follows a random link at each step with probability $\alpha$ (damping factor), or teleports to a random page with probability $1-\alpha$.

Transition matrix:

$$P_{ij} = \alpha \cdot \frac{A_{ij}}{d_i} + (1-\alpha) \cdot \frac{1}{N}$$

where $A_{ij} = 1$ if page $i$ links to page $j$, and $d_i = \sum_j A_{ij}$ is the out-degree of page $i$.

Dangling nodes: Pages with no outbound links ($d_i = 0$) create a stochastic matrix problem. Fix: replace the row for dangling node $i$ with the uniform distribution $1/N$. The resulting matrix is stochastic.

PageRank computation: The PageRank vector $\pi$ satisfies $\pi P = \pi$. Computed by power iteration:

$$\pi^{(k+1)} = \pi^{(k)} P$$

Convergence guaranteed by Perron-Frobenius (the damped matrix is primitive). Convergence rate: $\alpha^k$ geometric (since the second eigenvalue is $\leq \alpha$). With $\alpha = 0.85$, convergence to $10^{-8}$ precision takes $\approx 100$ iterations.

Interpretation: $\pi_i$ is the long-run fraction of time the random surfer spends on page $i$. Pages with high in-degree from other high-PageRank pages get high scores.

For AI: Influence in a social network, citations in academic papers, and token importance in attention patterns can all be modelled as PageRank variants. The attention mechanism in transformers can be viewed as a differentiable, query-dependent version of PageRank.

9.3 Markov Decision Processes

A Markov Decision Process (MDP) extends Markov chains by adding actions:

$$(\mathcal{S}, \mathcal{A}, P, r, \gamma)$$

• $\mathcal{S}$: state space; $\mathcal{A}$: action space
• $P(s' \mid s, a)$: transition probabilities given action $a$
• $r(s, a)$: reward function
• $\gamma \in [0,1)$: discount factor

A policy $\pi(a \mid s)$ induces a Markov chain on $\mathcal{S}$ with transition $P^\pi(s'\mid s) = \sum_a \pi(a\mid s) P(s'\mid s,a)$.

Bellman equation: The value function $V^\pi(s) = \mathbb{E}^\pi[\sum_{t=0}^\infty \gamma^t r(s_t,a_t) \mid s_0=s]$ satisfies:

$$V^\pi(s) = \sum_a \pi(a\mid s)\left[r(s,a) + \gamma \sum_{s'} P(s'\mid s,a) V^\pi(s')\right]$$

In matrix form: $\mathbf{V}^\pi = \mathbf{r}^\pi + \gamma P^\pi \mathbf{V}^\pi$, giving $\mathbf{V}^\pi = (I - \gamma P^\pi)^{-1}\mathbf{r}^\pi$.

Policy evaluation = linear system: Given a fixed policy $\pi$, computing $V^\pi$ requires inverting $(I - \gamma P^\pi)$. This is guaranteed well-conditioned since $\gamma < 1$ implies all eigenvalues of $\gamma P^\pi$ have magnitude $< 1$.

RLHF as MDP: Reinforcement learning from human feedback trains a language model (policy $\pi_\theta$) to maximise a reward model $r_\phi$ - an MDP with the KV cache as state, vocabulary as actions, and the human preference model as reward.

9.4 Hidden Markov Models

A Hidden Markov Model (HMM) is a Markov chain $\{Z_t\}$ (hidden states) with observations $\{X_t\}$ emitted from the current hidden state:

$$Z_0 \sim \mu_0, \quad Z_t \mid Z_{t-1} \sim P_{Z_{t-1}}, \quad X_t \mid Z_t \sim E_{Z_t}$$

where $P$ is the transition matrix and $E$ is the emission distribution.

Forward algorithm: Compute $\alpha_t(i) = P(X_1,\ldots,X_t, Z_t=i)$ recursively:

$$\alpha_t(j) = E_j(X_t) \sum_i \alpha_{t-1}(i) P_{ij}, \quad \alpha_0(j) = \mu_0(j) E_j(X_1)$$

Time complexity: $O(T \cdot |\mathcal{S}|^2)$. Used for likelihood computation and decoding.

Viterbi algorithm: Find the most likely hidden state sequence $\hat{Z}_{1:T} = \arg\max_{z_{1:T}} P(z_{1:T} \mid X_{1:T})$ via dynamic programming:

$$\delta_t(j) = E_j(X_t) \max_i \delta_{t-1}(i) P_{ij}$$

Time complexity: same as forward algorithm.

Baum-Welch (EM for HMMs): Learn $P, E, \mu_0$ from unlabelled observations. E-step: compute forward-backward probabilities. M-step: update parameters using expected sufficient statistics. Converges to a local maximum of the likelihood.

For AI: HMMs are classical sequence models (speech recognition, gene finding). Modern LLMs subsume HMMs: the hidden state (KV cache) is a rich continuous representation of the context, and emission (next-token distribution) is the softmax output.

9.5 Diffusion Models as CTMCs

The DDPM forward process can be viewed as a discrete-time Markov chain with Gaussian transitions:

$$q(x_t \mid x_{t-1}) = \mathcal{N}(x_t; \sqrt{1-\beta_t}\,x_{t-1},\, \beta_t I)$$

The marginal $q(x_t \mid x_0) = \mathcal{N}(\sqrt{\bar\alpha_t}x_0, (1-\bar\alpha_t)I)$ with $\bar\alpha_t = \prod_{s=1}^t (1-\beta_s)$.

Recall from Section06 Stochastic Processes: In the SDE formulation (Song et al., 2021), the continuous-time version is a CTMC/SDE: $dx = f(x,t)\,dt + g(t)\,dB_t$.

The reverse process: By time-reversal of Markov chains (Anderson, 1982), the reverse of an ergodic CTMC is also a CTMC. The reverse diffusion has:

$$p_\theta(x_{t-1} \mid x_t) = \mathcal{N}(x_{t-1};\, \mu_\theta(x_t, t),\, \Sigma_\theta(t))$$

The neural network learns to parameterise the reverse transitions - equivalently, to approximate the score function $\nabla_x \log q_t(x)$.

---