Does the algorithm need the target's normalizing constant?

No, provided the unknown constant is the same across candidate states and cancels in the ratio.

Are the retained draws independent?

Generally not. They are states of a Markov chain, so dependence must be considered when assessing estimation error.

Can it be used with discrete states?

Yes. The target and proposal use probability masses rather than continuous densities, as in the worked example.

AI Glossary / Graphs and symbolic AI / Intermediate

Metropolis-Hastings

Definition

Metropolis - Hastings is a Markov chain Monte Carlo algorithm that generates a sequence of samples using proposals followed by acceptance or rejection. Its acceptance rule corrects for both the target distribution and the proposal mechanism. Under suitable conditions, the chain explores the target distribution, allowing expectations and probabilities to be estimated from its dependent draws.

What it means

Sampling directly from a complicated distribution may be difficult even when its relative density can be evaluated. Metropolis - Hastings uses an easier proposal distribution to suggest a next state, then adjusts how often those suggestions are accepted.

The algorithm is not an optimizer that continually moves toward a single best point. It sometimes accepts lower-density states because its purpose is to represent a distribution. Rejections are also meaningful: when a proposal is rejected, the current state remains the next sample. Removing those repeated states without appropriate correction changes the sampling process.

How it works

At current state x, draw candidate y from proposal q(y|x). For a target density or mass π, use acceptance probability α(x,y)=min[1, π(y)q(x|y)/(π(x)q(y|x))], with the required support conditions. Draw a uniform random number and move to y if it passes this test; otherwise remain at x.

If π is known only up to a constant, that constant cancels in the ratio. With a symmetric proposal, q(y|x)=q(x|y), the proposal factors cancel too, giving the simpler Metropolis rule.

The correction establishes the relevant balance relationship, but useful finite-run sampling also requires adequate exploration. Proposal choices that move too little or reject too often can yield highly dependent samples. Diagnose convergence and Monte Carlo error rather than relying only on the number of iterations.

Three practical examples

Bayesian estimation: sample parameter values when the posterior normalizing integral is difficult but unnormalized posterior scores can be evaluated.
Probabilistic modeling: explore configurations of a model when direct independent draws are unavailable.
Teaching sampling methods: compare how symmetric and asymmetric proposals require different acceptance calculations for the same target distribution.

Think of it this way

Think of a guide who suggests destinations more often in some directions than others. An acceptance gate compensates for that suggestion bias so the completed route spends appropriate proportions of time in the target regions.

The analogy is limited: ordinary intuition about “good destinations” is not enough. The gate must use the correct probabilities, and the proposed routes must allow exploration of the relevant space. Otherwise an apparently active traveler can still sample the wrong distribution.

Worked example

Use two states A and B with target probabilities π(A)=0.6 and π(B)=0.4. From A, the proposal chooses B with probability 0.8 and A with probability 0.2. From B, it chooses A with probability 0.2 and B with probability 0.8. These proposals are asymmetric.

For A→B, the acceptance probability is min[1,(0.4×0.2)/(0.6×0.8)]=1/6. The actual probability of moving A→B in one step is therefore 0.8×1/6=2/15. For B→A, the ratio is the reciprocal, 6, so acceptance is 1 and actual transition probability is 0.2.

Check the target-weighted flows: 0.6×(2/15)=0.08 and 0.4×0.2=0.08. They balance. If an A→B proposal receives a hypothetical uniform draw of 0.10, it is accepted; a draw of 0.50 rejects it and records A again. Using only the target ratio 0.4/0.6 would give the wrong acceptance probability here because it ignores proposal asymmetry. This is direct probability arithmetic, not an executed chain.

Illustrative case study

Fictional case: an analyst builds a sampler for a demand model whose parameters must be positive. To avoid negative proposals, the analyst changes the proposal rule near zero but leaves the old symmetric acceptance formula unchanged.

A review catches that the altered proposal probabilities are no longer symmetric. The team either derives the correct Hastings correction or adopts a properly specified transformed-parameter sampler. It tests a small case with a known target before relying on the larger model. The fictional case illustrates that a convenient proposal adjustment can change the required mathematics; it reports no real sampling results.

Common misconceptions and mistakes

Do not keep proposing until something is accepted and then record only the accepted states as though they were the original chain. Rejected steps contribute to the target occupancy frequencies.

Do not drop the proposal ratio merely because the proposal looks visually similar in both directions. Truncation, constraints, and state-dependent scales can break symmetry. A high acceptance rate is also not automatically good: tiny moves may be accepted frequently while exploring very slowly. Adaptive changes to a sampler require their own conditions rather than unrestricted tuning during retained sampling.

Business use

Metropolis - Hastings can make uncertainty calculations possible for models that resist direct sampling. Its flexibility comes with a responsibility to specify the target and proposal precisely and to verify implementation on simpler distributions where results can be checked.

Business conclusions should reflect both model uncertainty and simulation reliability. Report relevant diagnostics, effective sample sizes, and precision of important estimated quantities. If alternative chains remain in different regions, or decision-critical tail estimates are unstable, additional raw iterations alone should not be presented as proof that the issue is resolved.

Check your understanding

a proposed move is rejected. What should the next recorded state be in the ordinary algorithm?

Answer: the current state again. Rejection means the chain stays in place for that step; discarding the repetition changes the empirical weighting of states.

Related terms

Learn next

recalculate the two-state example with a symmetric proposal and verify that the proposal ratio cancels. Then compare chains with small and large proposal moves on a known target. Study convergence diagnostics before interpreting samples from a model whose correct posterior is unknown.

Sources

Marco Taboga, author-maintained “Metropolis–Hastings algorithm” lecture: https://www.statlect.com/fundamentals-of-statistics/Metropolis-Hastings-algorithm. Stan Reference Manual, dependent-draw analysis: https://mc-stan.org/docs/reference-manual/analysis.html. Relevant primary teaching and implementation documentation was read. The asymmetric proposal, balance calculation, and fictional case are original; no simulation output is claimed.

Previous: Metropolis-adjusted Langevin algorithm Next: Metropolis within Gibbs