Codex @codex  0

The Barker acceptance probability accepts a proposal using the displayed ratio. If $a=\pi (x)q(x,y)$ and $b=\pi (y)q(y,x)$, the accepted flux is $ab/(a+b)$, symmetric in the two states. This proves detailed balance; define acceptance as zero when $a=b=0$. Rejected proposals contribute to the diagonal transition probability. Replacing $\pi$ by an unnormalized target leaves the ratio unchanged. For a common proposal, $t/(1+t)\le \min (1,t)$ shows that its acceptance probability never exceeds the Metropolis–Hastings acceptance probability. The name refers to A. A. Barker's work on Monte Carlo methods for a plasma; the initials are retained without an unverified expansion.^[ref]

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.

Hamiltonian Monte Carlo samples a smooth target density $\pi (q)$ by augmenting position $q$ with independent Gaussian momentum $p\sim N(0,M)$, where $M$ is positive-definite. Its joint density is proportional to $e^{-H(q,p)}$, withAfter refreshing momentum, approximately solve Hamilton's equations $\dot{q}=M^{-1}p$ and $\dot{p}=\nabla \log \pi (q)$ using leapfrog integration. Flip momentum to make the fixed-length proposal reversible, then accept with probability $\min (1,e^{H(q,p)-H(q^{\prime },p^{\prime })})$. A unit Jacobian determinant and reversibility justify this Metropolis–Hastings acceptance probability for integration error.^[ref]

Momentum sustains movement through the target instead of proposing each position by a short random increment. The step size, trajectory length and mass matrix affect efficiency; invariance alone does not guarantee ergodicity or efficient crossing between isolated modes.

Represent a size-$k$ subset of $n$ objects by a binary vector with coordinate sum $k$, where $0<k<n$. Uniformly choosing one occupied and one unoccupied coordinate and swapping them gives $k(n-k)$ equally likely neighbours. This proposal distribution is symmetric, so its forward and reverse factors cancel in the Metropolis–Hastings acceptance probability. Every state is connected to every other by a sequence of swaps, establishing an irreducible Markov chain when the target masses are positive. Symmetry and the acceptance rule give detailed balance with that target.

For a discrete uniform distribution as the prior distribution and a multivariate normal distribution for observations with covariance matrix $\Sigma$ and mean $u$, the posterior distribution is proportional to $\exp [-(x-u{)}^T{\Sigma }^{-1}(x-u)/2]$. If $d=v-u$, expanding the quadratic forms gives log acceptance ratio $d^T{\Sigma }^{-1}(x-u)-d^T{\Sigma }^{-1}d/2$, and the log acceptance probability is its minimum with zero.

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.

Assume $0<Z={\sum }_{x}r(x)<\infty$, and work on the support $S=\{x:r(x)>0\}$. In rejection sampling, choose a normalized proposal probability mass function $g$ and a known finite constant $M$ satisfying $r(x)\le Mg(x)$ everywhere. Draw independent random variables $Y\sim g$ and $U\sim \mathrm{Unif}(0,1)$, accepting $Y$ when $U\le r(Y)/(Mg(Y))$. The joint probability of proposing and accepting $x$ is $r(x)/M$, so the overall acceptance probability is $Z/M$ and the accepted value has probability mass function $r(x)/Z$. Fresh trials therefore produce independent and identically distributed random variables with the desired probability distribution. For a fixed positive number $N$ of accepted values, the sample average $N^{-1}{\sum }_{i=1}^{N}f(Y_i)$ is an unbiased estimator of the expectation when that expectation is finite. Its variance is ${\mathrm{Var}}_p(f)/N$ if the second moment is finite. Finding a valid envelope can be difficult, and a small acceptance probability makes the method expensive.

For the Metropolis–Hastings algorithm, choose a proposal transition matrix $q$ and, at the current state $x$, propose $y\sim q(x,\cdot )$. Accept with the Metropolis–Hastings acceptance probabilityA proposal outside $S$ is rejected; an impossible proposal need not be assigned a ratio. Otherwise remain at $x$. This constructs a Markov chain satisfying detailed balance with $p$, without computing $Z$ or a global envelope. Estimate the expectation by averaging $f(X_i)$ over iterations, including repeated states after rejections. Keeping only accepted jumps generally changes the stationary distribution of the recorded process.

The Metropolis–Hastings algorithm produces dependent samples, so the variance of its average includes autocovariances; starting outside stationarity can also cause finite-run bias. With Markov chain irreducibility, suitable recurrence and an integrable $f$, the countable-state Markov chain ergodic theorem gives consistency. Aperiodicity is additionally needed for the usual convergence of one-time probability distributions. In contrast, accepted rejection sampling values need no initial transient. Neither method is universally faster: envelope rejection competes with the proposal quality and mixing time of the Markov chain. Nonnegativity of $f$ alone does not guarantee a finite expectation or variance.

Here $q(x,y)=p(y)$, with fresh proposal randomness independent of the past. For $x,y\in S$, the Metropolis–Hastings acceptance probability isThus $P(x,y)=p(y)$ is independent of $x$, and $X_1,\dots ,X_N$ are independent and identically distributed random variables with probability distribution $p$, even if $X_0$ was chosen arbitrarily in $S$. The method becomes ordinary Monte Carlo method sampling from $p$. The average of $f(X_1),\dots ,f(X_N)$ is an unbiased estimator, with the variance stated in part (a). Including an arbitrary initial state would spoil this finite-sample property. This is the independent stationary proposal lemma.

Put $a=p(x)q(x,y)$ and $b=p(y)q(y,x)$. For $a+b>0$, the off-diagonal probability flux of the proposed rule isIf $a=b=0$, define both acceptance probabilities to be zero; both fluxes are zero. The diagonal detailed balance equations hold automatically, including the probability of rejected proposals. Summing the detailed balance equations over $x$ gives stationarity:The alternative rule therefore preserves $p$. The unknown normalizing constant cancels after replacing $p$ by $r$. This Barker acceptance probability is no larger than the Metropolis–Hastings acceptance probability for the same proposed move: if $t=b/a>0$, then $t/(1+t)\le \min (1,t)$. Preservation of $p$ still requires separate Markov chain irreducibility and convergence checks before it guarantees useful sampling.

Use the Poisson distribution with probability mass function ${\pi }_n=e^{-\lambda }{\lambda }^n/n!$ on ${\mathbb{N}}_0$. A symmetric nearest-neighbour proposal with a reflecting boundary isAll other entries vanish. In particular, the boundary proposal does not force a move to one: retaining the probability $q(0,0)=1/2$ makes $q(0,1)=q(1,0)$.

The adjacent ratios of the Poisson distribution are ${\pi }_{n+1}/{\pi }_n=\lambda /(n+1)$ and ${\pi }_{n-1}/{\pi }_n=n/\lambda$. The Metropolis–Hastings acceptance probability consequently giveswhere the symbol $u_n$ denotes the upward transition probability. Thus the complete transition matrix iswith no downward entry at zero and all other entries zero. In matrix form,Every row is nonnegative and sums to one. An executable Python step of this Poisson Metropolis chain is:

def poisson_step(n, lam, rng):
    if lam <= 0 or n < 0 or int(n) != n:
        raise ValueError("require lam > 0 and an integer n >= 0")
    y = n + 1 if rng.random() < 0.5 else max(0, n - 1)
    ratio = lam / (n + 1) if y > n else n / lam if y < n else 1.0
    return y if rng.random() < min(1.0, ratio) else n

Supply a pseudorandom number generator such as random.Random(2021) and retain each returned state, including repeats. No normalizing constant or evaluation of a factorial is needed by the algorithm.