0
$\begingroup$

Metropolis-Hastings Algorithm

Assume the Markov chain is in some state $X_{n} = i$. Let $\textbf{H}$ be the transition matrix for any irreducible Markov chain on the state space. We generate $X_{n+1}$ via the following algorithm:

(a) Choose a proposal state $j$ according to the probability distribution in the $i$-th row of $\textbf{H}$.

(b) Compute the acceptance probability $\alpha_{ij} = \min\left\{1,\displaystyle\frac{\pi_{j}H_{ji}}{\pi_{i}H_{ij}}\right\}$

(c) Generate a uniform random number $U\sim\text{Uniform}(0,1)$. If $U<\alpha_{ij}$, accept the move and set $X_{n+1} = j$. Otherwise, reject the move and keep $X_{n+1} = X_{n}$.

MY DOUBTS

I know that Markov chains that are aperiodic and irreducible admit a stationary distribution. I also know that any distribution $\pi$ satisfying the reversibility condition is an equilibrium distribution.

As far as I have understood, the Metropolis-Hastings algorithm proposes a Markov chain whose stationary distribution is $\pi$ (the target distribution we are interested in sampling) and then simulate the Markov chain.

However, I am a little bit lost as to the interpretation of the algorithm itself. Could someone interpret it step by step to me?

I know such question is quite naive, but I am not able to understand it properly. Any help is appreciated.

$\endgroup$
2
  • 1
    $\begingroup$ I don't claim to remember-understand the derivation now but I remember this paper making it click for me at the time. ( which was many years ago ). web1.sph.emory.edu/users/hwu30/teaching/statcomp/papers/… $\endgroup$
    – mlofton
    Commented Oct 7, 2019 at 4:41
  • $\begingroup$ Thanks for the reference. $\endgroup$
    – user242554
    Commented Oct 7, 2019 at 22:30

1 Answer 1

1
$\begingroup$

"...the Metropolis-Hastings algorithm proposes a Markov chain whose stationary distribution is 𝜋 (the target distribution we are interested in sampling) and then simulate the Markov chain."

This is not correct: $\mathbf H$ is a stochastic matrix associated with a Markov chain which stationary distribution is not $\pi$. The (different) stationary distribution associated with $\mathbf H$ does not matter, since the proposed state $j$ is potentially rejected with the Metropolis-Hastings acceptance probability $\alpha_{ij}$. The total transition matrix is thus made of the elements $$\beta_{ij} = \alpha_{ij} H_{ij} + \sum_{\ell=1}^k(1-\alpha_{i\ell}) H_{i\ell} \mathbb{I}_{i=j}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.