1.44 MCMC: Metropolis–Hastings and Gibbs: study notes

Learn AI by Story

1. The idea in one sentence

Markov chain Monte Carlo (MCMC) draws samples from a probability distribution p(x) that is too awkward to sample directly, by taking a random walk that is built so that, in the long run, it visits each place in proportion to p(x), and it only ever needs ratios of p, so the unknown normalising constant Z cancels out.

2. The story from the video

Kavya visits five river villages. The villages have populations in the ratio 1 : 2 : 3 : 4 : 5, so a "fair" random visitor should spend 1/15 ≈ 6.7%, 2/15 ≈ 13.3%, 3/15 = 20.0%, 4/15 ≈ 26.7% and 5/15 ≈ 33.3% of her time in villages 1 to 5. (All numbers in this story are illustrative.)

The catch is that Kavya does not know the total population, so she cannot write down the exact percentages. She only knows how big each village is compared with its neighbour. So she makes up a simple rule:

Flip a coin to propose the left or right neighbouring village.
If the neighbour is bigger, move there.
If the neighbour is smaller, move there only with probability equal to the ratio of the two sizes.
If the proposal falls off the end of the river, stay where she is.

From village 4, a move to village 5 is always accepted (5 is bigger). A move to village 3 is accepted with probability 3/4 = 75%. When she stays, the current village is counted again.

A computer simulation of 100,000 such steps, starting in village 3 (numpy seed 1), gave visit shares of 6.9%, 13.6%, 19.9%, 26.4% and 33.1%. These match 1 : 2 : 3 : 4 : 5 closely, although she never used the total.

The video then covers the practical points: the early steps depend on where she started (burn-in), nearby steps are correlated, and the step size is a trade-off. Hastings added a correction for proposals that are not symmetric. Gibbs sampling is a special case: for a 2-D Gaussian with correlation ρ = 0.8, you update one coordinate at a time from its conditional distribution, moving in a staircase, and every move is accepted. The uses are Bayesian models, restricted Boltzmann machines (RBMs) and topic models.

3. Key definitions (glossary)

Monte Carlo estimate: an average ŝₙ = (1/n) Σ f(x⁽ⁱ⁾) of f over n random samples, used to approximate s = E_p[f(x)]. Plain English: guess an average by sampling.
Target distribution p(x): the distribution we want samples from. Plain English: the shape we want our random visits to follow.
Unnormalised density p̃(x): a function proportional to p, with p(x) = p̃(x) ÷ Z. Plain English: the "sizes" of the villages before dividing by the total.
Normalising constant Z: the sum or integral of p̃(x) over all x, which makes p add up to 1. Plain English: the total population, often impossible to compute.
Markov chain: a sequence z₁, z₂, … where each state depends only on the one just before it (first-order Markov property). Plain English: the next step depends only on where you are now.
Transition probability T(z, z′): the chance of moving from z to z′. Plain English: the rule for the next step.
Stationary (invariant) distribution: a distribution that stays unchanged when the chain takes a step; in matrix form v = Av, an eigenvector with eigenvalue 1. Plain English: the shares you get after the walk has run for ages.
Detailed balance: p(z) T(z, z′) = p(z′) T(z′, z) for all pairs. It is sufficient (not necessary) for p to be stationary. Plain English: traffic from A to B equals traffic from B to A.
Ergodic chain: a chain that has a unique equilibrium distribution, whatever the starting point. Plain English: it forgets where it started.
Proposal distribution q: the rule that suggests a candidate move. Plain English: Kavya's coin flip.
Acceptance probability: the chance min(1, a) of taking the proposed move. Plain English: the "should I really go?" check.
Metropolis algorithm: MCMC with a symmetric proposal; accept with min(1, p̃(z*) ÷ p̃(z)) (Metropolis et al. 1953). Plain English: always go uphill, sometimes go downhill.
Metropolis–Hastings (MH): the general version with an asymmetric proposal, where the acceptance ratio includes the q terms. Plain English: Metropolis plus a fairness correction.
Gibbs sampling: cycle through the variables, resampling each one from its conditional distribution given all the others. It is MH with acceptance probability 1. Plain English: change one knob at a time, using the exact answer for that knob.
Burn-in: discarding the first samples, before the chain has reached its equilibrium. Plain English: throw away the warm-up walk.
Mixing time: how many steps the chain needs to get close to its stationary distribution. Plain English: how long until it has really wandered everywhere.
Thinning: keeping only every M-th sample to reduce correlation between kept samples. Plain English: skip some steps so the samples look less like copies.
Effective sample size (background): the number of independent samples that a correlated sample is "worth". Plain English: 10,000 sticky samples may only count as a few hundred.
Reversible chain: a chain that satisfies detailed balance. Plain English: the film of the walk looks the same run forwards or backwards.

