Continuous Function

Probability

MCMC: Metropolis-Hastings and Gibbs Sampling

MCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

status: reviewimportance: importantdifficulty 4/5math: graduateread: 24mlive demo
Back to ProbabilityNext: Variational Inference (review)

Concept Structure

MCMC: Metropolis-Hastings and Gibbs Sampling

01Intuition

Start with the picture, metaphor, or geometric mechanism.

02Math

Make the objects explicit and connect them with notation.

03Code

Mirror the equations with runnable implementation details.

04Interactive Demo

Manipulate the mechanism and watch the idea respond.

6prerequisites
1next concepts
2related links

Learner Contract

What this page should let you do.

You are here becauseMCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

This Probability concept is the current idea: keep the same invariant visible across Intuition, Math, Code, Interactive Demo.

By the end4/4 sections ready | runnable code expected | live demo

Explain the mechanism, trace the main notation, and test one prediction in the live demo.

Do this firstIntuition

Read the intuition before the notation; the math should name a mechanism you already felt.

Then go nextVariational Inference (review)

Follow this edge after making one prediction here; the next page should reuse the result, not restart the route.

Test the linkManipulate one control and predict the visible change.Then continue to Variational Inference (review)

Claim/source review status

Substantive review recorded

1/1 claims have bounded review metadata; still check caveats and source scope.Metadata-derived; review may be AI-assisted. Not a human certification.
Claims1/1 reviewed
Sources4 cited
Codeattached
Demolive
Reviewed2026-07-02
Updatedpage 2026-07-02

Learning item flow

4/4 sections readyAsk about thisResearch room
ConceptMCMC: Metropolis-Hastings and Gibbs SamplingProbabilityEquationMCMC: Metropolis-Hastings and Gibbs Sampling equation 1Exact equationCodeMCMC: Metropolis-Hastings and Gibbs Sampling runnable code 1Exact runnable codeDemoMCMC: Metropolis-Hastings and Gibbs Sampling interactive demoInteractive demoClaimMCMC builds a Markov chain with the target as its stationary distribu...Exact claim checkSourceCS228 Notes: Sampling MethodsExact source
ConceptMCMC: Metropolis-Hastings and Gibbs SamplingProbability
6 sources attachedLocal snapshot ready
concept:probability/mcmc-metropolis-hastings-gibbs
CodenearbyPredictbefore revealRoomitem handoff
01IntuitionStart with the picture, metaphor, or geometric mechanism.02MathMake the objects explicit and connect them with notation.03CodeMirror the equations with runnable implementation details.04Interactive DemoManipulate the mechanism and watch the idea respond.
01

01

Intuition

Build the mental picture first so the rest of the page has something to attach to.

Section prompt

Conjugate Bayesian updating gives a rare luxury: multiply likelihood by prior and read the posterior exactly.

Most useful Bayesian models do not stay that polite. A posterior can be known only up to a constant:

π(x)=π~(x)Z,Z=∑xπ~(x)\pi(x)=\frac{\tilde\pi(x)}{Z}, \qquad Z=\sum_x \tilde\pi(x)

or, in a continuous model, an integral we cannot compute. The unnormalized score π~(x)\tilde\pi(x) is easy enough to evaluate at one state, but the normalizer ZZ is the hard part.

Markov chain Monte Carlo changes the job. Instead of trying to draw independent samples from π\pi directly, we build a Markov chain:

X0→X1→X2→⋯X_0 \to X_1 \to X_2 \to \cdots

whose long-run distribution is π\pi. The samples are correlated, so we do not get iid magic. But if the chain is designed well, run long enough, and checked carefully, averages over the chain can approximate posterior expectations.

Metropolis-Hastings is the proposal-and-correction version:

  1. stand at the current state xx;
  2. propose a candidate x′x' from a proposal distribution q(x′∣x)q(x'\mid x);
  3. accept the move with a probability that compares the proposed target score to the current target score.

The important surprise is that the global normalizer cancels. If the target score doubles, an uphill symmetric proposal is accepted. If the score drops to one quarter, the move is accepted only one quarter of the time. Rejections are not failure; they are how the chain keeps the right long-run distribution.

Gibbs sampling is the conditional-resampling version. Instead of proposing an arbitrary move, it chooses one coordinate and samples that coordinate from its exact conditional distribution while holding the other coordinates fixed:

