The Metropolis-Hastings algorithm 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 from a probability distribution , dependent on the current state .
  2. The acceptance or rejection of the candidate by testing , where is the likelihood of state , and the is a uniform Random variable on the interval .

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 as the likelihood function, in practice creating local maxima for the likelihood, centered around and .

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.