4. Detailed explanation, from basics to the full picture

Step 1: Why sampling at all

Goodfellow, Bengio and Courville (G17, 17.1) explain that we often cannot compute a sum or integral exactly, but we can approximate it by sampling. If s = E_p[f(x)], the estimate ŝₙ = (1/n) Σ f(x⁽ⁱ⁾) is unbiased, converges by the law of large numbers, and has variance Var[ŝₙ] = Var[f(x)] ÷ n. MacKay (29.1) adds a key point: the accuracy depends on the variance of f, not on the number of dimensions, and even about a dozen independent samples may be enough in some cases. The difficulty is that drawing samples from p is hard in high dimensions.

Step 2: The two problems, Z and dimension

In many models, such as Bayesian posteriors, we can evaluate p̃(x) but not Z. Direct methods such as rejection sampling and importance sampling (previous video, 1.43) work badly in high dimensions. MCMC takes a different approach: do not draw independent samples, but build a walk whose long-run visits follow p.

Step 3: Markov chains and the stationary distribution

A Markov chain has the first-order Markov property: the next state depends only on the present state. If the transition probabilities T do not change in time, the chain is homogeneous. A distribution is invariant (stationary) if one more step leaves it unchanged (Bishop, 11.2.1). In matrix language, v = Av: the stationary distribution is an eigenvector with eigenvalue 1 (G17, 17.3). Under ergodicity there is a single equilibrium distribution that the chain approaches from any start.

To design a chain that has our p as its stationary distribution, we use detailed balance: p(z) T(z, z′) = p(z′) T(z′, z). Summing both sides over z shows p stays unchanged. Bishop notes this is a sufficient condition, not a necessary one.

Step 4: The Metropolis rule

Propose a candidate z* from a symmetric q, so that q(z* given z) = q(z given z*). Accept it with probability

A(z*, z) = min(1, p̃(z*) ÷ p̃(z)).

If it is rejected, the previous sample is repeated (Bishop, 11.2). Because only the ratio p̃(z*) ÷ p̃(z) appears, and p̃ = Z × p, the constant Z cancels: p(x′) ÷ p(x) = p̃(x′) ÷ p̃(x). That is the whole trick that makes MCMC useful for Bayesian posteriors.

Step 5: Why it works (detailed balance)

For two points x and x′ with p̃(x′) ≥ p̃(x), the move x → x′ has probability q × 1 and the move x′ → x has probability q × p̃(x) ÷ p̃(x′). Multiply by p̃: p̃(x) × q = p̃(x′) × q × p̃(x) ÷ p̃(x′) = p̃(x) × q. Both sides are equal, so detailed balance holds and p is stationary.

Step 6: Metropolis–Hastings

When the proposal is not symmetric, for example a proposal that favours moving in one direction, the acceptance ratio must be corrected (Bishop, 11.2.2; MacKay, 29.4):

a = p̃(x′) q(x given x′) ÷ (p̃(x) q(x′ given x)), accept with probability min(1, a).

In MacKay's notation the same thing is a = P*(x′) Q(x; x′) ÷ (P*(x) Q(x′; x)). If q is symmetric, the q terms cancel and we recover Metropolis. If rejected, stay at x.

Step 7: Gibbs sampling

Gibbs sampling (Bishop, 11.3; MacKay, 29.5) cycles through the variables z₁, …, z_M. At each step it replaces one variable zᵢ with a sample from p(zᵢ given all the other variables), keeping the others fixed. This is Metropolis–Hastings with acceptance probability exactly 1 (Bishop eq. 11.49: A = 1), because the proposal is already the exact conditional. It is ergodic if no conditional distribution is zero anywhere. Bishop also notes that the method is named for Josiah Willard Gibbs (1839–1903).

Step 8: The practical side

Four practical issues come up every time (Bishop 11.2; G17 17.3; MacKay 29.4).

Burn-in. The chain starts somewhere arbitrary, so the first samples are not from p. We discard them.
Correlation. Successive samples are highly correlated. We can keep every M-th sample, or run several chains in parallel (G17).
Step size. Small steps are almost always accepted but make a slow random walk. Large steps jump to places where p̃ is tiny, so most are rejected. MacKay's rule of thumb: a random walk with step size ε needs about T ≈ (L ÷ ε)² iterations to explore a length L.
Mixing. The second-largest eigenvalue of the transition matrix determines the mixing time (G17 17.3). Chains also struggle to cross low-probability gaps between separated modes (G17 17.5).