xj∼π(xj∣x−j).x_j \sim \pi(x_j\mid x_{-j}).

That can be easier than sampling the full joint distribution. In a high-dimensional model, a single conditional can be tractable even when the full posterior is not.

The learner move is to separate four ideas:

  1. π~(x)\tilde\pi(x) scores states but may not be normalized;
  2. the transition rule defines how the chain moves;
  3. stationarity means the target distribution is preserved by the transition rule;
  4. mixing and diagnostics decide whether a finite run deserves trust.

MCMC is not "run a loop and believe the histogram." It is a way to turn local probability comparisons into global posterior exploration, with correlation and convergence caveats attached.

02

02

Math

Translate the story into symbols, assumptions, and a derivation you can inspect.

Section prompt
Equation 1π(x′)=∑x∈Xπ(x)K(x,x′)for every x′∈X.\pi(x')=\sum_{x\in\mathcal X}\pi(x)K(x,x') \quad\text{for every }x'\in\mathcal X.Equation 2π(x)K(x,x′)=π(x′)K(x′,x)for all x,x′.\pi(x)K(x,x')=\pi(x')K(x',x) \quad\text{for all }x,x'.

Let X\mathcal X be a finite state space and let π(x)\pi(x) be the target distribution. A Markov chain transition kernel K(x,x′)K(x,x') gives the probability of moving from xx to x′x' in one step.

The target distribution is stationary for the chain when

π(x′)=∑x∈Xπ(x)K(x,x′)for every x′∈X.\pi(x')=\sum_{x\in\mathcal X}\pi(x)K(x,x') \quad\text{for every }x'\in\mathcal X.

This equation says that if the chain's current state is already distributed as π\pi, one transition leaves it distributed as π\pi.

A common sufficient condition is detailed balance:

π(x)K(x,x′)=π(x′)K(x′,x)for all x,x′.\pi(x)K(x,x')=\pi(x')K(x',x) \quad\text{for all }x,x'.

Detailed balance says the target-weighted probability flow from xx to x′x' matches the reverse flow. Summing detailed balance over all xx gives stationarity.

Metropolis-Hastings

Metropolis-Hastings starts with a proposal distribution q(x′∣x)q(x'\mid x). For x′≠xx'\ne x, define

K(x,x′)=q(x′∣x)α(x,x′),K(x,x')=q(x'\mid x)\alpha(x,x'),

where the acceptance probability is

α(x,x′)=min⁡(1,π(x′)q(x∣x′)π(x)q(x′∣x)).\alpha(x,x') = \min\left( 1, \frac{\pi(x')q(x\mid x')}{\pi(x)q(x'\mid x)} \right).

If the proposal is rejected, the chain stays at xx. The self-transition probability is whatever mass is left:

K(x,x)=1−∑x′≠xK(x,x′).K(x,x)=1-\sum_{x'\ne x}K(x,x').

When the target is known only up to a normalizing constant, π(x)=π~(x)/Z\pi(x)=\tilde\pi(x)/Z. Substitute that into the ratio:

π(x′)q(x∣x′)π(x)q(x′∣x)=π~(x′)q(x∣x′)π~(x)q(x′∣x).\frac{\pi(x')q(x\mid x')}{\pi(x)q(x'\mid x)} = \frac{\tilde\pi(x')q(x\mid x')}{\tilde\pi(x)q(x'\mid x)}.

The same unknown ZZ appears upstairs and downstairs, so it cancels.

For a symmetric proposal, q(x′∣x)=q(x∣x′)q(x'\mid x)=q(x\mid x'), the formula becomes

α(x,x′)=min⁡(1,π~(x′)π~(x)).\alpha(x,x') = \min\left(1,\frac{\tilde\pi(x')}{\tilde\pi(x)}\right).

That is the finite-state rule in the demo. Moving from score 33 to score 88 is accepted with probability 11. Moving from score 88 to score 22 is accepted with probability 2/8=0.252/8=0.25.

Gibbs Sampling

Suppose the state is split into coordinates x=(x1,…,xd)x=(x_1,\ldots,x_d). A Gibbs update chooses one coordinate jj and samples

xj′∼π(xj∣x−j),x−j′=x−j.x'_j \sim \pi(x_j\mid x_{-j}), \qquad x'_{-j}=x_{-j}.

