The draw that cannot be made

Suppose a distribution assigns probabilities to a landscape with many possible states. Finding the highest hill would answer the wrong question. The task is to estimate an average over the entire landscape: perhaps an expected energy, a posterior mean, or the probability of a region. If independent draws from the target were available, the route would be familiar. Draw a state, evaluate the quantity of interest, repeat, and average. Hastings addresses the harder case in which the target can be evaluated comparatively but cannot be sampled from directly.

The obstacle can be computational rather than conceptual. A density may be known only up to a multiplicative constant. In Bayesian work, a posterior is proportional to a likelihood multiplied by a prior, while the integral that turns the product into a density can be prohibitively difficult. In statistical mechanics, the analogous partition function sums contributions from a vast state space. The inability to compute that one global constant appears to prevent both normalisation and direct sampling.

Hastings changes the object being designed. Instead of manufacturing independent draws, construct a Markov chain whose next state depends on the current state and whose stationary distribution is the desired target. A long run can then estimate target expectations by time averages. This exchanges one difficult global draw for many local transitions. The exchange is powerful, but it creates new obligations: the chain must preserve the target, reach relevant regions, and reveal how serial dependence affects uncertainty.

The paper generalises the 1953 method of Metropolis and colleagues. Their physical application used a symmetric way of proposing local changes. Hastings allows a much broader proposal transition matrix. That generality makes the proposal itself part of the mathematics. If a mechanism proposes east more often than west, accepting only according to whether target density rises or falls will generally distort the long-run distribution. Directional bias must be corrected.

A proposal can lean before acceptance begins

Write the current state as i and a proposed state as j. Hastings starts from a proposal transition matrix Q. Its entry q_ij is the chance of proposing j while at i. The matrix may be chosen for convenience: a nearby state may be cheap to generate, a component may be updated conditionally, or a proposal may exploit a rough idea about the target’s shape. The proposal is not required to have the target as its stationary distribution.

That freedom is the source of both utility and danger. Imagine two states A and B with equal target probability. A mechanism suggests B from A with probability 0.9 but A from B with probability 0.1. If every proposal is accepted, the resulting chain spends far more traffic moving towards B than away from it. Equal target weights do not neutralise unequal proposal traffic. The acceptance stage must see both directions of Q.

For off-diagonal transitions, the completed chain has probability p_ij=q_ijα_ij, where α is the chance of accepting. The diagonal p_ii receives everything not used by accepted departures. This factorisation exposes two decisions: where to look and whether to go there. A symmetric proposal has q_ij=q_ji; only then can its two terms cancel from the correction and recover the Metropolis special case.

Balance the completed traffic

A distribution π is stationary for P when one transition leaves it unchanged. Detailed balance provides a local route: for every pair i and j require π_ip_ij=π_jp_ji. The left side is stationary mass at i times the move to j; the right is reverse traffic. If every pair balances, incoming and outgoing terms cancel when all origins are summed.

Substitute p_ij=q_ijα_ij. Acceptance probabilities must satisfy α_ij/α_ji=[π_jq_ji]/[π_iq_ij]. The numerator describes desired reverse traffic before acceptance and the denominator desired forward traffic. The equation constrains a pair of acceptances but does not uniquely choose them.

The familiar maximal choice is α(i,j)=min{1,r(i,j)}. If r is below one, the forward move is thinned and its reverse accepted. If r is above one, forward is accepted and reverse thinned by 1/r. Either way, their acceptance ratio is r. This is a convenient modern notation for one member of Hastings’s broader family.

Detailed balance is a local certificate, not a universal requirement. Non-reversible chains can preserve a target through circulating flows whose net inflow equals net outflow without matching each pair. Hastings uses reversibility because it gives an inspectable construction, not because every valid sampler must reverse each microscopic route.

Hastings gives a family, not one gate

