Metropolis–Hastings algorithm

The Metropolis-Hastings algorithms is an implementation of the Markov Chain Monte Carlo, where the Markov Chain used to generate examples is decoupled into 2 steps:

1. A generation of a candidate $x^{\prime }$ from a probability distribution $f_x$, dependent on the current state $x$.
2. The acceptance or rejection of the candidate $x^{\prime }$ by testing $\frac{L(x^{\prime })}{L(x)}\ge U$, where $L(x)$ is the likelihood of state $x$, and the $U$ is a uniform random variable on the interval $[0,1]$.

Warning

This algorithm might give us poor samples / get stuck in local maxima. As an example, the plot below results from

• Using the Normal distribution for generating new candidates
• Using $e^{-(x-3{)}^2}+e^{-(x+3{)}^2}$ as the likelihood function, in practice creating $2$ local maxima for the likelihood, centered around $-3$ and $3$.

Observe how the candidates jump from the two regions. This causes the sampled observations to be far from the underlying stationary distribution, as can be observed by the marginal distribution below.