Metropolis–Hastings algorithm

The Metropolis–Hastings algorithm proposes $y$ from $q(x,\cdot )$ at state $x$ and accepts it with probabilityThis acceptance rule enforces detailed balance with the target density $\pi$.

The Metropolis algorithm is the symmetric-proposal case of the Metropolis–Hastings algorithm. At state $x$ with positive target density $\pi (x)$, propose $y$ from $q(x,\cdot )$ with $q(x,y)=q(y,x)$, and accept with probabilityOtherwise remain at $x$. A normalizing constant in $\pi$ cancels, which makes the method useful when a target distribution is known only up to scale.

The accepted probability flow is $\pi (x)q(x,y)\alpha (x,y)=q(x,y)\min \{\pi (x),\pi (y)\}$, symmetric in $x,y$. This proves detailed balance and hence invariance of the target under the usual kernel assumptions.

For two states with target masses $1/4,3/4$ and an always-flip proposal, moves from the first state are always accepted, while reverse moves are accepted with probability $1/3$. The rejection probability creates holding at the second state. Target invariance alone does not prove convergence from every start; irreducibility and appropriate periodicity conditions matter. An asymmetric proposal requires the Hastings proposal-density correction.

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]

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 Metropolis-within-Gibbs sweep updates one coordinate or block at a time by a Metropolis–Hastings algorithm transition whose invariant law is that block's full conditional distribution. For a proposal changing only block $j$, the acceptance ratio uses the full joint target with the other coordinates fixed, together with the reverse/forward proposal ratio. Each block kernel preserves the joint posterior, so their composition does as well. Conjugate blocks can instead use exact Gibbs sampling draws. Systematic composition need not be reversible, even when every block kernel is reversible.

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.

An unbiased likelihood estimator has expectation equal to the likelihood function at each parameter. A pseudo-marginal algorithm requires this estimator to be nonnegative. Importance sampling provides $\hat{L}=M^{-1}{\sum }_j\ell (F_j)p_{\theta }(F_j)/g_{\theta }(F_j)$ for independent random variables $F_j\sim g_{\theta }$, provided the proposal covers the target support. Relative variance affects the mixing time even though unbiasedness guarantees the correct marginal target.

For target density $\pi$ and proposal density $q$, the Metropolis–Hastings acceptance probability is $1\wedge \{\pi (y)q(y,x)/(\pi (x)q(x,y))\}$.

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.

An involutive Metropolis proposal uses a deterministic bijection $S$ satisfying $S^2=I$. For a volume-preserving $S$ and target probability density function $\rho$, accept $S(z)$ with probability $\min (1,\rho (S(z))/\rho (z))$. The identity $\rho (z)\alpha (z)=\min (\rho (z),\rho (S(z)))$ and a change of variables under $S$ prove detailed balance. A non-unit Jacobian determinant must be included when volume is not preserved.

For a proposal $Y=AX+Z$, with isotropic $Z\sim N(0,I)$ and an independent random orthogonal matrix $A$, invariance of the distribution of $A$ under transpose makes the proposal distribution symmetric. Indeed $|y-Ax|=|x-A^{T}y|$, and averaging the isotropic Gaussian density over an inversion-invariant law yields $q(x,y)=q(y,x)$. The Metropolis–Hastings algorithm therefore accepts with the target density ratio alone.

Let $0<\beta \le 1$, let $X\in {\mathbb{R}}^p$, and proposeThe proposal distribution is $N(\sqrt{1-{\beta }^2}X,{\beta }^2{I}_p)$. If $X\sim N(0,I_p)$ independently of $Z$, then $(X,Y)$ is a jointly multivariate normal distribution invariant under exchanging $X$ and $Y$, because both random vectors have covariance matrix $I_p$ and their cross-covariance matrices are both $\sqrt{1-{\beta }^2}{I}_p$. Consequently its density $q$ satisfieswhere $\varphi$ is the standard-normal density. Thus the proposal is reversible with respect to the standard normal distribution.

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.

Random-walk Metropolis proposes a symmetric increment from the current state and accepts a proposal $y$ from $x$ with probability $\min \{1,\pi (y)/\pi (x)\}$.

A Poisson Metropolis chain samples a Poisson distribution by proposing an upward or downward unit step with equal probability and reflecting a downward proposal at zero into a self-proposal. Its upward and downward transition probabilities are the displayed $u_n,d_n$, with $d_0=0$, and the diagonal entry is $1-u_n-d_n$. For ${\pi }_n=e^{-\lambda }{\lambda }^n/n!$, adjacent stationary fluxes equal $\frac{1}{2}\min ({\pi }_n,{\pi }_{n+1})$. Hence detailed balance holds. Positive adjacent probabilities imply an irreducible Markov chain; $P(0,0)\ge 1/2$ implies aperiodicity. The normalized invariant Poisson distribution implies positive recurrence, so the countable-state Markov chain convergence theorem applies. The boundary proposal probability is essential: forcing every proposal at zero to go upward would require a different acceptance ratio.

To update a positive parameter, a symmetric additive proposal distribution can be generated on the whole real line. Reject nonpositive proposals; accept positive ones using the target density ratio. The off-diagonal proposal remains symmetric. Repeatedly redrawing until the proposal is positive instead truncates and renormalizes the proposal differently at different current states, so a Hastings correction is then required. A symmetric walk in $\log v$ is another valid method, but its transformed target includes the Jacobian determinant factor $v$.

A small proposal scale increases acceptance while making successive states almost equal. A large scale often proposes low-density states and creates long rejection runs. A pilot comparison can optimize effective sample size of a Markov chain per unit computing time, or expected accepted squared displacement, rather than acceptance alone. Tune on representative functions and then fix the scale for production; an arbitrarily history-dependent adaptation is not automatically a chain with the desired invariant distribution.

An independence Metropolis–Hastings algorithm proposes from a fixed density $q$ independent of the current state. If ${\sup }_x\pi (x)/q(x)<\infty$, it is uniformly and hence geometrically ergodic.

If a Metropolis–Hastings algorithm proposes fresh draws from its target stationary distribution $\pi$, its acceptance ratio on the positive support is $\pi (y)\pi (x)/(\pi (x)\pi (y))=1$. Therefore every proposal is accepted, and $P(x,y)=\pi (y)$. From the first update onward the recorded states are independent and identically distributed random variables with law $\pi$, regardless of the initial state in the support. An arbitrary initial state is excluded when claiming an unbiased finite-sample average.