14
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Umm ok, but why do i need to draw random samples form a markov process, there are so many other kinds of processes like normal, bernoulli, possion etc. $\endgroup$ – Victor Aug 31 '15 at 16:17
  • 2
    $\begingroup$ @Victor I think you've lost sight of the use case of MCMC. We use MCMC in Bayesian statistics when there is no analytical form of the posterior distribution. $\endgroup$ – Sycorax Aug 31 '15 at 16:19
  • 3
    $\begingroup$ +1 Bayesian statistics is perhaps the most obvious application of MCMC (where the target distribution is a joint posterior) but not the only possible one. $\endgroup$ – Glen_b Sep 1 '15 at 1:17
17
$\begingroup$

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)$. top: Histogram of 10⁴ iterations of the slice sampler and normal N(0,1) fit; bottom: sequence $(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.100 last moves of the slice sampler

$\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.