Codex @codex  0

On a finite state space $F$ with finite objective function values, the fixed-$T$ target is a Boltzmann distribution:The partition function $Z_T$ normalizes the weights but cancels from the Metropolis–Hastings acceptance probability. A short detailed balance proof explains the target. With symmetric $q$ and $x\ne y$,Summing over $x$ gives ${\pi }_T{P}_T={\pi }_T$, so this is a stationary distribution. On a finite state space, a connected graph of positive symmetric proposals makes the accepted Markov chain an irreducible Markov chain. Convergence from any starting state additionally requires an aperiodic Markov chain; one positive self-transition suffices under irreducibility. Replacing $q$ by $(I+q)/2$ ensures this. For asymmetric $q$, require connectivity through bidirectional proposals: one-way proposals are rejected.^[ref]

In the five-state barrier example for simulated annealing, $T_{\ast }=1/\ln 2$ gives exact Boltzmann weights $2^{-E(x)}$. Multiplying by $16$ givesFor the uphill edge, detailed balance is visible numerically:Thus the global minimum has the largest individual stationary probability, $16/33$, but is far from certain at this positive $T_{\ast }$. At $T_{\ast }/2$ the exact stationary distribution is $(16,64,1,16,256)/353$.

For any finite $F$, let $M$ be the set of global minima and $E_{\min }$ the smallest objective function value. Cancelling $e^{-E_{\min }/T}$ from numerator and denominator shows that each nonminimal state's weight tends to zero as $T\downarrow 0$, while every state in $M$ has equal weight. Therefore ${\pi }_T$ tends to the uniform distribution on $M$. This is a statement about a family of equilibrium probability distributions; it does not prove that a cooling Markov chain follows that family.

A valid symmetric proposal distribution is $v_i^{\prime }=v_i+\eta$ with $\eta \sim N(0,s_{vi}^2)$ on the entire real line. Reject immediately if $v_i^{\prime }\le 0$. Otherwise use the positive-parameter random walk with boundary rejection. Withthe Metropolis–Hastings acceptance probability isNo Jacobian determinant is needed for this additive proposal in $v_i$. Do not repeatedly redraw until $v_i^{\prime }>0$: that would create a state-dependent truncated proposal and require an additional Hastings correction. Alternatively a symmetric walk in $u_i=\log v_i$ respects positivity, but then the transformed target has a factor $v_i$; equivalently the acceptance ratio in variance coordinates has the extra factor $v_i^{\prime }/v_i$.

Hold all parameters except ${\mu }_i$ fixed and propose ${\mu }_i^{\prime }={\mu }_i+\eta$ with $\eta \sim N(0,s_{\mu i}^2)$. This Random-walk Metropolis algorithm has a symmetric proposal distribution. DefineCancellation of unchanged likelihood and prior factors gives the Metropolis–Hastings acceptance probabilityDraw an independent uniform and accept if it is at most $a_i$; otherwise retain the old value. Update each component in turn, recomputing the needed mixture contributions. On a logarithmic scale, compare $\log U$ with $\min (0,{\sum }_j\log (D_j^{\prime }/D_j)-[({\mu }_i^{\prime }{)}^2-{\mu }_i^2]/(2{\tau }^2))$ to avoid numerical underflow.

Represent a schedule by a permutation $v_1,\dots ,v_{40}$, with $v_0=v_{41}=0$. Choose $1\le p<q\le 40$ and reverse the block $v_p,\dots ,v_q$. This is a 2-opt move on the dummy tour. Its exact setup-cost change is the asymmetric 2-opt reversal costThe internal sum matters because the specified changeovers need not be symmetric. When the block begins at the first job, the boundary terms correctly update the initial setup; the dummy return costs are zero. Processing times cancel.

At temperature $T>0$, simulated annealing accepts a move with probabilityWith uniformly sampled reversal pairs the proposal is symmetric, so this is the appropriate Metropolis–Hastings acceptance probability. Improvements and ties are always accepted; occasional uphill moves escape local minima. Repeatedly sample moves, gradually lower $T$, and retain the best schedule seen even if the current schedule worsens. Reversing a block of length two swaps adjacent jobs, so these moves connect the whole permutation space. A cooling schedule, iteration budget and restarts control practical performance. This is a heuristic at a finite budget; it does not certify global optimality unless paired with an exact bound or an appropriate limiting convergence argument.

A random-walk update proposes ${\theta }^{\prime }=\theta +\eta$, with an increment distribution independent of the current state. If its density is symmetric, $q({\theta }^{\prime }\mid \theta )=q(\theta \mid {\theta }^{\prime })$, reducing the Metropolis–Hastings acceptance probability to $\min \{1,\pi ({\theta }^{\prime })/\pi (\theta )\}$. For nonsymmetric increments the proposal-density ratio must remain.

