What is the connection between Markov chain and Markov chain monte carlo

Question

I am trying to understand Markov chains using SAS. I understand that a Markov process is one where the future state depends only on the current state and not on the past state and there is a transition matrix that captures the transition probability from one state to another.

But then I came across this term :Markov Chain Monte Carlo. What I want to know is if Markov Chain Monte Carlo is in anyway related to Markov process that I describe above?

Answer 1

Well, yes, there is a relationship between the two terms because the draws from MCMC form a Markov chain. From Gelman, Bayesian Data Analysis (3rd ed), p. 265:

Markov chain simulation (also called Markov chain Monte Carlo or MCMC) is a general method based on drawing values of $\theta$ from appropriate distributions and then correcting those draws to better approximate the target posterior distribution, $p(\theta|y)$. The sampling is done sequentially, with the distribution of the sampled draws depending on the last value drawn; hence, the draws form a Markov chain.

Answer 2

The connection between both concepts is that Markov chain Monte Carlo (aka MCMC) methods rely on Markov chain theory to produce simulations and Monte Carlo approximations from a complex target distribution $\pi$.

In practice, these simulation methods output a sequence $X_1,\ldots,X_N$ that is a Markov chain, i.e., such that the distribution of $X_i$ given the whole past $\{X_{i-1},\ldots,X_1\}$ only depends on $X_{i-1}$. In other words, $$X_i=f(X_{i-1},\epsilon_i)$$ where $f$ is a function specified by the algorithm and the target distribution $\pi$ and the $\epsilon_i$'s are iid. The (ergodic) theory guarantees that $X_i$ converges (in distribution) to $\pi$ as $i$ gets to $\infty$.

The easiest example of an MCMC algorithm is the slice sampler: at iteration i of this algorithm, do

1. simulate $\epsilon^1_i\sim\mathrm{U}(0,1)$
2. simulate $X_{i}\sim\mathrm{U}(\{x;\pi(x)\ge\epsilon^1_i\pi(X_{i-1})\})$ (which amounts to generating a second independent $\epsilon^2_i$)

For instance, if the target distribution is a normal $\mathrm{N}(0,1)$ [for which you obviously would not need MCMC in practice, this is a toy example!] the above translates as

1. simulate $\epsilon^1_i\sim\mathrm{U}(0,1)$
2. simulate $X_{i}\sim\mathrm{U}(\{x;x^2\le-2\log(\sqrt{2\pi}\epsilon^1_i\})$, i.e., $X_i=\pm \epsilon_i^2\{-2\log(\sqrt{2\pi}\epsilon^1_i)\varphi(X_{i-1})\}^{1/2}$ with $\epsilon_i^2\sim\mathrm{U}(0,1)$

or in R

T=1e4
x=y=runif(T) #random initial value
for (t in 2:T){
  epsilon=runif(2)#uniform white noise 
  y[t]=epsilon[1]*dnorm(x[t-1])#vertical move       
  x[t]=sample(c(-1,1),1)*epsilon[2]*sqrt(-2*#Markov move from
        log(sqrt(2*pi)*y[t]))}#x[t-1] to x[t]

Here is a representation of the output, showing the right fit to the $\mathrm{N}(0,1)$ target and the evolution of the Markov chain $(X_i)$.

And here is a zoom on the evolution of the Markov chain $(X_i,\epsilon^1_i\pi(X_i))$ over the last 100 iterations, obtained by

curve(dnorm,-3,3,lwd=2,col="sienna",ylab="")
for (t in (T-100):T){
lines(rep(x[t-1],2),c(y[t-1],y[t]),col="steelblue");
lines(x[(t-1):t],rep(y[t],2),col="steelblue")}

that follows vertical and horizontal moves of the Markov chain under the target density curve.