Biostatistics · Advanced

Metropolis MCMC sampler

Written by SignalsLab

Early edition: these lessons are being reviewed.

Content

Summary

The Metropolis algorithm draws samples from a probability distribution known only up to a normalising constant, such as a Bayesian posterior. It proposes a random move and accepts it with probability equal to the ratio of target densities (capped at 1). The resulting Markov chain has the target as its stationary distribution, so a histogram of its visits approximates the posterior.

Intuition

Imagine a hiker walking in fog over a landscape whose height is the posterior density. The hiker cannot see the whole map, only the height at the current spot and at a trial spot nearby. If the trial spot is higher, they always step there. If it is lower, they step there only with probability equal to the ratio of heights, so they sometimes go downhill. Over a long walk, the time spent in each region is proportional to its height, which is exactly the posterior probability. Because only ratios matter, the intractable normalising constant (the marginal likelihood) cancels. The proposal width is a tuning knob: too small and the chain creeps slowly with high acceptance, too large and most proposals are rejected so the chain sticks. An acceptance rate around 20-40 percent is a good target in moderate dimensions.

Key equations

π(θ∣y)∝p(y∣θ)p(θ)
(1)

The target is known only up to a constant: likelihood times prior.

θ∗∼q(θ∗∣θt),q(θ∗∣θ)=q(θ∣θ∗)
(2)

A symmetric proposal, for example a normal random walk centred at the current value.

α=min⁡(1,π(θ∗)π(θt))
(3)

Acceptance probability; the normalising constant cancels in the ratio.

π(x)P(x→x′)=π(x′)P(x′→x)
(4)

Detailed balance, which guarantees that π is stationary.

Derivation

  1. Goal: build a Markov chain with transition kernel P whose stationary distribution is π.
  2. Sufficient condition: detailed balance, π(x)P(x→x′)=π(x′)P(x′→x) for all x,x′.
  3. For x′ different from x, P(x→x′)=q(x′|x)α(x,x′).
  4. With symmetric q, detailed balance requires π(x)α(x,x′)=π(x′)α(x′,x).
  5. Choose α(x,x′)=min⁡(1,π(x′)/π(x)). If π(x′)≥π(x), then α(x,x′)=1 and α(x′,x)=π(x)/π(x′), so both sides equal π(x).
  6. The case π(x′)<π(x) is symmetric, so detailed balance holds and π is stationary.
  7. With irreducibility and aperiodicity, the chain converges to π, and ergodic averages estimate posterior expectations.

Worked example

Problem

Target proportional to θ3(1−θ)2 on (0,1), from 3 successes and 2 failures with a flat prior. The chain is at θ=0.5 and proposes θ∗=0.7. Compute the acceptance probability. If the uniform draw is u=0.8, is the move accepted?

  1. Compute π(0.5)=0.53×0.52=0.125×0.25=0.03125.
  2. Compute π(0.7)=0.73×0.32=0.343×0.09=0.03087.
  3. Ratio = 0.03087/0.03125 = 0.988.
  4. α=min⁡(1,0.988)=0.988.
  5. Compare u=0.8 with α: 0.8<0.988, so accept.

Answer α is about 0.988; the move to 0.7 is accepted, so θt+1=0.7.

Common mistakes

  • Forgetting that on rejection the chain repeats the current value; dropping the repeat biases the samples.
  • Using an asymmetric proposal without the Hastings correction q(θ|θ∗)/q(θ∗|θ).
  • Judging convergence from a single chain or ignoring burn-in; run several chains and check R-hat and trace plots.
  • Tuning for a very high acceptance rate; tiny steps give strongly autocorrelated samples.
  • Treating samples as independent when computing standard errors; use effective sample size.
  • Computing ratios of raw densities and underflowing; work with log densities.

Animation

Animation coming soon

The animated version of this lesson is being prepared for the web. In the Signals AI app, lessons are drawn step by step.

Code

scene.py(142 lines)
import sys
import numpy as np
from manim import *
from blocks import *


def metropolis_sampler(target_mu, target_sigma, n_steps, initial_x, proposal_sigma):
    """
    Run Metropolis-Hastings MCMC.
    Returns list of (x, accepted) tuples.
    """
    np.random.seed(42)
    path = []
    current_x = initial_x
    
    for _ in range(n_steps):
        # Proposal: symmetric Gaussian random walk
        proposed_x = current_x + np.random.normal(0, proposal_sigma)
        
        # Target: Normal(target_mu, target_sigma)
        # Log-probability proportional to -0.5 * ((x - mu)/sigma)^2
        log_target_current = -0.5 * ((current_x - target_mu) / target_sigma)**2
        log_target_proposed = -0.5 * ((proposed_x - target_mu) / target_sigma)**2
        
        # Acceptance ratio
        log_alpha = log_target_proposed - log_target_current
        
        if np.log(np.random.uniform()) < log_alpha:
            current_x = proposed_x
            path.append((current_x, True))
        else:
            path.append((current_x, False))
            
    return path


