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$.

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)\}$.

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.