Metropolis-Hastings Algorithm

- We will now show that the Gibbs sampler discussed in
Section 3.3.2 is a special case of a class of MCMC
algorithms that are of the so-called
*Metropolis-Hastings type*. This class generalizes two aspects of the Gibbs sampler.- The transition matrix
can be of a
more general form than the one defined by

- Besides this, a
*procedure for acceptance or rejection*of the updates is integrated into the algorithm. It is based on a similar idea as the acceptance-rejection sampling discussed in Section 3.2.3; see in particular Theorem 3.5.

- The transition matrix
can be of a
more general form than the one defined by
- Let be a finite nonempty index set and let
be a discrete random vector,
- taking values in the finite state space with probability .
- As usual we assume for all where is the probability function of the random vector .

- We construct a Markov chain
with ergodic
limit distribution
whose transition matrix
is given by

- where is an arbitrary stochastic matrix that is irreducible and aperiodic, i.e. in particular if and only if .
- Moreover, the matrix
is
defined as

where

- and
is an arbitrary
symmetric matrix such that

**Remarks**-
- The structure given by (47) of the transition
matrix
can be
interpreted as follows.
- At first a candidate for the update is selected according to .
- If , then is accepted with probability ,
- i.e., with probability the update is rejected (and the current state is thus not changed).

- In order to apply the Metropolis-Hastings algorithm defined by (47)-(50), for a given ,,potential'' transition matrix only the quotients need to be known for all pairs of states such that .
- The special case of the Gibbs sampler (see Section
3.3.2) is obtained
- if the ,,potential'' transition probabilities are defined by (46).
- Then for arbitrary
such that
and thus
- By defining we obtain for arbitrary such that .

- The structure given by (47) of the transition
matrix
can be
interpreted as follows.

**Proof**-
- As the acceptance probabilities given by (48)-(50) are positive for arbitrary the irreducibility and aperiodicity of are inherited from the corresponding properties of .
- In order to check the detailed balance equation
(2.85), i.e.

we consider two cases.

**Examples**-
*Metropolis Algorithm*- The classic Metropolis algorithm is obtained if we consider equality
in (50), i.e. if
- In this case the acceptance probabilities
for arbitrary
such that
are of the following form:

i.e.

- If the matrix
of the ,,potential''
transition probabilities is symmetric, then (52)
implies

- In particular, if the ,,potential'' updates
are chosen ,,randomly'', i.e. if

- The classic Metropolis algorithm is obtained if we consider equality
in (50), i.e. if
*Barker Algorithm*- The so-called Barker algorithm is obtained if we consider the matrix where for arbitrary .
- The acceptance probabilities
are then given
by

- If the matrix
of ,,potential''
transition probabilities is symmetric, then

**MCMC Simulation Algorithm**-
- As it was done for the Gibbs sampler (see Section 3.3.2) we construct a Markov chain
- For sufficiently large the distribution on coincides approximately with .
- In estimating the approximation error for MCMC simulation
algorithms it is useful
- to know the
*variational distance*between the distributions and - as well as its
*upper bounds*; see Section 3.4.1.

- to know the