# Parameters
TARGET_MU = 0.0
TARGET_SIGMA = 1.0
N_STEPS = 200
INITIAL_X = -3.0
PROPOSAL_SIGMA = 0.5

# Run simulation
TRACE = metropolis_sampler(TARGET_MU, TARGET_SIGMA, N_STEPS, INITIAL_X, PROPOSAL_SIGMA)


class Main(Scene):
    def construct(self):
        self.camera.background_color = "#111111"
        
        TitleCard(self, "Metropolis MCMC", "Sampling from a Target Distribution")
        
        # Setup Axes
        # X axis: Iteration
        # Y axis: x value
        
        axes = Axes(
            x_range=[0, N_STEPS, 50],
            y_range=[TARGET_MU - 3 * TARGET_SIGMA, TARGET_MU + 3 * TARGET_SIGMA, 0.5],
            x_length=10,
            y_length=5,
            axis_config={"include_tip": True, "color": C_DIM}
        )
        axes.to_edge(LEFT, buff=0.5)
        axes.to_edge(UP, buff=0.5)
        
        # Place labels carefully to avoid overlap
        x_label = Text("Iteration", font_size=22, color=WHITE)
        x_label.next_to(axes.x_axis.get_end(), RIGHT + DOWN, buff=0.2)
        
        y_label = Text("x value", font_size=22, color=WHITE)
        y_label.next_to(axes.y_axis.get_end(), UP + LEFT, buff=0.2)
        
        self.play(Create(axes), FadeIn(x_label), FadeIn(y_label))
        
        # Target distribution line (mean)
        target_line = DashedLine(
            axes.c2p(0, TARGET_MU),
            axes.c2p(N_STEPS, TARGET_MU),
            color=C_ACCENT,
            dash_length=0.2
        )
        # Place label on the LEFT side of the line to avoid right-side clutter
        target_label = Text(f"Target Mean ({TARGET_MU})", font_size=20, color=C_ACCENT)
        target_label.next_to(axes.c2p(0, TARGET_MU), LEFT, buff=0.2)
        
        self.play(Create(target_line), FadeIn(target_label))
        
        # Plot the trace
        trace_points = []
        accepted_count = 0
        
        for i, (x, accepted) in enumerate(TRACE):
            trace_points.append(axes.c2p(i, x))
            if accepted:
                accepted_count += 1
        
        # Create segments for the trace line
        segments = VGroup()
        for i in range(len(trace_points) - 1):
            seg = Line(trace_points[i], trace_points[i+1], color=C_MAIN, stroke_width=2)
            segments.add(seg)
        
        self.play(Create(segments), run_time=2)
        
        # Overlay dots for accepted/rejected
        dots = VGroup()
        for i, (x, accepted) in enumerate(TRACE):
            pt = trace_points[i]
            color = C_GOOD if accepted else C_BAD
            dot = Dot(pt, color=color, radius=0.06)
            dots.add(dot)
            
        self.play(FadeIn(dots), run_time=1.5)
        
        # Final caption
        acceptance_rate = accepted_count / N_STEPS
        StepCaption(self, f"Acceptance Rate: {acceptance_rate:.1%} | Target: N({TARGET_MU}, {TARGET_SIGMA})")
        
        self.wait(2)


if __name__ == "__main__" and "--selftest" in sys.argv:
    # Check that we generated the correct number of steps
    assert len(TRACE) == N_STEPS
    
    # Check that accepted/rejected flags are boolean
    for x, accepted in TRACE:
        assert isinstance(accepted, bool)
        
    # Check that the values are within reasonable bounds (3 sigma)
    for x, accepted in TRACE:
        assert TARGET_MU - 4 * TARGET_SIGMA <= x <= TARGET_MU + 4 * TARGET_SIGMA, f"Value {x} out of bounds"
        
    # Check that the mean of the trace is close to the target mean (after burn-in)
    # Simple check: the overall mean should be somewhat close
    trace_values = [x for x, _ in TRACE]
    trace_mean = np.mean(trace_values)
    assert abs(trace_mean - TARGET_MU) < 1.0, f"Trace mean {trace_mean} too far from target {TARGET_MU}"
    
    print("ok")

The Manim scene code that draws this lesson's animation in the Signals AI app (Python, Manim Community).

ccBYNC© 2026 SignalsLab. Lesson text shared as is under CC BY-NC 4.0.