Modern introductions often present only the min{1,r} acceptance rule and call it Metropolis–Hastings. Hastings’s paper is broader. In finite-state notation, he writes an acceptance family using a function s_ij symmetric in i and j. One form is α_ij=s_ij/[1+(π_iq_ij)/(π_jq_ji)], with s chosen so every acceptance lies between zero and one. Symmetry of s makes the detailed-balance algebra work.

Different admissible symmetric functions produce different amounts of movement while preserving the same target. One choice yields maximal Metropolis acceptance. Another gives the smoother logistic form r/(1+r), associated with Barker’s rule in the symmetric-proposal case. Both can be correct invariant-distribution constructions, yet they need not have equal statistical efficiency.

Peskun’s 1973 paper supplies the successor result. For a fixed proposal in the finite reversible setting, increasing off-diagonal transition probabilities at the expense of holding probability lowers asymptotic variance for target expectations. The maximal Metropolis member is optimal within the relevant Hastings class. That ordering must not be retroactively reported as a theorem in the 1970 paper.

“Valid” and “efficient” answer different questions. Detailed balance asks whether the target is preserved. Peskun compares the precision of two preserving chains under stated conditions. A chain can pass the first test and perform poorly on the second. A higher acceptance rate is also not universally better across unrelated proposals, because proposal distance and computational cost change with the design.

The normalising constant vanishes locally

Let the target be π(x)=w(x)/Z, where w is evaluable and Z is an unknown sum or integral. The target ratio in the Hastings correction is [w(j)/Z]/[w(i)/Z]=w(j)/w(i). The same constant appears in numerator and denominator and cancels. A global quantity that may be computationally inaccessible is irrelevant to each local acceptance decision.

This cancellation is one reason the algorithm became central to Bayesian computation. A posterior can be represented by prior times likelihood without evaluating the marginal likelihood that normalises it. The 1997 introduction by T. L. Lai and the 2020 fiftieth-anniversary retrospective by Dunson and Johndrow both emphasise this bridge from statistical mechanics to general statistical targets.

The cancellation has limits. It requires ratios to be well-defined on moves the proposal can make. It does not rescue an improper target whose integral is infinite, a likelihood that cannot be evaluated, or a proposal with no reverse support where positive target traffic is required. It also does not calculate Z as a by-product. The method estimates expectations under a normalised target without necessarily discovering the normaliser.

Numerical arithmetic adds a practical boundary. In high dimensions, products of many small likelihood terms may underflow. Implementations usually calculate log weights, subtract them, add the log proposal ratio, and exponentiate only after capping at zero for the min rule. This is a later computational convention that preserves the same algebra. It does not alter the target or permit undefined values to pass unnoticed.

Rejection is a transition to the same state

An implementation often narrates rejection as “nothing happened”. In the mathematics, something precise happened: the chain transitioned from i to i. The diagonal entry p_ii is one minus the total probability of accepted departures from i. It makes every row of P sum to one and retains the probability mass removed by acceptance gates.

Deleting rejected iterations would create a different chain. States with low outward acceptance would lose their required residence time. Consider a high-weight state surrounded by low-weight neighbours. Many outward proposals must be rejected so the path spends enough time at the centre. Keeping only accepted moves would make it appear too rare and bias time averages.

Repeated states are observations of the Markov chain, not missing values. They contribute again to estimated expectations. They also create serial dependence: a run of rejections can repeat the same function value many times. Nominal iteration count is therefore not equivalent to the number of independent observations.

The self-loop also helps break periodic motion. A nearest-neighbour proposal on a two-colour lattice can alternate colours at every accepted step. A positive chance of staying put breaks that exact rhythm. Rejection does not guarantee aperiodicity in every design, but its diagonal mass often supplies it. Convergence still requires that target states communicate through proposal paths and that recurrence conditions hold.

A stationary path still carries correlated error

If X_t were independent target draws, the variance of an average would be the target variance divided by the number of observations. A Markov chain usually makes adjacent function values correlated. The variance of its time average includes lagged covariance terms. Positive correlation inflates uncertainty because a run of similar states contributes less new information than the same number of independent draws.

