# Could someone help me to understand the Metropolis-Hastings algorithm for discrete Markov Chains?

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.

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}$$