Markov Chain Monte Carlo Methods

Rejection Sampling

Many MCMC algorithms are strongly related to rejection sampling, and this is the main reason for our discussion of rejection sampling.

A simple example best illustrates the idea behind rejection sampling. Let π is a distribution on [0,1] with density p(x). Now, suppose that there is another distribution with density q(x) on [0,1] such that p(x) < Mq(x) for all x and such that we can sample from q. To get one sample X from π, let Y be a sample from q and U be a sample from U[0,1]. If U < p(Y)/(Mq(Y)) = p(Y)/M, then we accept Y as a sample from q and set X = Y, else we reject and try again (see Figure 1 for an illustration of this).

We see that the infinitesimal probability that X = x is returned is

so this gives a perfect sample from p(x). Notice, however, that the efficiency is 1/M, because only one out of every M samples will be accepted.

Figure 1 Rejection Sampling

In general, any distribution q with p(x) ≤ Mq(x) will do (not just uniform), and the efficiency will again be 1/M.

Generalities on MCMC

For Monte Carlo simulation, we require samples from the distribution π. This is very often either impossible or highly impractical to do. Even if it is possible to generate one perfect sample, we need many independent samples for a Monte Carlo simulation. MCMC eases this problem by giving up the requirement for independent samples from π and generating instead many correlated approximate samples from π, with the approximation improving as the simulation continues.

The ergodic theorem gives some very general conditions under which MCMC will work. A Markov chain with state space Ω is irreducible if it is possible for the chain to get from any state in Ω to any other state in Ω, and it is positively recurrent if the expected time for transition from state i to state j is finite for every i,j ∊Ω. Clearly if Ω is finite and the chain is irreducible, then it is also positively recurrent.

...