Hastings did not treat error assessment as an afterthought. The publisher summary explicitly lists methods and difficulties of assessing error in Monte Carlo estimates, and the primary paper’s references include work on stationary-process means and spectral estimation. Generating a target-preserving chain and measuring the precision of its average belong in the same account.

A practical route divides a long run into batches, calculates one mean per batch, and uses variation among batch means to estimate uncertainty. Batches must be long enough that their means are less strongly dependent. Contemporary effective sample size compresses the warning into an approximate count: how many independent draws would give comparable variance? That phrase is later terminology and can conceal assumptions, so the correlation mechanism matters more than the single number.

Initialisation adds another finite-run issue. Stationarity is a property of a target and transition kernel. A chain started far from representative regions does not instantly have the stationary distribution. Discarding an initial segment can reduce start-up effects, but no universal deletion length proves convergence. Multiple starts, trace inspection, problem-specific bounds and sensitivity to proposal design address different parts of uncertainty.

Error is function-specific. A chain may estimate a broad mean adequately while failing to estimate a rare-event probability, because crossings into a tail are much slower than motion within the centre. One reported effective sample size cannot certify every query. The quantity of interest, proposal geometry and realised path jointly determine precision.

Acceptance rate is not the same as exploration

A proposal determines the scale and direction of attempted movement. Tiny local changes often land at similar target density and are accepted frequently, yet the chain may need many steps to cross the target. Enormous jumps may explore widely when accepted but land in low-density regions and be rejected repeatedly. Tuning seeks useful movement, not a universally maximal acceptance percentage.

Hastings’s generality opens several designs. A random-walk proposal is centred at the current state. An independence proposal ignores it and draws from an approximation to the target. Component-wise updates alter one coordinate at a time. The primary paper discusses random orthogonal matrices and possible statistical applications, and its first searchable example targets a Poisson distribution. Those examples establish range; the numerical laboratories here remain authored finite-state constructions.

Support is foundational. If q(j|i)>0 but q(i|j)=0 while both target states have positive probability, the reversible ratio forces acceptance of i→j to zero. If entire target regions cannot communicate through proposal paths, the chain is reducible and no run from one component can represent the whole target. Aperiodicity prevents a deterministic rhythm. Self-loops often help, but not every design gains enough holding automatically.

Multimodality exposes the difference between local correctness and global usefulness. A random walk can preserve a target with two distant modes while crossing between them so rarely that a finite run reports only one. The acceptance calculation can be correct at every attempt. The failure is exploration. Tempering, non-local proposals, multiple chains and reparameterisation are later responses, each with new assumptions.

Executable Hastings laboratory

The laboratory keeps five states so every probability can be inspected. The target is the distribution used above. The symmetric kernel proposes neighbours. The clockwise kernel strongly favours increasing labels and weakly favours the reverse. The independence kernel proposes from a fixed skewed distribution. Each uses the same target and its own reverse-to-forward proposal ratio.

Choose a kernel, set a deterministic seed, and step or run two hundred iterations. The chart shows empirical occupancy beside the target. The log reports the latest proposal, target ratio, proposal ratio, acceptance and decision. Reproducibility makes numerical checks repeatable without suggesting that one seed is representative.

The exact tests calculate the completed transition matrix rather than trusting simulation. They check target normalisation, maximum detailed-balance residual, cancellation after multiplying all target weights, and stationary drift after correction. The empirical distance is intentionally separate. Exact algebra can pass while a short random path remains visibly uneven.

This bench is a mechanism demonstration, not a convergence certificate. Two hundred transitions can reveal correction but cannot support a universal finite-run guarantee. Change only the seed and compare occupancy. Then switch to the clockwise kernel. Its raw proposal has a direction, yet corrected detailed-balance residual remains near floating-point precision.

Successors, extensions and rivals

The 1953 Metropolis paper is the prerequisite. It establishes local acceptance for a symmetric proposal in statistical mechanics. Hastings retains its logic while allowing arbitrary compatible proposal matrices and general target distributions. In the symmetric case, reverse and forward proposal terms cancel, so the older rule appears as a special case.