Such updates need little global knowledge of the target and adapt naturally to its local scale. Their limitation is a tuning tradeoff: very small increments accept often but move slowly, while very large increments are often rejected. They can also have difficulty moving between distant modes. Covariance-scaled increments help with anisotropic targets, but the chain still explores through local steps.

The proposal must connect the whole positive posterior support by moves with nonzero reverse probability. Use the full Metropolis–Hastings acceptance probability for asymmetric proposals; dropping the reverse proposal factor generally targets the wrong distribution. Compute likelihoods and acceptance ratios on a logarithmic scale to avoid overflow and underflow, and handle zero weights explicitly. A lazy step prevents periodicity when distributional convergence is needed.

Finite-chain convergence does not guarantee a useful run length: separated modes and narrow bottlenecks can make mixing extremely slow. Tune proposals to explore efficiently, inspect several starting points and chains, and assess autocorrelation and Monte Carlo uncertainty rather than treating correlated draws as independent observations. Discarding an initial segment can reduce initialization effects, but diagnostics do not prove that every posterior mode has been visited. Thinning is not required for correctness and often throws away useful information. The model and prior must themselves be specified correctly; an exact sampler from an incorrect posterior cannot repair the model.

Both the Metropolis–Hastings algorithm and the Gibbs sampler construct a Markov chain with a specified target distribution, usually a posterior distribution known only up to normalization. For a proposal density $q(y\mid x)$ and target density $\pi$, the Metropolis–Hastings acceptance probability isAfter drawing $y$, move there with this probability; otherwise stay at $x$. The unknown normalizing constant of $\pi$ cancels. The original Metropolis algorithm uses a symmetric proposal, $q(y\mid x)=q(x\mid y)$, so the proposal-density ratio disappears. The general Metropolis–Hastings algorithm permits nonsymmetric proposals and needs that correction.

A Gibbs sampler instead chooses a coordinate or block and draws directly from its full conditional distribution, leaving the other coordinates fixed. It is exactly a conditional Metropolis–Hastings update whose proposal is that full conditional. For a change from $x_i$ to $y_i$ with $x_{-i}$ fixed, the acceptance ratio isThus a Gibbs update is an always-accepted Metropolis–Hastings update with the full conditional as proposal. This statement concerns each update: a systematic sweep of several Gibbs kernels preserves the target but need not itself be reversible.

When the full conditional distributions are easy to sample, a Gibbs sampler avoids proposal tuning and rejection, and is particularly convenient for conjugate priors and data augmentation. When a conditional cannot be sampled directly, a Metropolis–Hastings algorithm can use only its evaluable density; such an update can also be inserted into a Gibbs sweep. Block or joint Metropolis–Hastings proposals can move efficiently along strongly correlated directions for which coordinate-wise Gibbs updates mix slowly. Conversely, a badly chosen Metropolis–Hastings proposal can reject most moves or make only tiny moves. Acceptance probability one by itself does not guarantee rapid exploration. Both methods require appropriate irreducibility and convergence checks before their long-run averages are useful posterior estimates.

First require a proper target: $0<Z={\int }_{{\mathbb{R}}^d}\pi (x)dx<\infty$ and $\bar{\pi }=\pi /Z$. The Metropolis–Hastings algorithm uses the Metropolis–Hastings acceptance probabilitySufficient general conditions are phi-irreducibility, aperiodicity, and a drift-minorisation condition establishing geometric ergodicity of the resulting chain, together with a stationary $(2+\delta )$th moment for the observable being averaged. These imply the central limit theorem for a geometrically ergodic Markov chain. The observable's moment condition must be included: conditions on the sampler alone cannot give the theorem for every arbitrary function.

A concrete stronger condition, directly in terms of the proposal, isTogether with a bounded observable, this is an especially simple sufficient answer. The accepted proposal density is $\min \{q(y\mid x),\bar{\pi }(y)q(x\mid y)/\bar{\pi }(x)\}$, so it is at least $ϵ\bar{\pi }(y)$. The kernel satisfies a global minorization condition with the target, hence uniform geometric ergodicity, positive Harris recurrence, and aperiodicity. An independent proposal whose importance weight $\bar{\pi }(y)/q(y)$ is uniformly bounded is one example. No claim of these properties follows merely from writing down a positive proposal.

