ExtendedSource checked

Metropolis-Hastings

Samples from a target distribution by accepting or rejecting proposed moves.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Randomness & Sampling
Difficulty: Advanced
Family: Markov Chain Monte Carlo
Tier: Extended
Status: Verified
Review: Source Checked
Sources: 1
Formulas: 1
Relationships: 6
Code example: Not ready
Visualization: Ready
Aliases: MH

Overview

Metropolis-Hastings builds a Markov chain whose long-run states follow the desired target distribution.

Core Concepts

sample selectionMarkov chain staterandom samplingstate estimatemarkov chain monte carlorandom sourcedistribution shape

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(t)

Average

O(t)

Worst

O(t)

Space

O(1)

When to Use

Use Metropolis-Hastings when you need to proposes a nearby random state.
Use it for bayesian inference with inputs like target density up to scale.
Use it when randomization, representative samples, or controlled variation are needed.
Use it when the Markov Chain Monte Carlo tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when repeatability is required but seeds and random sources are not controlled.
Avoid it when reproducibility, distribution quality, or sample independence cannot be verified.
Avoid it when the required output is not correlated target samples.

What It Does

Proposes a nearby random state
Accepts moves based on target probability ratio

Use Cases

Bayesian inference
Sampling complex distributions
Monte Carlo estimation

Inputs

Target density up to scale
Proposal distribution
Initial state

Outputs

Correlated target samples

Key Formulas (1)

Acceptance probability

p = min(1, target(x_new) · proposal(x_old | x_new) / (target(x_old) · proposal(x_new | x_old)))

p = min(1, target(x_new) * proposal(x_old | x_new) / (target(x_old) * proposal(x_new | x_old)))

Decides whether to move to a proposed Markov-chain state.

Pseudocode

1.Start from an initial state
2.Propose a new state
3.Compute the acceptance probability
4.Accept or keep the old state
5.Repeat to collect samples

Canonical Example

Input: items = [A, B, C, D], seed = 7
Output: sampled or randomized result
Explanation: Metropolis-Hastings: The algorithm uses controlled randomness to choose or generate values.

Implementation Notes

Keep the input contract explicit: Target density up to scale; Proposal distribution; Initial state.
Use this step as the implementation spine: Start from an initial state.
Then preserve the next state change: Propose a new state.
Thread a seedable random source through the implementation for repeatable tests.
Separate the random number source from the algorithm so tests can use fixed seeds.

Common Pitfalls

Samples are correlated, so diagnostics and burn-in choices matter.
Sampling from the wrong distribution can make the estimate look precise but biased.
Using biased random choices or forgetting to store the seed for reproducible runs.
Returning correlated target samples without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Iterative Convergence & State Trajectory

Show a random walk accepting moves more often in high-probability regions.

Step 1 of 5: Start from an initial state

mcmc-walk

Notes

Metropolis-Hastings operates in O(t) time and O(1) space within the Markov Chain Monte Carlo family. Key governing relation: p = min(1, target(x_new) * proposal(x_old | x_new) / (target(x_old) * proposal(x_new | x_old))). Often compared with Rejection Sampling and Importance Sampling.