Peskun’s 1973 comparison asks which reversible kernel is more precise for the same target. Its ordering result favours greater off-diagonal movement and identifies maximal acceptance as optimal within the relevant Hastings family. This is a theorem about asymptotic variance, not a premise required to prove invariance.

Gibbs sampling is a close successor route. If a proposal draws a component from its exact full conditional distribution, the Hastings ratio can reduce to one and every proposed component update is accepted. Geman and Geman’s 1984 image-restoration work made this form widely visible. Later accounts placed Gibbs and general Hastings updates in one Markov-chain Monte Carlo family.

Tierney’s 1994 treatment develops general-state-space conditions for posterior exploration, clarifying irreducibility, recurrence, laws of large numbers and central-limit questions beyond finite matrices. Optimal-scaling research asks how proposal variance should change with dimension. Adaptive methods let proposals learn under conditions intended to retain convergence. Hamiltonian Monte Carlo uses gradients and auxiliary momentum to travel through high-dimensional targets. Each attacks geometry or mixing; none removes the need to show target preservation.

Non-reversible samplers refuse detailed balance while preserving global stationarity. Circulating probability currents can reduce diffusive backtracking. They are rivals to reversibility as a design principle, not refutations of Hastings’s algebra. They need their own invariance arguments and can be harder to implement or diagnose.

Dunson and Johndrow’s fiftieth-anniversary retrospective emphasises how many current algorithms still contain the Hastings mechanism. Longevity comes from modularity: change target, representation or proposal while retaining a local correction. That modularity also creates source errors when later names and diagnostics are projected backwards. This article uses “Hastings algorithm” for the primary construction and labels later efficiency and convergence claims.

From a finite matrix to a usable scientific calculation

The finite-state notation makes the proof visible, but the same logic extends to continuous variables by replacing target probabilities with densities and proposal entries with conditional proposal densities. If the current point is x and the candidate is y, the ratio uses the target density at y times the proposal density of returning to x from y, divided by the target at x times the density of proposing y from x. Individual points have probability zero in a continuous distribution, so it is densities and transition kernels, rather than point masses, that enter the calculation. The local traffic argument survives this change of language.

That translation needs care at boundaries. Suppose a random walk adds a symmetric Gaussian increment on the real line, but the target is restricted to positive values. Simply reflecting, truncating or resampling negative proposals changes the effective proposal density near zero. A reflection can remain symmetric under a suitable construction; a truncated proposal usually acquires a state-dependent normalising factor. The correction must use the proposal actually implemented, not the simpler distribution imagined before boundary handling. Many silent sampler errors begin when code and algebra describe different Q.

Transformations create the same obligation. A positive scale parameter may be sampled on its logarithm because additive proposals move more naturally there. The target density in log space includes the change-of-variables Jacobian. Ignoring it changes relative weights, even if the Hastings acceptance code is otherwise flawless. Conversely, calculating the transformed target correctly can greatly improve movement by replacing a cramped positive half-line with an unconstrained line. The algorithm does not choose a representation on the scientist’s behalf. It supplies a correction after target and proposal have been specified coherently.

Hastings’s Poisson example illustrates that proposal design can exploit target form in a discrete problem. His discussion of random orthogonal matrices shows that the state need not be a scalar or ordinary vector. An orthogonal matrix lives on a constrained geometric space; moves must respect that constraint and the intended measure. The paper’s breadth is important because it reveals the construction as a pattern for simulation, not one recipe for a bell-shaped density. This companion does not reconstruct those examples beyond the accessible source record, but their presence guards against reducing the paper to a modern one-dimensional classroom walk.

Consider an independence proposal g(y) that does not depend on x. Its correction becomes π(y)g(x)/[π(x)g(y)]. If g is a close approximation to π, candidates arrive in useful regions and weights vary modestly. If g has lighter tails than π, the chain can become sticky in target tails because proposals back towards the centre carry an unfavourable correction. Direct proposal quality therefore affects more than raw candidate plausibility. It controls the ratios needed to undo the proposal’s own sampling pattern.