5. Everything the video skipped

Formulas in simple words

Metropolis: accept with probability min(1, p̃(z*) ÷ p̃(z)). In words: if the new place is at least as popular, always go; if less popular, go with probability equal to the popularity ratio.
Hastings: multiply by q(x given x′) ÷ q(x′ given x), which compensates for proposals that are easier in one direction.
Monte Carlo error: Var[ŝₙ] = Var[f(x)] ÷ n. For MCMC the samples are correlated, so the real error is larger (background: this is what effective sample size measures).
Gibbs conditional for a 2-D Gaussian with correlation ρ and unit variances: x given y is a normal with mean ρy and variance 1 − ρ².

Variants

Block Gibbs: update a group of variables at once. In RBMs, all hidden units can be sampled together given the visible ones, and vice versa (G17, 17.4).
Hamiltonian Monte Carlo: uses gradient information to make large, informed moves (MacKay 30.1 introduces it; this document only names it).
Parallel chains: several chains started in different places, to help detect poor mixing (G17).
Choosing the acceptance rate: MacKay's figure caption suggests aiming for an acceptance frequency of about 0.5 in his example. (Background: for high-dimensional random-walk Metropolis, Roberts, Gelman and Gilks 1997 derived about 0.234 as the optimal rate. Do not generalise either number blindly.)

Limitations

Mixing between separated modes can take astronomically long (G17 17.5).
Strong correlation between variables makes Gibbs sampling take tiny steps along each axis.
There is no simple, certain test that the chain has converged (background); we use diagnostics.
Random walks explore inefficiently. Bishop shows that after τ steps of a random walk, E[z²] = τ ÷ 2, so the distance travelled grows only like √τ.

Background

MCMC has roots in physics. Bishop (11.2) cites Metropolis and Ulam (1949) and the Metropolis et al. (1953) algorithm.
Hastings generalised the method in 1970 (background). Geman and Geman (1984) applied Gibbs sampling to image restoration (background).
Bishop's Figure 11.9 shows a Metropolis run on a Gaussian with proposal standard deviation 0.2: of 150 candidate samples, 43 were rejected. That is 43 ÷ 150 ≈ 28.7% rejected, so 107 accepted (≈ 71.3%).

Links on the roadmap

Before: 1.42 Markov chains and 1.43 Monte Carlo sampling.
After: 1.45 Mutual information and Jensen's inequality, then 1.46 Fourier transform.

6. Worked examples with real numbers

Example A: Kavya's five villages (acceptance probabilities)

Setup: villages have sizes 1, 2, 3, 4, 5 (illustrative); the proposal is left or right with probability ½ each, and an off-river proposal means stay.

Total Z = 1 + 2 + 3 + 4 + 5 = 15. Kavya does not need this, but we use it to check the answer: target shares are 1/15, 2/15, 3/15, 4/15, 5/15.
From village 4, propose village 5: ratio 5 ÷ 4 = 1.25 ≥ 1, so accept with probability 1.
From village 4, propose village 3: ratio 3 ÷ 4 = 0.75, so accept with probability 75%.
Probability of each outcome from village 4: move to 5 is ½ × 1 = 0.5; move to 3 is ½ × 0.75 = 0.375; stay is ½ × 0.25 = 0.125. Check: 0.5 + 0.375 + 0.125 = 1.
Check detailed balance for the pair 4 and 5, using sizes as weights: p̃(4) × T(4 → 5) = 4 × 0.5 = 2, and p̃(5) × T(5 → 4) = 5 × (½ × 4/5) = 5 × 0.4 = 2. Equal.

Result: the rule satisfies detailed balance, so the shares 1 : 2 : 3 : 4 : 5 are stationary. A 100,000-step simulation gave 6.9%, 13.6%, 19.9%, 26.4%, 33.1% against targets 6.7%, 13.3%, 20.0%, 26.7%, 33.3%.

Example B: Z cancels

Setup: suppose the village sizes are only known as a function p̃(x) = x for x = 1, …, 5 (illustrative), and the true p(x) = p̃(x) ÷ Z.

Compare villages 3 and 4: p(4) ÷ p(3) = (4 ÷ Z) ÷ (3 ÷ Z).
Z appears in the numerator and denominator, so it cancels: ratio = 4 ÷ 3 ≈ 1.333.
The Metropolis rule only needs this ratio, so Kavya can run the walk without ever computing Z = 15.

Result: the acceptance ratio is p̃(x′) ÷ p̃(x) = 4 ÷ 3 for 3 → 4, so that move is always accepted, and 3 ÷ 4 = 0.75 for 4 → 3.

