Homepage > MCMC

Metropolis Algorithm

Let $ \pi$ be a pdf of interest on a state space $ S$, and let $ \mathbf{Q}$ be a transition probability on $ S$. 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 $ x$ to $ y$ satisfying $ \mathbf{Q}(x,y) \neq 0$ and $ \mathbf{Q}(y,x) \neq 0$. The Metropolis-Hastings algorithm can be implemented as follows:
  1. Choose an initial state $ X_0$ at time $ t = 0$.
  2. Suppose that $ X_t = x$ at time $ t$. Then pick $ y$ according to $ \mathbf{Q}(x,\cdot)$.
  3. Move to $ X_{t+1} = y$ with the probability $ A(x,y)$, or stay $ X_{t+1} = x$ with the probability $ (1 - A(x,y))$.

Transition probability. One should choose $ \mathbf{Q}$ to be irreducible on $ S$, 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 $ x = y$ 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 $ A(y,x) = 1$, 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)$.


© TTU Mathematics