Skip to content
Tutorials Center
My learning

Topics

Lesson 32 of 39 · Non-Equilibrium and Monte Carlo Methods

The Metropolis Algorithm

Learn how Markov chain Monte Carlo samples the Boltzmann distribution: detailed balance, the Metropolis acceptance rule, step size, equilibration and autocorrelation, with runnable examples.

Most systems in statistical mechanics have far too many states to sum over. A lattice of just 100 Ising spins has 2^100 configurations, more than the number of grains of sand on Earth. Yet we want averages like ⟨E⟩ and ⟨m⟩ over the Boltzmann distribution. The way out is to sample: generate configurations with the correct probabilities and average over them. The Metropolis algorithm (1953) is the classic recipe, and it is a Markov chain Monte Carlo method.

The goal

We want configurations x drawn with probability

Text
P(x) = e^(-E(x)/kT) / Z

without knowing Z. The trick is to build a random walk through configuration space whose long-run visiting frequencies equal P(x). The walk is a Markov chain: the next configuration depends only on the current one, with transition probability W(x → x').

Detailed balance

A sufficient condition for P to be the stationary distribution of the chain is detailed balance:

Text
P(x) W(x → x') = P(x') W(x' → x)

In words: in equilibrium, the flow from x to x' equals the flow back. Dividing both sides gives W(x → x') / W(x' → x) = P(x')/P(x) = e^(-βΔE), with ΔE = E(x') - E(x). The normalization Z cancels. Metropolis satisfied this with a two-step move:

  1. Propose a new configuration x' by a small random change, using a symmetric rule (proposing x → x' is as likely as x' → x).
  2. Accept it with probability min(1, e^(-βΔE)). If it is rejected, keep the old configuration and count it again in the averages.

Moves that lower the energy are always accepted; moves that raise it are accepted with the Boltzmann probability. Nothing more is needed.

When a move is rejected, the old state must be counted again. Skipping rejected steps biases averages toward high-acceptance regions.

Sampling a harmonic oscillator

A particle in a potential U(x) = ½ x² at kT = 1 has P(x) ∝ e^(-x²/2), a Gaussian with ⟨x⟩ = 0 and ⟨x²⟩ = 1. The code runs Metropolis with a uniform proposal x' = x + δ·u, u ∈ [-1, 1], and checks the average of x², plus ⟨U⟩ = ½kT, which is equipartition.

Python Metropolis sampling of a Gaussian

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sample mean of x² is near 1 within statistical error. We discarded the first 1000 steps: the chain started at x = 5, far out in the tail, and needed a while to forget that. This is equilibration or burn-in.

Step size, acceptance and autocorrelation

Successive Metropolis samples are correlated. A tiny step size δ gives high acceptance but slow exploration; a huge δ proposes mostly rejected moves. Both give a chain that moves slowly. The integrated autocorrelation time τ measures how many steps are needed for one effectively independent sample, so the error of an average over n steps is about σ √(2τ/n).

The code estimates τ from the autocorrelation function of x² and shows how it depends on δ.

Python Acceptance rate and autocorrelation time versus step size

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The best step size is of order a few times the width of the distribution (here about 2 to 4), where acceptance is roughly 40 to 60 percent. A common rule of thumb is to tune δ so that about half of the moves are accepted in simple problems.

Applying it to many particles

Everything above carries over to a system of many variables: propose changing one spin or one particle, compute the energy change ΔE from just its neighbors (cheap!), and accept or reject. A sweep is N such attempted updates. In the next lesson you will use exactly this to simulate the 2D Ising model.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What does detailed balance ensure?

    If P(x)W(x→x') = P(x')W(x'→x), then P is invariant under the chain.
  2. 2. The Metropolis acceptance probability for a move with energy change ΔE is

    Downhill moves are always accepted; uphill moves with probability e^(-βΔE).
  3. 3. When a proposed move is rejected, you should

    The stay-put outcome is part of the Markov chain; omitting it biases averages.
  4. 4. Why is a very small step size a poor choice?

    Detailed balance holds for any δ; small steps just give strongly correlated samples.

Summary

  • Metropolis builds a Markov chain with stationary distribution e^(-βE)/Z using detailed balance; Z is never needed.
  • Accept with probability min(1, e^(-βΔE)); count rejected steps as repeats.
  • Discard an initial burn-in; estimate errors using the autocorrelation time τ.
  • Tune the step size for moderate acceptance (roughly 40-60 percent for simple cases).

Next: Monte Carlo Simulation of the 2D Ising Model