For two binary coordinates, if y=1y=1 is fixed and the unnormalized scores are

π~(x=0,y=1)=3,π~(x=1,y=1)=8,\tilde\pi(x=0,y=1)=3, \qquad \tilde\pi(x=1,y=1)=8,

then

Pr⁡(x=1∣y=1)=83+8=0.727….\Pr(x=1\mid y=1) = \frac{8}{3+8} =0.727\ldots.

The full target normalizer over all states is not needed. The conditional normalizer only sums over the coordinate being refreshed.

Finite-Run Caveat

Stationarity is an asymptotic design property. A useful MCMC run also needs the chain to be irreducible enough to reach the relevant states, aperiodic enough not to oscillate deterministically, and well-mixed enough that finite samples represent the target. Burn-in, autocorrelation, effective sample size, multiple chains, and posterior predictive checks are practical warnings, not decorative statistics.

03

03

Code

Keep the implementation aligned with the notation so the algorithm is legible.

Section prompt
Runnable code 1import numpy as np states = [(0, 0), (0, 1), (1, 0), (1, 1)] score = {(0, 0): 1.0, (0, 1): 3....python
import numpy as np

states = [(0, 0), (0, 1), (1, 0), (1, 1)]
score = {(0, 0): 1.0, (0, 1): 3.0, (1, 0): 2.0, (1, 1): 8.0}
target = {s: score[s] / sum(score.values()) for s in states}

def mh_step(current, proposal, u):
    ratio = score[proposal] / score[current]  # symmetric proposal
    alpha = min(1.0, ratio)
    accepted = u <= alpha
    return proposal if accepted else current, alpha, accepted

def gibbs_refresh_x_when_y_is_1(u):
    p_x1 = score[(1, 1)] / (score[(0, 1)] + score[(1, 1)])
    return ((1, 1) if u <= p_x1 else (0, 1)), p_x1

chain = [(0, 0)]
proposals = [(0, 1), (1, 1), (1, 0), (0, 0), (1, 1), (0, 1)]
uniforms = [0.20, 0.91, 0.12, 0.70, 0.40, 0.60]

for proposal, u in zip(proposals, uniforms):
    nxt, alpha, accepted = mh_step(chain[-1], proposal, u)
    chain.append(nxt)
    print(chain[-2], "->", proposal, "alpha", round(alpha, 3),
          "u", u, "accepted", accepted, "next", nxt)

print("target", target)
print("Gibbs x|y=1", gibbs_refresh_x_when_y_is_1(0.62))

The code never uses the target normalizer inside mh_step. It only compares unnormalized scores. The normalizer appears when we print target, because that is a diagnostic view of the toy distribution, not a requirement for making one Metropolis-Hastings move.

04

04

Interactive Demo

Use direct manipulation to connect the explanation to a moving system.

Section prompt

The Transition Ledger Lab hides the acceptance or conditional ledger until you commit.

Switch among three situations:

  1. an uphill Metropolis-Hastings proposal from score 33 to score 88;
  2. a downhill Metropolis-Hastings proposal from score 88 to score 22;
  3. a Gibbs update that refreshes xx while holding y=1y=1 fixed.

Before revealing, decide whether the next move should accept, reject, resample a coordinate from a conditional, or require the global normalizer. Then reveal the ratio, the uniform draw, the next state, and a small stationarity check for the finite chain.

Live Concept Demo

Explore MCMC: Metropolis-Hastings and Gibbs Sampling

The stage is code-native and interactive. Use it to test the explanation against the mechanism.

difficulty 4/5graduatecode-aligned
Demo Prediction Checkpoint

Manipulate one control and predict the visible change.

Commit to what MCMC: Metropolis-Hastings and Gibbs Sampling should make visible before reading the result.

After The First Pass

Turn the concept into an inspected object.

Once the invariant is visible in the intuition, math, code, and demo, use these panels to inspect the mechanism visually, check source support, practice the idea, and attach a grounded research question.

Mechanism Storyboard

See the idea move before the page explains it

MCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

Prediction open01 / Intuition
Prediction lens

Start with the picture, metaphor, or geometric mechanism.

Commit first

Before reading further, choose the kind of change MCMC: Metropolis-Hastings and Gibbs Sampling should make visible.

Visual Inquiry

Make the image answer a mathematical question

MCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

4/4 stages readyLive demo connected
Prediction

Which visible object should carry the first intuition?

Commit first

Pick the cue that should make MCMC: Metropolis-Hastings and Gibbs Sampling easier to reason about before the page gives the answer.

Source Grounding

Canonical references for the mechanism on this page.

course-notes · 2026CS228 Notes: Sampling MethodsStanford CS228

Grounds Monte Carlo sampling, Markov-chain stationary distributions, detailed balance, Metropolis-Hastings acceptance ratios, Gibbs sampling, burn-in, and proposal/mixing cautions.

Open source
course-notes · 2015Machine Learning and Neural Computation: Markov Chain Monte CarloGatsby Computational Neuroscience Unit, UCL

Supports detailed-balance reasoning, unnormalized target densities, the Metropolis acceptance rule, Gibbs sampling, and the warning that correlated samples require care.

Open source
course-notes · 2015MIT 6.438 Inference: Gibbs SamplingDavid Sontag

Supports the Gibbs update as resampling one variable from its conditional distribution while holding the rest fixed, along with practical burn-in and mixing discussion.

Open source
book · 2016Deep Learning, Chapter 17: Monte Carlo MethodsGoodfellow, Bengio, and Courville

Deep-learning textbook anchor for MCMC as a sampling method and for the practical caveat that mixing can become slow in high-dimensional energy landscapes.

Open source
paper · 1953Equation of State Calculations by Fast Computing MachinesMetropolis, Rosenbluth, Rosenbluth, Teller, and Teller

Historical source for the Metropolis sampling method.

Open source
paper · 1970Monte Carlo Sampling Methods Using Markov Chains and Their ApplicationsW. K. Hastings

Historical source for the generalized Metropolis-Hastings transition rule.

Open source

Claim Review

MCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

Status1 substantive review recorded

Claims without a substantive review badge still need exact source-support review.

Sources6 references

cs228-sampling-notes, gatsby-mcmc-lecture, mit-sontag-gibbs, goodfellow-2016-deep-learning-monte-carlo, metropolis-1953, hastings-1970

Local checks4 local checks

Use equations, runnable code, and demos to check whether the source support is operational.

Substantively reviewedMCMC builds a Markov chain with the target as its stationary distribution; Metropolis-Hastings uses target-score ratios where Z cancels, and Gibbs refreshes coordinates from full conditionals.Claim metadata: source checked

The sources support the page's finite-state MCMC witness, the stationarity/detailed-balance math, the symmetric-proposal Metropolis-Hastings acceptance rule, the Gibbs full-conditional update, and the caveat that correlated samples need burn-in, mixing, and diagnostic scrutiny.

Sources: CS228 Notes: Sampling Methods, Machine Learning and Neural Computation: Markov Chain Monte Carlo, MIT 6.438 Inference: Gibbs Sampling, Deep Learning, Chapter 17: Monte Carlo MethodsFinite discrete witness only; excludes continuous-state measure theory, Hamiltonian Monte Carlo, slice sampling, adaptive MCMC, exact convergence diagnostics, high-dimensional posterior geometry, and a GPT Pro publication pass.A bounded review summary is present; still check caveats and exact reference scope.

Checked Stanford CS228 notes for Markov-chain stationarity, detailed balance, Metropolis-Hastings ratios, Gibbs sampling, burn-in, and mixing caveats; checked Gatsby/UCL MCMC notes for detailed balance and unnormalized target-density framing; checked MIT Sontag Gibbs slides for one-coordinate conditional updates; checked the Deep Learning Book for MCMC's role in machine learning and slow-mixing caveats; used Metropolis, Hastings, and Geman & Geman as historical anchors. GPT Pro publication critique remains pending.

Reviewer: codex-local-source-review; reviewed 2026-07-02
source-span-cs228-sampling-notessource-span-gatsby-mcmc-lecturesource-span-mit-sontag-gibbsEquation 1Equation 2Runnable code 1Interactive demo

Source support candidates

course-notes 2026CS228 Notes: Sampling Methods

Grounds Monte Carlo sampling, Markov-chain stationary distributions, detailed balance, Metropolis-Hastings acceptance ratios, Gibbs sampling, burn-in, and proposal/mixing cautions.

course-notes 2015Machine Learning and Neural Computation: Markov Chain Monte Carlo

Supports detailed-balance reasoning, unnormalized target densities, the Metropolis acceptance rule, Gibbs sampling, and the warning that correlated samples require care.

course-notes 2015MIT 6.438 Inference: Gibbs Sampling

Supports the Gibbs update as resampling one variable from its conditional distribution while holding the rest fixed, along with practical burn-in and mixing discussion.

book 2016Deep Learning, Chapter 17: Monte Carlo Methods

Deep-learning textbook anchor for MCMC as a sampling method and for the practical caveat that mixing can become slow in high-dimensional energy landscapes.

Mechanism checks

Equation 1
π(x′)=∑x∈Xπ(x)K(x,x′)for every x′∈X.\pi(x')=\sum_{x\in\mathcal X}\pi(x)K(x,x') \quad\text{for every }x'\in\mathcal X.
Equation 2
π(x)K(x,x′)=π(x′)K(x′,x)for all x,x′.\pi(x)K(x,x')=\pi(x')K(x',x) \quad\text{for all }x,x'.
Runnable code 1import numpy as np states = [(0, 0), (0, 1), (1, 0), (1, 1)] score = {(0, 0): 1.0, (0, 1): 3....Demo stateLive mechanism probe

Practice Loop

Try the idea before it explains itself

MCMC turns an intractable target distribution into a Markov chain: Metropolis-Hastings accepts or rejects proposals by a target ratio, while Gibbs resamples coordinates from conditionals.

Readiness0/3 checks ready
Predict

Before touching the demo, predict one visible change that should happen in MCMC: Metropolis-Hastings and Gibbs Sampling.

Hint 1

Reveal when your model needs a nudge.

Hint 2

Reveal when your model needs a nudge.

Hint 3

Reveal when your model needs a nudge.

Grounded research drawerClose
ConceptMCMC: Metropolis-Hastings and Gibbs SamplingProbability
Runnable code comparisonMCMC: Metropolis-Hastings and Gibbs Sampling runnable code 1states = [(0, 0), (0, 1), (1, 0), (1, 1)]Prediction before revealMCMC: Metropolis-Hastings and Gibbs Sampling interactive demoManipulate one control and predict the visible change.
Grounded room questionWhat is the smallest example that makes MCMC: Metropolis-Hastings and Gibbs Sampling click without losing the math?Local snapshot ready

Research Room

Attach the question to a claim, equation, code, or demo

Pick the concept, equation, source, runnable code, claim, misconception, or demo state before asking for help. The handoff keeps that page item in context.
Next local actionNo local draft saved yet

Open the draft below to save one note and next action in this browser.

conceptProbability

MCMC: Metropolis-Hastings and Gibbs Sampling

Attached question

What is the smallest example that makes MCMC: Metropolis-Hastings and Gibbs Sampling click without losing the math?

Local action draftNo local draft saved yetExpand only when ready to capture one local next action
Local action draft

This draft stays in this browser, attached to the selected learning item.

No local draft saved.
Evidence to inspect
  • References to inspect: attached references on this page.
  • Definition, prerequisite, and contrast concept links
  • The equation or runnable code that makes the concept operational
  • One demo state that shows the invariant instead of a slogan
What would resolve this
  • The learner can state the mechanism in their own words
  • The learner can name the prerequisite that would repair confusion
  • The learner can predict how the mechanism changes under one perturbation
Grounded AI handoff

I am working in Continuous Function's research reading room. Object: concept - MCMC: Metropolis-Hastings and Gibbs Sampling Selected item key: recorded for copy. Context: Probability Page anchor: recorded for copy. Open question: What is the smallest example that makes MCMC: Metropolis-Hastings and Gibbs Sampling click without losing the math? Evidence to inspect: - References to inspect: attached references on this page. - Definition, prerequisite, and contrast concept links - The equation or runnable code that makes the concept operational - One demo state that shows the invariant instead of a slogan What would resolve this: - The learner can state the mechanism in their own words - The learner can name the prerequisite that would repair confusion - The learner can predict how the mechanism changes under one perturbation Answer as a careful research tutor: stay source-grounded, separate verified evidence from assumptions, name the relevant math objects, and end with one next action.

View it in context
concept/concept-notebook/probability/mcmc-metropolis-hastings-gibbs concept:probability/mcmc-metropolis-hastings-gibbs