Metropolis-Hastings transitions

Consider the transition from $X_i$

to the next realized state $X_{i+1}$ .

Let $q(x, x^\prime)$ denote a transition probability function, such that if $X_i=x$ , $x^\prime$ drawn from $q(x,x^\prime)$ is considered a possible value for $X_{i+q}$ . With some probability $\alpha(x, x^\prime)$ , we accept $X_{i+1}=x^\prime$ ; otherwise we reject $x^\prime$ and set $X_{i+1}=x$ . In other words, we have defined defined a Markov chain with transition probabilities given by:

$P(x, x^\prime) = q(x, x^\prime)\alpha(x, x^\prime)$

if $x\not=x^\prime$ , or

$P(x, x^\prime) = 1-\sum_{x\not=x^\prime} q(x, x^\prime)\alpha(x, x^\prime)$

otherwise.

If we now set:

$\alpha(x, x^\prime) = \min\left[1, {\pi(x^\prime)q(x^\prime, x)\over \pi(x)q(x, x^\prime)} \right]$

if $\pi(x)q(x^\prime, x)>0$ and $\alpha(x, x^\prime) = 1$ otherwise.

It is now easy to check that $\pi(x)p(x,x^\prime) = \pi(x^\prime)p(x^\prime, x)$ . One can then show that $\pi(x)$ is the equilibrium distribution of the Markov chain if $q(x,x^\prime)$ is aperiodic and irreducible (Hastings 1970).

There are a number of often used special cases:

The Metropolis Algorithm: $q(x, x^\prime) = q(x^\prime, x)$
The Random Walk chain: $q(x, x^\prime) = q(x-x^\prime)$
The Independence chain: $q(x, x^\prime) = q(x^\prime)$
Gibbs sampling: $q(x, x^\prime) = P(x^\prime_i | x_j), j\not=i$

Send suggestions, questions, and feedback to WEINBERG at ASTRO dot UMASS dot EDU.
Documentation generated at Fri Mar 26 00:35:11 2010 by

BIE

Metropolis-Hastings transitions