Why can it accept a lower-density state?

Sampling must explore the distribution, including less dense regions; the acceptance probability controls their visitation frequency.

Are the resulting draws independent?

Generally not. Successive states are related through the proposal and acceptance process, so precision calculations must account for dependence.

Must the normalizing constant be known?

No, a common multiplicative constant cancels in the target-density ratio.

AI Glossary / Probabilistic machine learning / Intermediate

Random-walk Metropolis

Definition

Random-walk Metropolis is a Markov chain Monte Carlo algorithm that proposes a new state by adding a random increment to the current state. With symmetric increments, it accepts the proposal using a ratio of target densities. Rejected proposals leave the chain at its current state, which is recorded again.

What it means

The algorithm creates a sequence whose long-run behavior can represent a target probability distribution under suitable conditions. It is useful when the target density can be evaluated up to an unknown normalizing constant but direct independent sampling is difficult.
The random walk supplies candidate moves; the acceptance rule changes their behavior so that the intended distribution is invariant. This is a sampling method, not simply an optimizer that always climbs toward a high-density point. Occasional moves to lower-density regions are essential to representing uncertainty rather than returning only a mode.

How it works

From current state x, draw an increment epsilon from a distribution symmetric about zero and propose y = x + epsilon. For example, use a normal increment with a fixed covariance matrix. Accept with probability alpha = min[1, pi(y)/pi(x)]; otherwise set the next state equal to x.
An unknown constant multiplying pi cancels in the ratio. In practice, log densities often make the calculation more stable: compare log(U) with min[0, log pi(y) - log pi(x)] for U uniform on (0, 1).
The simple ratio requires proposal symmetry. State-dependent scales, truncation, or other changes can make forward and reverse proposal probabilities differ, requiring the full Metropolis-Hastings correction. The resulting chain still needs adequate exploration and diagnostics. Invariance alone does not establish that a finite run has explored every important region.

Three practical examples

Bayesian parameter analysis: sample from a low-dimensional posterior whose unnormalized density is available but whose normalizing integral is inconvenient.
Teaching and implementation checks: compare sampled summaries with a distribution whose mean and variance are known analytically.
Research baselines: assess a more sophisticated sampler against a clearly specified random-walk method, including computational cost and effective sample sizes.

Think of it this way

Think of a walker proposing nearby steps on a landscape, sometimes declining a step and staying put. The acceptance rule controls how much time is spent in different regions. The analogy has limits: height represents density, not a destination to maximize, and repeated stays are part of the sampling record rather than missing observations.

Worked example

Consider an original normal-target illustration with unnormalized density pi(x) = exp(-x^2/2). Start at x = 0 and use symmetric proposals. Suppose the first proposed increment is 1, giving y = 1. The acceptance probability is exp(-1/2), approximately 0.6065. With a uniform draw U = 0.4, accept, so the next state is 1.
Now suppose the increment is 1 again, proposing y = 2 from x = 1. The ratio is exp[-(4 - 1)/2] = exp(-1.5), approximately 0.2231. With U = 0.3, reject. The next recorded state is still 1.
Next propose an increment of -0.5, giving y = 0.5. The density ratio is exp[-(0.25 - 1)/2] = exp(0.375), greater than one, so the proposal is accepted with probability one.
The resulting recorded sequence is 0, 1, 1, 0.5. The repeated 1 must not be deleted merely because the proposal was rejected. These four steps demonstrate the update rule; they are far too few to estimate the target distribution reliably.

Illustrative case study

Fictional case: Brookstone Research builds a small Bayesian demonstration model and uses random-walk Metropolis as a transparent baseline. The first implementation stores only accepted states, producing a distorted sampling record.
The team corrects it to retain every post-decision state, checks the normal-target example above, and examines several chains with different starting values. It then evaluates mixing and Monte Carlo precision for the actual quantities of interest. This invented case illustrates a common implementation issue, not a claim that this sampler is suitable for every production posterior.

Common misconceptions and mistakes

A high acceptance rate does not necessarily indicate efficient sampling. Extremely small moves may be accepted almost always while exploring very slowly. Very large moves can create frequent rejections and long repeated stretches. The useful balance depends on the target and proposal.
There is no universal acceptance-rate target that certifies convergence. Also, clipping an out-of-bounds proposal is not automatically equivalent to rejecting it: changing the proposal mechanism can change the required acceptance correction. Support constraints need a mathematically consistent treatment.

Business use

For business analyses, the method offers simplicity and a clear audit trail, but efficiency can deteriorate with strong parameter correlations, difficult geometry, or separated modes. Evaluate how much reliable information it produces per unit of computation rather than relying on raw iteration counts.
Document the proposal covariance, initialization, adaptation policy if any, retained-draw procedure, and diagnostic results. Use methods and transformations appropriate to the model's structure. Consistent sampling and good model fit remain separate requirements for useful conclusions.

Check your understanding

A proposal is rejected at current state x = 3. What should be stored as the next state?

Answer: Store 3 again. Omitting rejected steps changes the sampling record and generally changes the distribution represented by an unweighted average.

Related terms

Metropolis-Hastings
Acceptance probability
Autocorrelation
Effective sample size
Detailed balance
MCMC
symmetric proposal
target density
invariant distribution

Learn next

Implement the one-dimensional normal example and retain rejected states. Compare small and large proposal scales using trace plots and effective sample sizes. Then derive the full Metropolis-Hastings ratio before modifying the proposal to depend asymmetrically on the current state.

Metropolis-Hastings

Sources

Deligiannidis, Oxford Advanced Simulation, Lecture 6, random-walk Metropolis and proposal choice: https://www.stats.ox.ac.uk/~deligian/pdf/sc5/slides_2020/L6.pdf Stephens, The Metropolis Hastings Algorithm, instructor-authored explanation and implementation: https://stephens999.github.io/fiveMinuteStats/MH_intro.html The Oxford random-walk Metropolis lecture was independently consulted for symmetric proposals and scale-dependent exploration.

Previous: Random walk Next: Randomization, scientific