A special type of Markov Chain Monte Carlo (MCMC) algorithm used to simulate from complex probability distributions. It is validated by Markov chain theory and offers a wide range of possible implementations.
The Metropolis-Hastings algorithm is a Markov Chain Monte Carlo (MCMC) technique used to sample from arbitrary probability distributions. The steps of the algorithm to sample from a distribution with density $\mathscr{p}(x)$ are as follows:
- Choose an initial point $x_0$ and a proposal distribution $\mathscr{q}(y|z)$. Let $t=0$.
- Generate a candidate point $x^\star$ according to the proposal with density $\mathscr{q}(x|x_t)$.
- Calculate the value of $$\alpha=\min\left(1,\frac{\mathscr{p}(x^\star)\mathscr{q}(x_t|x^\star)}{\mathscr{p}(x_t)\mathscr{q}(x^*|x_t)}\right)$$
- Accept the point $x^\star$ as $x_{t+1}$ with probability $\alpha$ and else set $x_{t+1}=x_t$.
- Increment $t$ ($t\rightarrow t+1$) and return to step 2 and iterate until the desired $t_\max$ is reached.
The Metropolis-Hasting algorithm is the generalization of the original or random-walk Metropolis algorithm, for which the proposal density $\mathscr{q}$ must be symmetric, i.e. $\mathscr{q}(y|z)=\mathscr{q}(z|y)$. It is validated by the detailed balance condition, which shows that the Markov chain is both invariant wrt $\mathscr{p}(\cdot)$ and time-reversible.
