MCMC

Metropolis Algorithm

Let $\pi$ be a pdf of interest on a state space

, and let $\mathbf{Q}$ be a transition probability on

. Define the acceptance probability by

$\displaystyle A(x,y) := \min\left\{\dfrac{\pi(y) \mathbf{Q}(y,x)} {\pi(x)\mathbf{Q}(x,y)}, 1 \right\}$

for a move from

satisfying $\mathbf{Q}(x,y) \neq 0$ and $\mathbf{Q}(y,x) \neq 0$ . The Metropolis-Hastings algorithm can be implemented as follows:

Choose an initial state at time .
Suppose that at time . Then pick according to $\mathbf{Q}(x,\cdot)$ .
Move to $X_{t+1} = y$ with the probability , or stay $X_{t+1} = x$ with the probability .

Transition probability. One should choose $\mathbf{Q}$ to be irreducible on , and call it a proposal chain. In terms of transition probability, the above algorithm is given by

$\displaystyle \mathbf{P}(x,y) = \begin{cases} \mathbf{Q}(x,y) A(x,y) \quad\mb... ..._{z \in S} \mathbf{Q}(x,z) (1 - A(x,z)) \quad\mbox{ if } x = y. \end{cases}$

Then $\mathbf{P}$ is irreducible, aperiodic and reversible transition probability with the stationary distribution $\pi$ .

Reversibility. The detailed balance clearly holds for either or $\pi(x) \mathbf{Q}(x,y) = \pi(y) \mathbf{Q}(y,x)$ . Let $x \neq y$ . Suppose that $\pi(x) \mathbf{Q}(x,y) > \pi(y) \mathbf{Q}(y,x)$ . Then $A(x,y) = \frac{\pi(y) \mathbf{Q}(y,x)}{\pi(x)\mathbf{Q}(x,y)}$ and , and therefore, we obtain

$\pi(x) \mathbf{P}(x,y) = \pi(x) \mathbf{Q}(x,y) A(x,y)$ $= \pi(y) \mathbf{Q}(y,x) = \pi(y) \mathbf{P}(y,x)$ .

By symmetry it also holds for the case that $\pi(x) \mathbf{Q}(x,y) < \pi(y) \mathbf{Q}(y,x)$ .