15 Markov chain Monte Carlo: sampling what you cannot normalize

15.1 The other road

Module 2 faced the intractable partition function and approximated the distribution: bounded it with a factorized family (Week 5), corrected the bound (Chapter 11), passed messages on the graph (Chapter 12), and finally decoupled it into a trainable latent-variable model (Chapter 14). Every one of those methods lives with \(Z\) and manages it — deterministically, with a bias fixed by the chosen family. Module 3 opens the road Week 5’s dichotomy left deliberately untaken: do not approximate \(p\) at all — sample it.

The fact that makes this possible is the simplest of the course’s escapes from \(Z\). To evaluate \(p(x) = e^{-\beta E(x)}/Z\) you need \(Z\), and that is hopeless. But to sample, you never need the probability of any single state; you only ever need to compare two, and in the ratio

\[ \frac{p(x')}{p(x)} \;=\; \frac{e^{-\beta E(x')}/Z}{e^{-\beta E(x)}/Z} \;=\; e^{-\beta\,\Delta E}, \qquad \Delta E = E(x') - E(x), \]

the partition function cancels, so that one can draw samples from a distribution one cannot normalize. The course has now met three ways of handling \(Z\): Module 1 approximated its parameter-gradient (contrastive divergence), Module 2 bounded its logarithm (the variational free energy), and Module 3 makes it cancel. The fourth, removal (\(\nabla_x \log Z = 0\)), comes in Week 10.

The history closes a loop the course opened on day one. In 1953, at Los Alamos, Nicholas Metropolis, Arianna and Marshall Rosenbluth, and Augusta and Edward Teller published Equation of State Calculations by Fast Computing Machines (Metropolis et al. 1953) — the “fast computing machine” being the MANIAC, one of the first electronic computers, and the calculation being the equilibrium properties of a fluid of hard disks that no closed form could touch. Their idea — walk through configuration space, accepting each proposed move with a probability built from the Boltzmann ratio — is Markov chain Monte Carlo, and it now runs everywhere from lattice QCD to Bayesian statistics to the negative phase of Week 3’s Boltzmann machines. Hastings (1970) generalized it.

Sampling is asymptotically exact: run the chain long enough and the answers converge to the truth, with no family bias and no bound. It is limited instead by time. The chain must mix, decorrelating from its initial state and visiting configuration space with the right frequencies, and mixing is slow near phase transitions and in the rugged landscapes of Weeks 2 and 6. Module 3 thus exchanges the normalization obstruction for the sampling one.

15.2 Approximate versus sample

The module map frames the fork (Figure 15.1). Road one — Module 2 — replaces \(p\) by the best member of a tractable family: deterministic, fast, sometimes armed with a bound, and biased forever by whatever the family cannot express (the factorized ansatz never contained a correlation, no matter how long you optimized). Road two — this module — builds a stochastic process whose visits are draws from \(p\): no family, no bias in the limit, and instead a stochastic error that shrinks with simulation time — if the process equilibrates. The choice is deterministic-and-biased against stochastic-and-exact-eventually; the course will need both, and Module 4 will need them married.

Figure 15.1: The two roads out of an intractable \(Z\). Module 2 approximated the distribution — mean field, TAP, message passing, the VAE — deterministic and biased by the chosen family, sometimes with a bound. Module 3 samples it: Markov chain Monte Carlo is stochastic, asymptotically exact, and \(Z\)-free, because the normalizer cancels in every ratio the algorithm ever uses. Each road has its own obstruction: family bias on one, mixing time on the other — and Week 10’s score matching still waits at the bottom, where \(Z\) is neither bounded nor canceled but removed.

Figure 15.2 draws the method before the mathematics. Left: a walker on an energy landscape takes proposed steps — downhill steps always accepted, uphill steps accepted with probability \(e^{-\beta \Delta E}\) — and the histogram of its visits piles up, over time, into exactly \(e^{-\beta E}\): the Boltzmann distribution, assembled from nothing but local energy differences. Right: the same walker at low temperature, confined to one basin behind a barrier it crosses only with exponentially small probability, sampling that basin faithfully but not the rest of configuration space. The left panel is the theorem proved below; the right is the mixing problem of Section 15.4.

Figure 15.2: Left: the Metropolis walker — downhill proposals always accepted, uphill ones accepted with probability \(e^{-\beta\Delta E}\) — and the histogram of its visits (orange) converging onto \(e^{-\beta E}\) (red dashed): the Boltzmann distribution sampled without \(Z\) ever being computed. Right: at low temperature a barrier is crossed only with probability \(\sim e^{-\beta\,\Delta E_{\text{barrier}}}\) per attempt; the chain samples its home basin and not the other one, so equilibration within a basin falls short of global equilibration.

15.3 Detailed balance and the Metropolis rule

Setup. We want a stochastic process on configuration space — a Markov chain, specified by transition probabilities \(W(x \to x')\) — whose long-run visit frequencies are \(p(x) \propto e^{-\beta E(x)}\), built using only the ratio \(e^{-\beta \Delta E}\). The design condition is stationarity: if the chain’s states are distributed as \(p\) at one step, they must remain so at the next,

\[ \sum_x p(x)\, W(x \to x') \;=\; p(x') \quad \text{for all } x'. \]

(That a well-behaved chain then converges to this \(p\) from any start — uniqueness of the stationary distribution under irreducibility and aperiodicity, Perron–Frobenius — is the same bookkeeping we took as read for Glauber in Section 5.3. The convergence rate is treated in Section 15.4.)

Detailed balance. Stationarity is a global condition — a sum over all states, awkward to engineer directly. The workhorse is a local, pairwise condition that implies it:

\[ \boxed{\; p(x)\, W(x \to x') \;=\; p(x')\, W(x' \to x) \quad \text{for all pairs } x, x' \;} \tag{15.1}\]

detailed balance \(\Rightarrow\) \(p\) stationary

— detailed balance: at equilibrium, probability flows equally in both directions across every pair of states, not just in aggregate. The implication is one line — sum both sides over \(x\), and \(\sum_x W(x' \to x) = 1\) collapses the right side:

\[ \sum_x p(x)\, W(x \to x') \;=\; p(x') \sum_x W(x' \to x) \;=\; p(x'). \]

You have seen this condition before, doing exactly this job: it is what gave Glauber dynamics its Boltzmann stationary law in Section 5.3, there checked for one specific flip rule. Today it is promoted from a property we verified to a design principle we build from. (One margin note, made precise at the end of this section: detailed balance is sufficient, not necessary — valid and sometimes faster chains exist that break it. It is the standard tool because it is the checkable one.)

The Metropolis rule. Split each transition into a proposal and an acceptance: \(W(x \to x') = g(x \to x')\, A(x \to x')\), with \(g\) symmetric (\(g(x \to x') = g(x' \to x)\) — flip a random spin, jiggle a coordinate). Inserted into Equation 15.1, the symmetric proposal cancels from both sides, and what remains is a condition on the acceptance alone:

\[ \frac{A(x \to x')}{A(x' \to x)} \;=\; \frac{p(x')}{p(x)} \;=\; e^{-\beta\, \Delta E}, \qquad \Delta E = E(x') - E(x). \tag{15.2}\]

The right-hand side is a ratio of Boltzmann weights, and the normalizer cancels from it identically. The condition fixes only the ratio of the two acceptances for each pair, so it has many solutions, and one more requirement selects among them. A rejected proposal leaves the chain where it was, so a chain that rejects less moves more; we therefore make the acceptances as large as the constraint allows. For each pair, the larger of \(A(x \to x')\) and \(A(x' \to x)\) can be raised to one, and Equation 15.2 then fixes the other. For a downhill move, \(\Delta E \le 0\), this sets \(A(x \to x') = 1\) and \(A(x' \to x) = e^{\beta \Delta E}\); for an uphill move the roles exchange, \(A(x \to x') = e^{-\beta \Delta E}\) and \(A(x' \to x) = 1\). Both branches are one formula,

\[ \boxed{\; A(x \to x') \;=\; \min\!\big( 1,\; e^{-\beta\, \Delta E} \big) \;} \tag{15.3}\]

Metropolis acceptance

— accept every downhill move; accept an uphill move with probability \(e^{-\beta \Delta E}\) (Figure 15.3). This is the rule of Metropolis et al. (1953). A compact form of the same statement: with symmetric \(g\), \(p(x)\, g\, A(x \to x') = g\, \min\big(p(x), p(x')\big)\), because \(p \min(1, p'/p) = \min(p, p')\), and this expression is manifestly symmetric under \(x \leftrightarrow x'\). And the algorithm consumed only one thing: \(p\) entered only through the ratio \(p(x')/p(x) = e^{-\beta\Delta E}\). \(Z\) never appears. The chain’s visit frequencies converge to the full, correctly normalized Boltzmann distribution — normalizer included — and the normalizer was never computed, only canceled. One local rule, using one energy difference per step, samples a globally intractable distribution exactly.

Two standard extensions complete the design. For asymmetric proposals, Hastings (1970) rebalances the acceptance, \(A = \min\big(1, \frac{p(x')\,g(x' \to x)}{p(x)\,g(x \to x')}\big)\) — still a ratio, \(Z\) still gone. And proposing from an exact conditional distribution (resample one variable given all others) makes the Hastings ratio identically one — accept always: the Gibbs sampler (Geman and Geman 1984), which you have been running since Week 3, because the RBM’s block Gibbs (Section 6.3) is precisely this with whole layers as the resampled blocks. Glauber’s flip rule, likewise, is just a different valid acceptance function (\(1/(1 + e^{\beta\Delta E})\) — the “heat bath” choice, which satisfies the same ratio condition Equation 15.2 with smaller acceptances than Metropolis’s \(\min\)). One principle generates a family of algorithms.

Sufficient, not necessary: the adjoint kernel. The precise statement identifies what stationarity actually requires — and introduces one of the module’s central objects (Welling, Lu, and Holdijk 2026, ch. 11 on Markov chain Monte Carlo). We claim that \(p\) is stationary under \(W\) if and only if there exists a second transition probability \(W^\dagger\) — the adjoint kernel, nonnegative and normalized — satisfying the generalized balance relation

\[ p(x)\, W(x \to x') \;=\; p(x')\, W^\dagger(x' \to x) \quad \text{for all pairs } x, x'. \tag{15.4}\]

generalized balance: stationarity’s exact requirement

One direction is the same one-line sum as before: if such a \(W^\dagger\) exists, summing Equation 15.4 over \(x\) gives \(\sum_x p(x)\, W(x \to x') = p(x') \sum_x W^\dagger(x' \to x) = p(x')\), which is stationarity. For the converse there is only one candidate — solve Equation 15.4 for

\[ W^\dagger(x' \to x) \;=\; \frac{p(x)\, W(x \to x')}{p(x')}, \]

manifestly nonnegative, and check that it is normalized:

\[ \sum_x W^\dagger(x' \to x) \;=\; \frac{1}{p(x')} \sum_x p(x)\, W(x \to x'), \]

which equals one for every \(x'\) exactly when \(p\) is stationary. The constructed \(W^\dagger\) is a genuine transition kernel precisely when the chain has \(p\) as its stationary law, and the equivalence is proved. Detailed balance is the special case \(W^\dagger = W\): the chain is its own adjoint.

The adjoint has a physical reading that the course will lean on. By construction, \(W^\dagger(x' \to x)\) is the probability that a stationary chain sitting at \(x'\) arrived from \(x\) — Bayes’ rule applied to one step — so \(W^\dagger\) is the chain watched in reverse. Detailed balance then says the film run backwards is statistically indistinguishable from the film run forwards: no pair of states carries a net probability current, which is the defining property of equilibrium. Generalized balance permits more: \(W^\dagger \neq W\), probability circulating around closed loops, every state’s total inflow and outflow balancing while individual pairs carry steady current. Such a chain is stationary but irreversible — a nonequilibrium steady state, the same object whose circulating currents reappear in Week 9’s anisotropic SGD — and irreversibility is not a defect: the persistent current stirs the state space rather than diffusing through it, which is why deliberately non-reversible chains can mix faster than any detailed-balance competitor built from the same moves. You have, in fact, been running one since Week 3: fixed-scan Gibbs on the RBM’s joint \((v, h)\) chain — resample \(h\), then \(v\) — satisfies detailed balance in each half-step but not in their composition (its adjoint is the scan run in the opposite order), and it leaves \(p\) invariant all the same. (The chain it induces on the visible units alone, \(v \to h \to v\), is reversible again: \(p(v) \sum_h p(h \mid v)\, p(v' \mid h) = \sum_h p(v, h)\, p(v', h) / p(h)\) is symmetric in \(v\) and \(v'\).) Why, then, does detailed balance remain the standard tool? Because normalizing \(W^\dagger\) is exactly as global a check as stationarity itself — a sum over all states — while detailed balance is verified pair by pair, from energy differences alone. Design locally with Equation 15.1, knowing the license Equation 15.4 grants is wider; Week 10 will use that license out of equilibrium, where the marginals themselves change in time and the reversed kernel becomes the generative object.

Show code

dE = np.linspace(-2.5, 4, 500)
fig, ax = plt.subplots(figsize=(8.0, 3.9))
ax.plot(dE, np.minimum(1, np.exp(-dE / 1.0)), color=ORANGE, lw=2.4,
        label=r"Metropolis, $T = 1$")
ax.plot(dE, np.minimum(1, np.exp(-dE / 0.3)), color=NAVY, ls="--", lw=2.0,
        label=r"Metropolis, $T = 0.3$ (nearly greedy)")
ax.plot(dE, 1 / (1 + np.exp(dE / 1.0)), color=ORANGE, ls=":", lw=1.8,
        label=r"Glauber (heat bath), $T = 1$")
ax.axvline(0, color=GRAY, lw=0.8)
ax.text(-1.4, 0.5, "downhill:\nalways accepted", color=GRAY, fontsize=10.5, ha="center")
ax.text(2.3, 0.62, "uphill: accepted with $e^{-\\beta\\Delta E}$ —\n"
        "the tolerance that makes it a sampler,\nnot an optimizer", color=GRAY,
        fontsize=10.5, ha="center")
ax.set_xlabel(r"proposed energy change $\Delta E$")
ax.set_ylabel(r"acceptance $A$")
ax.set_ylim(0, 1.1)
ax.legend(frameon=False, fontsize=9.5, loc="lower left")
fig.tight_layout(); plt.show()

Figure 15.3: The Metropolis acceptance Equation 15.3 against the proposed energy change, at two temperatures, with Glauber’s heat-bath rule (Section 5.3) alongside for the warm case. Downhill moves (\(\Delta E < 0\)) are always accepted; uphill moves survive with probability \(e^{-\beta\Delta E}\) — the uphill tolerance that distinguishes a *sampler* from Week 2’s greedy descent, and the only place temperature enters the algorithm. Cool the chain and the tolerance narrows toward pure descent (navy dashed); both acceptance functions satisfy detailed balance with respect to the same Boltzmann distribution, Metropolis simply accepting more.

15.4 Sampling since Week 3, and the mixing problem

The method is not new to this course, but it now gets its name. Glauber dynamics — Week 3’s stochastic flip rule, from which the Boltzmann machine was built — is single-spin MCMC with the heat-bath acceptance. The RBM’s block Gibbs ladder is the Gibbs sampler, layer by layer. And contrastive divergence is a truncated Markov chain — a sampler deliberately run \(k\) steps from the data instead of to equilibrium — and that is the entire content of its bias. In Section 6.4 we quantified the CD-\(k\) gap, watched it decay with \(k\), and saw that the decay is controlled by the chain’s mixing; today that observation becomes a general statement about any unequilibrated chain, which samples the wrong distribution, so the negative phase it estimates is systematically off, by exactly the amount the chain has failed to mix.

Mixing. Everything above says the chain converges; none of it says when. Three consequences follow. First, MCMC samples are correlated: consecutive states differ by one accepted move, so a run of \(M\) steps carries not \(M\) independent draws but roughly \(M/(2\tau)\), where \(\tau\) is the autocorrelation time — the number of steps over which the chain decorrelates, measured in the same unit as \(M\) (steps or sweeps; the Ising numbers below are in sweeps). Second, the chain needs burn-in: samples taken before stationarity is reached are draws from the wrong distribution and must be discarded (CD’s bias again, this time as a lab habit). Third, and most seriously, \(\tau\) itself can diverge. It does so in exactly the two regimes this course keeps meeting. Near a critical point, fluctuations become system-spanning while the dynamics stays local, and \(\tau\) grows as a power of the correlation length (critical slowing down — the worked example below measures it); physics has cures here (cluster algorithms that flip correlated islands wholesale, which we do not develop). In rugged, glassy landscapes — Week 2’s overloaded memory, Week 6’s spin glass — barriers are extensive, crossing times are exponential, and below the glass transition ergodicity breaks: the chain is confined to one valley of many, and no polynomial patience rescues it. For the models this course cares about, Figure 15.2’s right panel shows the typical situation.

Week 3 already separated normalization and sampling as two distinct obstructions (Section 5.5). Module 2 fought the first — \(Z\), the normalizer — by bounding and approximating. Module 3 makes the first cancel outright, and inherits the second: mixing. Neither implies the other (a perfectly known \(Z\) would not flatten a single barrier), and the map of the field keeps them separate. MCMC yields samples and ratios, never \(Z\) itself — if you genuinely need the normalizer (to compare models, to report a likelihood), sampling alone is not enough, and the machinery that extracts free energies from chains (thermodynamic integration, annealed importance sampling) is Week 11’s, where it arrives in the language of nonequilibrium thermodynamics.

Trap

A chain that has not mixed samples the wrong distribution, with no internal sign of it. MCMC’s samples are correlated (effective sample size \(M/(2\tau)\) from \(M\) steps, not \(M\)), require burn-in, and are only asymptotically exact given equilibration. An unmixed chain produces smooth, convergent-looking, reproducibly wrong averages — it is why contrastive divergence is biased (Section 6.4), and why every MCMC result should report an autocorrelation time. And \(Z\) cancels in ratios, but MCMC never yields \(Z\); estimating normalizers from samples is Week 11’s subject.

Take-home 1

Glauber dynamics, block Gibbs, and contrastive divergence are all MCMC — and CD is biased precisely because its chain is deliberately not equilibrated. \(Z\)-free sampling is limited by mixing: correlated samples (\(M_\text{eff} \approx M/(2\tau)\) from \(M\) steps), mandatory burn-in, autocorrelation times that diverge at critical points and grow exponentially in glassy landscapes. Normalization and mixing are distinct obstructions; Module 3’s subject is the second.

15.5 Example: Metropolis on the two-dimensional Ising model

A single chain shows both the method’s reach and its limitation. We run checkerboard Metropolis on a \(24 \times 24\) Ising lattice (the two sublattices updated in alternating half-sweeps, a vectorized equivalent of single-site updates) across the temperature range straddling Onsager’s exact critical point \(T_c = 2/\log(1 + \sqrt{2}) \approx 2.269\) (Onsager 1944), and measure the magnetization and the autocorrelation time of its time series (Figure 15.4).

The magnetization curve shows what sampling achieves. The full phase transition — the ordered branch, the collapse at \(T_c\), the disordered tail — emerges from a walker that only ever computed local energy differences: no \(Z\), no free energy, no \(2^{576}\)-term sum, just \(\min(1, e^{-\beta\Delta E})\) applied a few million times per temperature. Where Week 5 obtained this curve from a variational bound (with the transition in the wrong place) and the exact treatments of Weeks 1–2 needed enumerability, the sampler reaches the exact answer. On a \(4\times 4\) lattice, where all \(65{,}536\) states can be enumerated, the same chain reproduces the exact \(\langle |m| \rangle\) to a few parts in a thousand:

\(T\)	exact \(\langle\|m\|\rangle\) (\(4\times4\), enumerated)	MCMC estimate
\(2.0\)	\(0.9189\)	\(0.9193\)
\(2.5\)	\(0.7647\)	\(0.7606\)
\(3.0\)	\(0.6013\)	\(0.5977\)

The autocorrelation panel shows the limitation. Away from the transition, \(\tau \approx 1\)–\(3\) sweeps — consecutive configurations decorrelate almost immediately, and every sweep is nearly a fresh sample. Approaching \(T_c\), the time series develops long correlated excursions, because system-spanning fluctuations must rearrange through single spin flips, and \(\tau\) rises to \(\approx 29\) sweeps, a twenty-fold collapse in effective sample size, at fixed computational cost. Critical slowing down is visible directly, and it scales: on larger lattices the peak grows as a power of the system size, and in the glassy landscapes of Weeks 2 and 6 the analogous times are exponential. The sampler is exact when it mixes, and the plot shows where mixing fails.

Show code

def metropolis_ising(L, T, sweeps, burn, rng):
    s = rng.choice([-1, 1], size=(L, L))
    mask = (np.indices((L, L)).sum(axis=0) % 2).astype(bool)
    ms = np.empty(sweeps)
    for t in range(burn + sweeps):
        for sub in (mask, ~mask):                      # checkerboard half-sweeps
            nb = (np.roll(s, 1, 0) + np.roll(s, -1, 0) +
                  np.roll(s, 1, 1) + np.roll(s, -1, 1))
            dE = 2 * s * nb                            # flip cost, all sites at once
            acc = (rng.random((L, L)) < np.exp(-dE / T)) & sub
            s = np.where(acc, -s, s)                   # Metropolis: min(1, e^{-dE/T})
        if t >= burn:
            ms[t - burn] = abs(s.mean())
    return ms

def tau_int(x, c=5):
    """integrated autocorrelation time, automatic windowing."""
    x = x - x.mean()
    n = len(x)
    f = np.fft.rfft(x, 2 * n)
    acf = np.fft.irfft(f * np.conj(f))[:n].real
    acf /= acf[0]
    tau = 0.5
    for M in range(1, n // 2):
        tau += acf[M]
        if M >= c * tau:
            return max(tau, 0.5)
    return tau

rng = np.random.default_rng(1)
L = 24
Ts = np.linspace(1.8, 3.2, 15)
mm, tt = [], []
for T in Ts:
    series = metropolis_ising(L, T, sweeps=10000, burn=1500, rng=rng)
    mm.append(series.mean())
    tt.append(tau_int(series))

Tc = 2 / np.log(1 + np.sqrt(2))
fig, (a1, a2) = plt.subplots(1, 2, figsize=(10.4, 4.0))
a1.plot(Ts, mm, "o-", color=NAVY, lw=2)
a1.axvline(Tc, color=GRAY, ls="--", lw=1.2)
a1.text(Tc + 0.04, 0.85, r"$T_c \approx 2.269$" "\n(Onsager)", color=GRAY, fontsize=10)
a1.set_xlabel(r"$T/J$"); a1.set_ylabel(r"$\langle |m| \rangle$")
a1.set_title("the transition, sampled — no $Z$ anywhere", fontsize=12)
a2.plot(Ts, tt, "s-", color=ORANGE, lw=2)
a2.axvline(Tc, color=GRAY, ls="--", lw=1.2)
a2.annotate(rf"$\tau \approx {max(tt):.0f}$ sweeps:" "\ncritical slowing down",
            xy=(Ts[int(np.argmax(tt))], max(tt)), xytext=(2.55, 24),
            color=ORANGE, fontsize=10.5,
            arrowprops=dict(arrowstyle="->", color=ORANGE, lw=1))
a2.text(2.9, 6, r"$\tau \approx 1$–$3$ away" "\nfrom criticality", color=GRAY, fontsize=10)
a2.set_xlabel(r"$T/J$"); a2.set_ylabel(r"autocorrelation time $\tau$ (sweeps)")
a2.set_title("autocorrelation time", fontsize=12)
fig.tight_layout(); plt.show()

Figure 15.4: Sampling and its mixing time on one chain: checkerboard Metropolis on a \(24\times24\) Ising lattice (\(10{,}000\) measurement sweeps per temperature after burn-in). Left: the sampled magnetization \(\langle|m|\rangle(T)\) traces the full phase transition across Onsager’s \(T_c \approx 2.269\) (dashed) — obtained from local energy differences alone, with \(Z\) never computed (and verified against exact enumeration on a \(4\times4\) lattice to a few parts per thousand). Right: the autocorrelation time of the magnetization series rises from \(1\)–\(3\) sweeps far from criticality to \(\approx 29\) sweeps near \(T_c\): critical slowing down. The effective sample size drops near the transition; in glassy landscapes the corresponding times become exponential.

A distribution that cannot be normalized can still be sampled, because \(Z\) cancels in every ratio; what remains is the mixing time.

Take-home 2

Metropolis samples the 2-D Ising phase transition without ever computing \(Z\) — and matches exact enumeration where enumeration is possible — but its autocorrelation time rises twenty-fold at \(T_c\): critical slowing down. The method is exact when it mixes and silently unreliable when it does not.

15.6 Outlook: temperature becomes a tool

A short algorithm samples the distribution whose normalizer was intractable throughout Weeks 3–7, by canceling it in every ratio; its limitation is the equilibration time, which diverges near transitions and in glassy landscapes. The next lecture turns the algorithm’s temperature into a schedule (Kirkpatrick, Gelatt, and Vecchi 1983): at high \(T\) the walker crosses barriers and moves globally, at low \(T\) it stays in one basin and refines, and a cooling schedule combines both, using the Boltzmann distribution’s own concentration onto low-energy states as an optimization principle. That is simulated annealing, and with it Module 3’s second theme: the dynamics of a sampler as a subject in itself.

Week 9 then delivers the module’s main consequence for machine learning. Stochastic gradient descent — the algorithm training every model in this course’s second half — takes noisy downhill steps on a loss landscape: a proposal (the gradient direction, jittered by the mini-batch) and no explicit acceptance, yet to leading order, and for isotropic gradient noise, its long-run behavior is that of a Langevin sampler whose stationary law is a Boltzmann distribution over the loss, at a temperature set by the learning rate and batch size. Anisotropic noise turns this into a nonequilibrium steady state. The Fokker–Planck machinery that makes this precise is the subject of Week 9, and one module later it becomes the mathematical substrate of diffusion models.