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
$\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, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.