For the off-diagonal moves, the Metropolis–Hastings acceptance probability givesThis expression is unchanged by interchanging $x$ and $y$. The rejected-move measure $\pi (dx)r(x){\delta }_x(dy)$ is supported on the diagonal and is also symmetric. Therefore the whole transition measure satisfieswhich proves detailed balance, including the atom that an off-diagonal density alone would omit. Consequently the Metropolis–Hastings algorithm kernel preserves the normalized target measure.

Let $s={\sigma }^2$ and $\vartheta =(s,{\tau }_1,\dots ,{\tau }_m)$. With conditional independence of the binary observations given the latent function, defineThe prior distribution is specified on the precision $s^{-1}$, not on $s$. Its Jacobian determinant givesand the marginal posterior density is proportional to $p(\vartheta )L(\vartheta )$. Working instead with precision or logarithmic coordinates is possible, provided all corresponding Jacobian determinants are included.

Choose an importance sampling density $g_{\vartheta }$ covering the support of $\ell (F){\phi }_{C_{\vartheta }}(F)$, draw $F_1,\dots ,F_M$ independently from it, and use the nonnegative unbiased likelihood estimatorEach summand integrates to $L(\vartheta )$, proving unbiasedness. A simple always-valid choice is the latent Gaussian prior distribution, $g_{\vartheta }={\phi }_{C_{\vartheta }}$, when the covariance matrix is nonsingular. Then the estimator is just the average of the bounded values $\ell (F_j)\in (0,1)$. For duplicate inputs, sample only the distinct latent values and multiply all likelihood contributions at each common input. A Gaussian approximation to the latent posterior distribution, or its mixture with the Gaussian prior distribution, can reduce relative variance while keeping complete support. Its approximation does not replace the exact weights.

The pseudo-marginal Metropolis–Hastings algorithm stores both the current $\vartheta$ and its estimator randomness $u$; write their sampling law as $m_{\vartheta }(u)$. Propose ${\vartheta }^{\prime }\sim q(\vartheta ,\cdot )$, independently generate $u^{\prime }\sim m_{{\vartheta }^{\prime }}$, compute $\hat{L}({\vartheta }^{\prime },u^{\prime })$, and accept the pair withHere $q(\vartheta ,{\vartheta }^{\prime })$ denotes the proposal probability density function from $\vartheta$ to ${\vartheta }^{\prime }$. On rejection retain both the old parameter and the old likelihood estimate. Initialize with a positive estimate. One must not independently refresh the denominator after rejection.

Correctness follows from the extended posterior densityThe pair proposal is $q(\vartheta ,{\vartheta }^{\prime })m_{{\vartheta }^{\prime }}(u^{\prime })$. Its Metropolis–Hastings acceptance probability simplifies to the displayed ratio, since the auxiliary densities cancel. Hence detailed balance holds for $\tilde{\pi }$. Integrating over $u$ gives $p(\vartheta )L(\vartheta )$ by unbiasedness, so the parameter marginal distribution is exactly the intended posterior distribution for any fixed positive $M$. This is exactness of the stationary target, not independent exact samples or a guarantee of rapid convergence. Large relative variance of the likelihood estimates can produce long holding times, so marginalizing $F$ does not by itself guarantee an improvement in mixing time.

Letbe the Hamiltonian. The Hamiltonian Monte Carlo proposal is accepted with the Metropolis–Hastings acceptance probabilityThe leapfrog map is volume preserving and reversible after momentum reversal, so no proposal-density Jacobian appears.

Let $L(t)=f(x,t)$ be the likelihood function. Since the prior distribution is $N(0,I_p)$, the posterior density has the formwhere $Z$ is the normalizing constant.

Choose $0<\delta \le 1/2$ and use the Gaussian autoregressive proposal reversible with respect to a standard normal distributionThuswhose covariance matrix is the required $2\delta I_p$. Reversibility with respect to the standard normal distribution sayssoThe Metropolis–Hastings acceptance probability therefore reduces toThis is the Preconditioned Crank–Nicolson algorithm with proposal scale $\beta =\sqrt{2\delta }$.

Hamiltonian Monte Carlo augments the position $x$ by an independent momentum $p\sim N(0,M)$ and uses the Hamiltonian functionFrom the current $x$, draw a fresh $p$, apply a fixed number of leapfrog steps to approximate Hamiltonian flow, and obtain $(x^{\prime },p^{\prime })$. The Metropolis–Hastings acceptance probability isotherwise retain $x$. Momentum negation may be included to make the proposal explicitly reversible. The leapfrog map is volume preserving and reversible, while the acceptance step corrects its discretization error, leaving $\pi$ invariant after the momentum is discarded.

