The Metropolis-Hastings algorithm: principle

Let us consider a transition kernel with density q(z,z'), which verifies the following property: , and guarantees the aperiodicity and the irreducibility of the chain. The principle is to build an acceptance probability a which guarantees the reversibility condition for . The Metropolis-Hastings algorithm is made of the two following steps:

1. we propose a transition state z' from the proposal kernel q(z,z'),
2. z' is accepted with probability a(z,z') (and the chain remains in z with probability 1-a(z,z')).

To guarantee the reversibility, it is sufficient to choose a so that :

Two common choices for a are the Barker dynamics:

and the Metropolis dynamics:
 
It is possible to show that for fixed target distribution and proposal kernel q the Metropolis dynamics is the acceptance probability which minimizes the variance estimation in the Monte Carlo integration [10]. Hence, in the following, we only consider the Metropolis dynamics given by equation 16.

A nice feature about the Metropolis-Hastings algorithm is that the target density needs only to be known up to a multiplicative factor, since only the ratio needs to be computed. This makes this sampling algorithm very attractive for Bayesian computation, where the posterior distribution is often only known up to a normalization factor.

Although convergence to the target distribution is guaranteed through the acceptance probability, the convergence rate is highly dependent on the choice of the proposal kernel q. In the sequel, we describe different possible choices for q.