A component-wise scheme adds another layer. In a ten-dimensional target, update coordinate one using its proposal, then coordinate two, and so forth. Each substep can preserve the target, making their composition invariant even when the full sweep is not reversible as a single block. Randomly choosing the updated component produces a different kernel from cycling deterministically. Both can be useful, but an error analysis should say which chain generated the output. Calling every arrangement “the Hastings algorithm” without specifying its composition hides the mechanism that determines correlation.

The calculation also has a computational denominator. One transition may require evaluating an expensive likelihood over millions of observations. A proposal that makes statistically efficient movement but demands a full likelihood twice per step can be worse per second than a somewhat stickier proposal with reusable calculations. Conversely, thinning a chain by discarding most recorded states does not usually save the evaluations already spent generating them. Precision should be reported against computational cost and retained path structure, not improved cosmetically by reducing the file size.

Diagnostics cannot repair a wrong acceptance ratio. A smooth trace, plausible histogram or agreement between two identically flawed implementations is compatible with sampling the wrong stationary distribution. Exact tests on small cases are therefore valuable. Construct a target whose normalised probabilities can be enumerated, form P from the implemented Q and acceptance rule, and verify both row sums and πP=π. Then test asymmetric proposals specifically. A symmetric-only test never exercises the term that distinguishes Hastings’s generalisation from the earlier Metropolis case.

Once invariance passes, exploration tests ask different questions. Start chains in separated regions, examine transitions between modes, compare function-specific autocorrelations, and vary proposal scale. None is an infallible proof of convergence. Together they can reveal failures that the invariant equation cannot: regions disconnected by code, numerical underflow that rejects legitimate moves, or a path whose crossing time dwarfs the available run.

The professional standard is therefore layered. First document the target, including support and any transformation Jacobian. Second document the proposal in both directions, including boundary behaviour. Third state the acceptance rule and treatment of rejection. Fourth verify invariance on auditable instances. Fifth assess mixing and Monte Carlo error for the actual estimands. Hastings provides the hinge between the second and third layers. Its clarity becomes most useful when the surrounding layers remain visible.

Memory studio

Next three papers to read

1. Canon 0017, Rubin (1974). Move from probability-preserving computation to treatment outcomes under intervention.
2. Peskun (1973). Compare Hastings members by asymptotic variance.
3. Tierney (1994). Extend finite-state reasoning to general posterior spaces.

The achievement is correction, not automatic exploration

Hastings’s enduring move is to expose and repair the proposal mechanism. The target says where long-run probability should reside. The proposal says where computation looks. Acceptance reconciles them by comparing target weights and both proposal directions. Rejection retains the remainder as residence time. An arbitrary compatible proposal becomes useful without being mistaken for an unbiased draw.

The result is exact at the level of invariant-distribution algebra. A common normaliser cancels. Pairwise balance can be checked locally. The symmetric Metropolis rule appears as a special case. Those achievements do not settle finite computation. A reducible chain misses regions. A periodic chain oscillates. A sticky or badly scaled proposal produces severe correlation. A multimodal target can look stable within one mode while another remains unseen.

The disciplined reading asks three successive questions. Does the completed kernel preserve the target? Can the path explore relevant support from chosen starts? Does the realised run estimate the required function with acceptable uncertainty? Hastings gives the central construction and treats the third as a genuine difficulty. Later literature sharpens all three without erasing their separation.

For intelligence and consciousness research, the lesson is methodological rather than metaphysical. A process can have correct long-run statistics even if each local proposal is biased, provided a compensating mechanism is verified. Conversely, a plausible trajectory or high acceptance rate is not evidence that an intended distribution has been explored. The paper offers no criterion for agency, intelligence or experience. It models how to distinguish a desired invariant, a search mechanism, a correction rule and an error account.