Next: Error Analysis for MCMC Up: Simulation Methods Based on Previous: Gibbs Sampler   Contents

### 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.
1. The transition matrix can be of a more general form than the one defined by

 (46)

2. 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.

• 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

 (47)

• 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

 (48)

where

 (49)

• and is an arbitrary symmetric matrix such that

 (50)

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 .

Theorem 3.14   The transition matrix defined by - is irreducible and aperiodic and the pair is reversible.

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.

 (51)

we consider two cases.
• If , then and (51) holds.
• If , then also and (47)-(50) imply

where the last equality follows by the symmetry of the matrix .

Examples

1. 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.

 (52)

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

 (53)

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

then the acceptance probabilities are also given by (53).

2. Barker Algorithm
• The so-called Barker algorithm is obtained if we consider the matrix where for arbitrary .
• The acceptance probabilities are then given by

 (54)

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

 (55)

MCMC Simulation Algorithm

• As it was done for the Gibbs sampler (see Section 3.3.2) we construct a Markov chain
• with state space and with the (irreducible and aperiodic) transition matrix defined by (47)-(50)
• such that is the ergodic limit distribution of .
• 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.

Next: Error Analysis for MCMC Up: Simulation Methods Based on Previous: Gibbs Sampler   Contents
Ursa Pantle 2006-07-20