Example C: An asymmetric proposal (Hastings correction)

Setup: current state x with p̃(x) = 3, candidate x′ with p̃(x′) = 2. Suppose (illustrative) the proposal gives q(x′ given x) = 0.5 but the reverse q(x given x′) = 0.25.

Target ratio: p̃(x′) ÷ p̃(x) = 2 ÷ 3 ≈ 0.667.
Proposal ratio: q(x given x′) ÷ q(x′ given x) = 0.25 ÷ 0.5 = 0.5.
Hastings ratio: a = 0.667 × 0.5 = 1/3 ≈ 0.333.
Accept with probability min(1, 1/3) = 1/3.

Result: without the correction we would accept with probability 0.667; the proposal favoured going to x′, so the correct rule accepts only 1/3 of the time to stay fair.

Example D: Gibbs sampling on a 2-D Gaussian

Setup: x and y have unit variances and correlation ρ = 0.8 (illustrative). The conditional of x given y is normal with mean 0.8y and variance 1 − ρ² = 1 − 0.64 = 0.36, so the standard deviation is √0.36 = 0.6. The same holds for y given x.

Start at (2.6, −2.4), far out in the corner where p is small.
Resample x given y = −2.4: the mean is 0.8 × (−2.4) = −1.92 and the standard deviation is 0.6. The new x is typically near −1.92, so x jumps a long way from 2.6.
Resample y given the new x: the mean is 0.8 × x. If x ≈ −1.92 the mean is 0.8 × (−1.92) ≈ −1.54, so y moves from −2.4 towards the middle.
Repeat. The path moves one axis at a time, a staircase towards the centre. Every move is accepted (A = 1).
Mixing speed: the conditional sd 0.6 is small compared with the width of the whole cloud (sd 1 along each axis, longer along the diagonal), so a strongly correlated target leads to small steps and slow mixing.

Result: Gibbs needs no rejection step and walks into the high-probability region quickly from the corner, but with ρ close to 1 each step becomes tiny.