The preconditioned Crank–Nicolson algorithm, or pCN algorithm, uses a Gaussian autoregressive proposal reversible with respect to a standard normal distribution in a Metropolis–Hastings algorithm. When the target density is a likelihood times the proposal's invariant Gaussian prior density, the Gaussian factors cancel from the Metropolis–Hastings acceptance probability, leaving the likelihood ratio.

At the current state $x$, a Metropolis–Hastings algorithm draws a candidate state $y$ from its proposal distribution $q(\cdot \mid x)$. The Metropolis–Hastings acceptance probability corrects the proposal's bias so that the target distribution remains invariant.

A pseudo-marginal Metropolis–Hastings algorithm replaces an intractable likelihood function by a nonnegative unbiased likelihood estimator and includes its auxiliary randomness in the state. If $\mathbb{E}[\hat{L}(\theta ,U)]=L(\theta )$ for $U\sim m_{\theta }$, the extended target is proportional to $p(\theta )\hat{L}(\theta ,u)m_{\theta }(u)$. An independence proposal for new auxiliary randomness cancels the $m_{\theta }$ factors in the Metropolis–Hastings acceptance probability. On rejection the old estimate must be retained. Integrating the extended target gives the desired marginal posterior distribution exactly.

Simulated annealing accepts worse feasible solutions to escape a local minimum. Minimize an objective function $E(x)$, analogous to energy. Effective temperature $T>0$ has the same units as $E$, absorbing the Boltzmann constant; it controls exploration, rather than a material's thermodynamic temperature.^[ref]

Given current feasible point $x$, draw $y$ from a proposal distribution $q(x,y)$. For a symmetric proposal distribution, $q(x,y)=q(y,x)$, use the Metropolis–Hastings acceptance probabilityAccept with this conditional probability; on rejection retain $x$. Every downhill or equal-cost proposal is accepted. Draw a fresh uniform random variable $U$ on $(0,1)$ and accept if $U<a_T(x,y)$. The off-diagonal transition probability $P_T(x,y)=q(x,y)a_T(x,y)$ includes proposing $y$.^[ref]

For a maximization problem with objective function $f$, set $E=-f$: every improving proposed neighbor is accepted, and a worsening move of loss $\Delta =f(x)-f(y)>0$ has conditional probability $\exp (-\Delta /T)$ of acceptance, under the same symmetry assumption. Likelihood-power annealing uses precisely this sign convention for a log-likelihood. Retain the best feasible solution seen, since the current state can worsen even after a global minimum has been visited.

If the proposal distribution is asymmetric, use the full Metropolis–Hastings acceptance probability, for $q(x,y)>0$,A missing reverse proposal gives zero acceptance. Even a downhill proposal need not be accepted with probability one in this case. Choosing uniformly among a variable number of neighbors is generally asymmetric: $q(x,y)=1/d(x)$ and $q(y,x)=1/d(y)$ give the correction $d(x)/d(y)$, where $d$ is vertex degree.^[ref]

The useful idea is to separate exploring from insisting on improvement: an uphill move can open a route to a better feasible solution. Its usefulness depends on the proposal distribution, the scale of the objective function, and the cooling schedule for simulated annealing. Finite practical schedules carry no general guarantee of finding a global minimum.

Surrogate Hamiltonian Monte Carlo uses an auxiliary smooth probability density function $\nu$ to generate trajectories but applies a Metropolis–Hastings acceptance probability using the intended target $\mu$. For Gaussian momenta and an involutive Metropolis proposal generated by flipped leapfrog integration, the acceptance probability is $\min (1,\mu (x^{\prime })e^{-\Vert p^{\prime }{\Vert }^2/2}/[\mu (x)e^{-\Vert p{\Vert }^2/2}])$. Only the surrogate gradient is required during the trajectory; target density evaluations are still required at the endpoints.

To minimize $E_j(\theta )=2k_j-2{\ell }_j(\theta )$ over models with different parameter dimensions, sample from a target proportional to $w_j{e}^{-E_j(\theta )/(2T)}$ and cool $T$. A dimension-matching proposal augments the smaller model by auxiliary variables, transforms them bijectively into the larger parameter vector, and includes the proposal probability density function and absolute Jacobian determinant in the Metropolis–Hastings acceptance probability. For a positive Poisson mean $\lambda$ and normal parameters $(\mu ,v)$, one convenient transformation isIts absolute Jacobian determinant is one. If the forward and reverse model-jump selection probabilities are $b$ and $d$, the Poisson-to-normal ratio isThe reverse ratio is its reciprocal at the inverse map. This enforces detailed balance. When the target is proper and the annealing chain explores it adequately, the low-temperature laws concentrate on the minimum Akaike information criterion, rather than the maximum marginal model evidence. Likelihoods compared across models must describe the same observed data with a compatible reference measure.