Does “Markov Chain Monte Carlo” method really need “Markov Chain”? [duplicate]

Question

I am studying MCMC with "Pattern Recognition and Machine Learning" Book by Christopher Bishop. In the chapter of MCMC, this book introduces Markov Chain also a little bit.

However, while reading the book, I wonder why Markov chain is needed. Because to conduct the Metropolis-Hasting algorithm, for every step I make sample from proposal distribution and then decide whether it is accepted or not.

For me, this Metropolis-Hasting algorithm is more like rejection sampling. Adopting proposal distribution that we can directly draw sample from and deciding the sample should be accepted or not are similar.

Where is the room for using Markov chain? Do I need to calculate 'transition matrix' for Metropolis-Hasting algorithm? At this my confusing state, I feel that I can conduct Metropolis-Hasting sampling without need of transition matrix of Markov Chain.

I am very confusing now. This book just says "under some circumstances a Markov chain converges to the desired distribution". But it does not say how can I design the Markov chain to converge distribution I desire. And many of the materials in the Internet also seems to skip this part. I thought designing transition matrix of MC is important part to conduct MCMC. But now, I guess it is not necessary.

Thanks in advance.

Answer 1

First, there are more Markov chain Monte Carlo (MCMC) samplers aside from the Metropolis-Hastings (MH), but I will focus on MH.

It is not that a Markov chain is needed, it is that using an MH algorithm the samples obtained themselves form a Markov chain that converge to the stationary distribution indicated in the accept-reject criterion. There are a couple of differences between rejection sampling and MH. Lets say your distribution from which you desire samples is $\pi$.

1. In MH if your current sample is $x$, you draw a sample $y$ from a proposal distribution $q$, and find the following accept reject ratio $$\min \left( 1,\dfrac{\pi(y) \,q(x \mid y)}{\pi(x) \, q(y \mid x) } \right). $$ Notice that the accept-reject ratio itself is a function of the current step $x$. Even if your proposal is not dependent on your current step (like in Independent MH), your ratio will still be $$\min \left( 1,\dfrac{\pi(y) \,q(x)}{\pi(x) \, q(y) } \right), $$ which again depends on the current step. Thus the probability with which you accept or reject depends on the current step, making the samples that you obtain a Markov chain.

2. If the proposed step is rejected in MH, then the next step is the same as the current step. So again, the next step depends on the previous step, and thus we have a Markov chain.

The stationary distribution that the MH algorithm will converge to is the one that takes $\pi$s position in the ratio. If you replace it with any other distribution, the samples you get will converge to that distribution. Whether the Markov chain converges or not is something practioners don't have to worry about because this has already been proven for the MH algorithm.

Finally, there is no need to calculate the transition matrix because there is a clear path of updating the Markov chain without a transition matrix. Also, for when the state space infinite (like the real line), then we can no longer deal with the transition matrix and have to study the transition "kernel". But this is not required since the way the Markov chain updates itself is only theMH-ratio algorithm, and no other information is needed.

Answer 2

This is just confusion with the terminology. It's not that you need to "use" a Markov chain to draw Metropolis-Hastings samples, it's that the sequence of Metropolis-Hastings draws is a Markov chain. This is an innate part of the algorithm design.

"Markov chain Monte Carlo" is just a qualifier indicating that the draws from this Monte Carlo algorithm produce a Markov chain.

Answer 3

MCMC in general and Metropolis-Hastings in particular is quite distinct from rejection sampling.

• Note that rejection sampling is independent from one generated value to the next -- it doesn't matter what value you just generated, the distribution of the next one doesn't consider it. MCMC involves a series of moves. At one step you are at some value and then conditional on that value you have some way of possibly moving to a (possibly) new value next step.

• In addition, you left out of your description what happens when you reject.

  In rejection sampling you simply fail to have a value. You generate again.

  In Metropolis-Hastings, you fail to accept the move, so you retain the previous value.