Markov Chain Monte Carlo Methods · Gibbs Sampling

§17.3 Markov chain Monte Carlo

Sometimes there is no tractable way to draw exact samples from $p_\text{model}$ or even from a good importance distribution $q$ — the typical case for an energy-based model $p(\boldsymbol{x}) \propto \exp(-E(\boldsymbol{x}))$ . Sampling an EBM directly is a chicken-and-egg problem: to sample $a$ you need $p(a\mid b)$ , but to sample $b$ you need $p(b\mid a)$ . Directed models sidestep this with ancestral sampling in topological order; undirected models cannot.

The escape is a Markov chain : hold a state $\boldsymbol{x}$ , start it anywhere, and update it repeatedly with a transition operator $T(\boldsymbol{x}'\mid\boldsymbol{x})$ until it becomes (nearly) a fair sample. The family of algorithms doing this is Markov chain Monte Carlo (MCMC).

The matrix view. Restrict to countably many states (index them by integers) and imagine infinitely many chains run in parallel; let $v_i$ be the fraction in state $i$ . One update multiplies that distribution by the transition matrix $A_{i,j} = T(\boldsymbol{x}'{=}i \mid \boldsymbol{x}{=}j)$ :

A Markov step is a matrix multiply (eqs 17.20–17.21)

\boldsymbol{v}^{(t)} = \boldsymbol{A}\,\boldsymbol{v}^{(t-1)} = \boldsymbol{A}^{t}\,\boldsymbol{v}^{(0)}

$\boldsymbol{v}^{(t)}$	the distribution over states after t steps (across the parallel chains)	probability vector
$\boldsymbol{A}$	the transition matrix; each COLUMN is a probability distribution (where you go from that state) — a stochastic matrix	states × states
$\boldsymbol{A}^{t}$	applying the update t times = raising A to the t-th power — the whole trajectory is matrix exponentiation	states × states

Because $\boldsymbol{A}$ is a stochastic matrix (columns are distributions), the Perron–Frobenius theorem guarantees its largest eigenvalue is exactly $1$ . Diagonalizing, $\boldsymbol{v}^{(t)} = \boldsymbol{V}\,\mathrm{diag}(\boldsymbol{\lambda})^{t}\,\boldsymbol{V}^{-1} \boldsymbol{v}^{(0)}$ (eq 17.22): every eigenvalue below $1$ is raised to the $t$ -th power and decays to zero, leaving only the eigenvalue-1 direction — the stationary (equilibrium) distribution :

The stationary distribution (eq 17.23)

\boldsymbol{v} = \boldsymbol{A}\boldsymbol{v}

$\boldsymbol{v}$	the equilibrium: applying the transition leaves the DISTRIBUTION unchanged (individual states still move)	probability vector
$\boldsymbol{A}\boldsymbol{v} = \boldsymbol{v}$	an eigenvector equation with eigenvalue 1 — the fixed point the chain converges to	eigenvector

Choose $T$ so this stationary $\boldsymbol{v}$ equals the target $p$ . Watch a four-state chain converge — and watch mixing collapse as its two clusters decouple:

A four-state Markov chain, two clusters. Each "step" applies v ← Av; the distribution converges to the uniform stationary distribution (the eigenvalue-1 eigenvector). The coupling ε controls the second eigenvalue |λ₂| = 1−4ε: shrink ε and mixing time diverges — the chain stays trapped in cluster L. This is exactly the separated-modes problem of §17.5.

ε = 0.06

step t = 0

‖v − uniform‖₁ = 1.500

|λ₂| = 1 − 4ε = 0.76

mixing time ≈ 5 steps

Each step multiplies the whole distribution by the stochastic matrix A. It converges to the eigenvalue-1 eigenvector (the uniform stationary distribution). The second eigenvalue |λ₂|sets the speed: as the coupling ε → 0 the clusters separate, |λ₂| → 1, and mixing time → ∞ — the chain never leaves cluster L.

Burn-in, thinning, and the mixing-time problem

Running a chain to equilibrium is called burning in ; those early samples are discarded. After equilibrium the samples are identically distributed but successive ones are highly correlated, so a short run is unrepresentative — mitigate by keeping only every $n$ -th sample, or by running many chains in parallel (deep-learning practice uses around 100, one per minibatch example). How long is burn-in? The mixing time is set by the second-largest eigenvalue of $\boldsymbol{A}$ — but the state space is exponentially large, so we cannot compute it. We run “long enough” and check for mixing with heuristics (inspecting samples, measuring autocorrelation). Theory promises convergence, and little more.

§17.4 Gibbs sampling

We still need to choose a transition operator $T$ whose stationary distribution is our $p_\text{model}$ . There are two routes: derive $T$ from a learned EBM (this section), or parametrize and learn $T$ directly so its stationary distribution is implicitly the model (§20.12–20.13). The standard derived choice is Gibbs sampling: update one variable at a time from its conditional given its graph neighbors.

Gibbs sampling (deriving T from an EBM)

1initialize the state $\boldsymbol{x}$ arbitrarily
2repeat until burned in, then keep samples:
3for each variable $x_i$ (or each conditionally-independent block):
4sample $x_i \sim p_\text{model}(x_i \mid \text{neighbors of } x_i)$ ⓘ
5emit $\boldsymbol{x}$ as a sample (thinning as needed)ⓘ

Variables that are conditionally independent given their neighbors can be sampled together — block Gibbs sampling . The RBM is the model example: all hidden units are independent given the visibles (and vice versa), so each entire layer updates in one shot. Replay it — this is the Markov chain whose stationary distribution is the RBM:

Block Gibbs sampling in an RBM (from §16.7.1), seen now as an MCMC transition operator. Alternating "sample all h | v" and "sample all v | h" is one Gibbs sweep; iterating defines a Markov chain whose stationary distribution is p_model(v, h). The restricted (bipartite) structure is what lets a whole block move at once.

step 0 · v = [1, 0, 1] · h = [0, 0]

next: sample the HIDDEN block from P(hᵢ=1 | v)

No hidden–hidden or visible–visible edges means every unit in a layer is conditionally independent of the rest of its layer given the other layer — so the whole block samples at once, each unit from a simple sigmoid. Alternating h, v, h, v… is block Gibbs sampling, and it is what makes the RBM cheap to train (ch18).

How does this compare with the directed-model sampler?

Ancestral sampling vs MCMC/Gibbs. Click a cell for detail.
	Aspect	Ancestral (directed)	MCMC / Gibbs (undirected)
Exactness	sample quality	exact in one pass	approximate; fair only after burn-in
Cost	compute per sample	one forward pass	burn-in + decorrelation time
Applies to	model type	directed acyclic graphs only	any model with p̃ > 0 (EBMs)
Failure mode	what goes wrong	none (single pass)	slow mixing between modes

Dotted-underlined cells have explanations — click one.

Other transition operators exist — Metropolis–Hastings is standard in many fields — but in the deep-learning approach to undirected models, Gibbs sampling is almost the only one used; better samplers remain a research frontier. Its Achilles’ heel is coming up next: when the distribution has well-separated modes, the chain mixes agonizingly slowly.

Check yourself — MCMC & Gibbs sampling

1.Why can't we use ancestral sampling on an energy-based (undirected) model?

2.In the matrix view v⁽ᵗ⁾ = Aᵗv⁽⁰⁾, why does the chain converge to a stationary distribution?

3.What sets a Markov chain's mixing time, and why is it a practical problem?

4.In block Gibbs sampling of an RBM, why can a whole layer be sampled at once?

5.Predict the outcome — in MarkovChainLab you lower the coupling ε toward 0 and step the chain (started in cluster L). What do the readouts show?

5 questions