Interactive demo · Bayesian and Probabilistic Machine Learning · Chapter 11

Markov chain Monte Carlo: Metropolis and Gibbs

The target is a correlated Gaussian in two dimensions, drawn as its one- and two-standard-deviation ellipses. Metropolis proposes a step from an isotropic Gaussian of size ρ and accepts it with probability min(1, p(z*)/p(z)) (green moves are accepted, red ones rejected). Gibbs sampling redraws one coordinate at a time from its conditional distribution. Both chains explore by a random walk, so when the target is elongated the number of steps per independent sample grows like (σ_max/σ_min)².

Sampler

Proposal size ρ

Gibbs update

Target correlation r

Run

Lower right panel

Try these

Target: mean (1.5, 1.5), both marginal standard deviations s = 0.529, correlation r, so σ_max = s√(1+r) and σ_min = s√(1−r). With r = 0.759 this is the target of Figure 11.9, whose drawn ellipse is the two-standard-deviation contour (see the notes). The chain starts at (1, 1) for Metropolis and at (0.8, 0.8) for Gibbs; the random numbers are seeded, so a class sees the same pictures.

In the lecture notes

Chapter 11 notes: Section 11.2 (Markov chain Monte Carlo, the Metropolis algorithm and the random walk), Section 11.2.1 (Markov chains, invariance, detailed balance, ergodicity), Section 11.2.2 (Metropolis-Hastings and the choice of the proposal scale, Figure 11.10), Section 11.3 (Gibbs sampling, the widths l and L, over-relaxation).
Gradient-based moves that avoid the random walk: the companion demo slice sampling and Hamiltonian Monte Carlo.
Python code: code/ch11_sampling.py (functions metropolis, gibbs_gaussian, overrelaxed_gibbs, ordered_overrelaxed_gibbs; Figures 11.9 to 11.12) and the checks in code/checks_ch11.py. Passing JSRandom(seed) to those functions reproduces this page's chains number for number.