Example E: How many steps for a random walk? (MacKay's rule of thumb)

Setup: explore a length L = 10 with step size ε = 0.5 (illustrative).

L ÷ ε = 10 ÷ 0.5 = 20.
T ≈ (L ÷ ε)² = 20² = 400 iterations.
Halve the step to ε = 0.25: L ÷ ε = 40 and T ≈ 1,600, four times longer.

Result: halving the step size multiplies the exploration time by 4, which is why small steps are slow, while large steps are rejected too often.

7. Comparison tables

Metropolis versus Metropolis–Hastings versus Gibbs

Method	Proposal	Acceptance	Needs
Metropolis	Symmetric q	min(1, p̃ ratio)	p̃ only
Metropolis–Hastings	Any q	min(1, p̃ ratio × q ratio)	p̃ and q
Gibbs	Exact conditional	Always 1	All conditionals

Step size trade-off

Step size	Acceptance	Movement	Result
Very small	Almost always	Tiny, random walk	Slow exploration
Moderate	Moderate	Good	Best balance
Very large	Rarely	Mostly stays	Many repeated samples

MCMC versus plain Monte Carlo

Feature	Plain Monte Carlo	MCMC
Samples	Independent	Correlated
Needs to sample p directly	Yes	No
Handles unknown Z	Not directly	Yes (ratios)
Extra steps	None	Burn-in, thinning

8. Common mistakes and myths

Myth: you need the normalising constant. Truth: only the ratio p̃(x′) ÷ p̃(x) matters, so Z cancels.
Mistake: deleting repeated samples after a rejection. When a move is rejected, the previous sample is repeated (Bishop). Dropping the repeats biases the answer, because a village that is "sticky" would be under-counted.
Mistake: using the early samples. The first part of the run reflects the starting point, so discard a burn-in.
Myth: more samples always means independent samples. Successive samples are highly correlated, so 10,000 MCMC samples carry less information than 10,000 independent ones.
Mistake: always choosing a tiny step to get a high acceptance rate. High acceptance with tiny steps still explores slowly (T ≈ (L ÷ ε)²).
Myth: Gibbs is always better because nothing is rejected. With strongly correlated variables the steps are small and mixing is slow.
Mistake: forgetting the q correction when the proposal is asymmetric. This gives the wrong stationary distribution.
Myth: one chain that looks stable has converged. Separated modes can trap a chain (G17 17.5); running several chains helps.

9. Real-life and AI uses

Bayesian posteriors and uncertainty. MCMC samples parameters from the posterior, giving credible ranges, not just a single best answer. (Background: tools such as Stan and PyMC use Hamiltonian Monte Carlo and its NUTS variant.)
Restricted Boltzmann machines. G17 (17.4) describes block Gibbs sampling in RBMs and notes that "in the deep learning approach to undirected modeling, it is rare to use any approach other than Gibbs sampling". (Background: contrastive divergence is a training method built on Gibbs steps.)
Topic models. (Background: latent Dirichlet allocation is commonly fitted with collapsed Gibbs sampling, Griffiths and Steyvers 2004.)
Physics and other fields. G17 notes that Metropolis–Hastings is widely used in other disciplines; the method began with statistical physics (Bishop 11.2).
Generative models. Sampling is sometimes the goal itself, and MCMC provides samples from a model's distribution (G17 17.1.1).
Image restoration. (Background: Geman and Geman 1984.)

10. Self-check questions (with answers)

Why does the normalising constant Z not matter in Metropolis sampling? Because the acceptance rule uses the ratio p̃(x′) ÷ p̃(x) = p(x′) ÷ p(x), and Z cancels.
From village 4, what is the probability of accepting a move to village 3, given sizes 3 and 4? 3 ÷ 4 = 75%.
What happens when a proposal is rejected? The chain stays and the current value is counted again as a new sample.
What does detailed balance say? p(z) T(z, z′) = p(z′) T(z′, z), which makes p stationary (sufficient, not necessary).
What does the Hastings correction add? The factor q(x given x′) ÷ q(x′ given x) in the acceptance ratio, needed when the proposal is not symmetric.
What is the acceptance probability in Gibbs sampling? Exactly 1, because Gibbs is Metropolis–Hastings with the exact conditional as proposal.
What is burn-in? Discarding the first samples, before the chain has reached its stationary distribution.
Why are MCMC samples less informative than independent samples? Successive samples are highly correlated, so we may thin or run parallel chains.
What is the step-size trade-off? Small steps are accepted but explore slowly (T ≈ (L ÷ ε)²); large steps are mostly rejected.
For a 2-D Gaussian with ρ = 0.8 and unit variances, what is the conditional sd? √(1 − 0.64) = √0.36 = 0.6.

11. Key takeaways, go deeper, next

Key takeaways

MCMC builds a Markov chain whose stationary distribution is the target p(x).
Metropolis needs only ratios p̃(x′) ÷ p̃(x), so the unknown Z cancels.
Detailed balance, p(z) T(z, z′) = p(z′) T(z′, z), guarantees p is stationary.
Hastings adds the proposal ratio for asymmetric proposals; Gibbs is the special case with acceptance 1.
In practice: discard burn-in, expect correlated samples, and tune the step size. Mixing between separated modes is the hard case.

Go deeper

Bishop, Pattern Recognition and Machine Learning, sections 11.2 and 11.3.
MacKay, Information Theory, Inference, and Learning Algorithms, chapter 29 (Monte Carlo methods) and 30.1 (Hamiltonian Monte Carlo).
Goodfellow et al., Deep Learning, chapter 17 (mixing and RBMs).

Next on the roadmap: 1.45 Mutual information and Jensen's inequality.

12. Sources and further reading

Bishop, Pattern Recognition and Machine Learning (2006), Chapter 11: Sampling Methods, sections 11.2 Markov Chain Monte Carlo, 11.2.1 Markov chains, 11.2.2 The Metropolis–Hastings algorithm, 11.3 Gibbs Sampling
Goodfellow, Bengio and Courville, Deep Learning (2016), Chapter 17: Monte Carlo Methods, sections 17.1 to 17.5
MacKay, Information Theory, Inference, and Learning Algorithms (2003), Chapter 29: Monte Carlo Methods, sections 29.1, 29.4 Metropolis–Hastings, 29.5 Gibbs sampling
Grinstead and Snell, Introduction to Probability (AMS), Chapter 11: Markov Chains, sections 11.1 and 11.3 Ergodic chains
Wikipedia, Monte Carlo method (secondary source only), Overview and history

Accuracy note: all numbers about the villages, the Gibbs path, the Hastings example and the step counts are illustrative or computed from stated assumptions (the 100,000-step simulation used numpy seed 1 and is one run). Statements marked "(background)", including Hastings 1970, Geman and Geman 1984, Roberts, Gelman and Gilks 1997, effective sample size, Stan, PyMC, NUTS, contrastive divergence and collapsed Gibbs for topic models, are not from the listed sources and should be checked before being relied on. The Monte Carlo history comes from Wikipedia as a second source.

MCMC: Metropolis–Hastings and Gibbs: study notes