Markov chain Monte Carlo

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In statistics, Markov chain Monte Carlo (MCMC) methods are a class of algorithms for sampling from a probability distribution based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a number of steps is then used as a sample of the desired distribution. The quality of the sample improves as a function of the number of steps.

Convergence of the Metropolis-Hastings algorithm. MCMC attempts to approximate the blue distribution with the orange distribution

Random walk Monte Carlo methods make up a large subclass of MCMC methods.

Application domains[edit]


Random walk Monte Carlo methods[edit]

See also: Random walk

Multi-dimensional integrals[edit]

When an MCMC method is used for approximating a multi-dimensional integral, an ensemble of "walkers" move around randomly. At each point where a walker steps, the integrand value at that point is counted towards the integral. The walker then may make a number of tentative steps around the area, looking for a place with a reasonably high contribution to the integral to move into next.

Random walk Monte Carlo methods are a kind of random simulation or Monte Carlo method. However, whereas the random samples of the integrand used in a conventional Monte Carlo integration are statistically independent, those used in MCMC methods are correlated. A Markov chain is constructed in such a way as to have the integrand as its equilibrium distribution.


Examples of random walk Monte Carlo methods include the following:

  • Metropolis–Hastings algorithm: This method generates a random walk using a proposal density and a method for rejecting some of the proposed moves.
  • Gibbs sampling: This method requires all the conditional distributions of the target distribution to be sampled exactly. When drawing from the full-conditional distributions is not straightforward other samplers-within-Gibbs are used (e.g., see [4][5][6]). Gibbs sampling is popular partly because it does not require any 'tuning'.
  • Slice sampling: This method depends on the principle that one can sample from a distribution by sampling uniformly from the region under the plot of its density function. It alternates uniform sampling in the vertical direction with uniform sampling from the horizontal 'slice' defined by the current vertical position.
  • Multiple-try Metropolis: This method is a variation of the Metropolis–Hastings algorithm that allows multiple trials at each point. By making it possible to take larger steps at each iteration, it helps address the curse of dimensionality.[7][8]
  • Reversible-jump: This method is a variant of the Metropolis–Hastings algorithm that allows proposals that change the dimensionality of the space.[9] MCMC methods that change dimensionality have long been used in statistical physics applications, where for some problems a distribution that is a grand canonical ensemble is used (e.g., when the number of molecules in a box is variable). But the reversible-jump variant is useful when doing MCMC or Gibbs sampling over nonparametric Bayesian models such as those involving the Dirichlet process or Chinese restaurant process, where the number of mixing components/clusters/etc. is automatically inferred from the data.

Other MCMC methods[edit]

Training-based MCMC[edit]

Unlike most of the current MCMC methods that ignore the previous trials, using a new algorithm the MCMC algorithm is able to use the previous steps and generate the next candidate. This training-based algorithm is able to speed-up the MCMC algorithm by an order or magnitude.[10]

Interacting MCMC methodologies are a class of mean field particle methods for obtaining random samples from a sequence of probability distributions with an increasing level of sampling complexity.[11] These probabilistic models include path space state models with increasing time horizon, posterior distributions w.r.t. sequence of partial observations, increasing constraint level sets for conditional distributions, decreasing temperature schedules associated with some Boltzmann-Gibbs distributions, and many others. In principle, any MCMC sampler can be turned into an interacting MCMC sampler. These interacting MCMC samplers can be interpreted as a way to run in parallel a sequence of MCMC samplers. For instance, interacting simulated annealing algorithms are based on independent Metropolis-Hastings moves interacting sequentially with a selection-resampling type mechanism. In contrast to traditional MCMC methods, the precision parameter of this class of interacting MCMC samplers is only related to the number of interacting MCMC samplers. These advanced particle methodologies belong to the class of Feynman-Kac particle models,[12][13] also called Sequential Monte Carlo or particle filter methods in Bayesian inference and signal processing communities.[14] Interacting MCMC methods can also be interpreted as a mutation-selection genetic particle algorithm with MCMC mutations.

Markov Chain quasi-Monte Carlo (MCQMC)[15][16] The advantage of low-discrepancy sequences in lieu of random numbers for simple independent Monte Carlo sampling is well known.[17] This procedure, known as Quasi-Monte Carlo method (QMC),[18] yields an integration error that decays at a superior rate to that obtained by IID sampling, by the Koksma-Hlawka inequality. Empirically it allows the reduction of both estimation error and convergence time by an order of magnitude.[citation needed]

Reducing correlation[edit]

More sophisticated methods use various ways of reducing the correlation between successive samples. These algorithms may be harder to implement, but they usually exhibit faster convergence (i.e. fewer steps for an accurate result).


Examples of non-random walk MCMC methods include the following:

  • Hybrid Monte Carlo (HMC): Tries to avoid random walk behaviour by introducing an auxiliary momentum vector and implementing Hamiltonian dynamics, so the potential energy function is the target density. The momentum samples are discarded after sampling. The end result of Hybrid Monte Carlo is that proposals move across the sample space in larger steps; they are therefore less correlated and converge to the target distribution more rapidly.
  • Some variations on slice sampling also avoid random walks.[19]
  • Langevin MCMC and other methods that rely on the gradient (and possibly second derivative) of the log posterior avoid random walks by making proposals that are more likely to be in the direction of higher probability density.[20]


Usually it is not hard to construct a Markov chain with the desired properties. The more difficult problem is to determine how many steps are needed to converge to the stationary distribution within an acceptable error. A good chain will have rapid mixing: the stationary distribution is reached quickly starting from an arbitrary position.

Typically, MCMC sampling can only approximate the target distribution, as there is always some residual effect of the starting position. More sophisticated MCMC-based algorithms such as coupling from the past can produce exact samples, at the cost of additional computation and an unbounded (though finite in expectation) running time.

Many random walk Monte Carlo methods move around the equilibrium distribution in relatively small steps, with no tendency for the steps to proceed in the same direction. These methods are easy to implement and analyze, but unfortunately it can take a long time for the walker to explore all of the space. The walker will often double back and cover ground already covered.

See also[edit]


Further reading[edit]

External links[edit]


  1. ^ See Gill 2008.
  2. ^ See Robert & Casella 2004.
  3. ^ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (Second ed.). CRC Press. p. xix. ISBN 978-1-4398-1917-3. 
  4. ^ Gilks, W. R.; Wild, P. (1992-01-01). "Adaptive Rejection Sampling for Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 41 (2): 337–348. doi:10.2307/2347565. JSTOR 2347565. 
  5. ^ Gilks, W. R.; Best, N. G.; Tan, K. K. C. (1995-01-01). "Adaptive Rejection Metropolis Sampling within Gibbs Sampling". Journal of the Royal Statistical Society. Series C (Applied Statistics). 44 (4): 455–472. doi:10.2307/2986138. JSTOR 2986138. 
  6. ^ a b Martino, L.; Read, J.; Luengo, D. (2015-06-01). "Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling". IEEE Transactions on Signal Processing. 63 (12): 3123–3138. doi:10.1109/TSP.2015.2420537. ISSN 1053-587X. 
  7. ^ Liu, Jun S.; Liang, Faming; Wong, Wing Hung (2000-03-01). "The Multiple-Try Method and Local Optimization in Metropolis Sampling". Journal of the American Statistical Association. 95 (449): 121–134. doi:10.1080/01621459.2000.10473908. ISSN 0162-1459. 
  8. ^ Martino, Luca; Read, Jesse (2013-07-11). "On the flexibility of the design of multiple try Metropolis schemes". Computational Statistics. 28 (6): 2797–2823. doi:10.1007/s00180-013-0429-2. ISSN 0943-4062. 
  9. ^ See Green 1995.
  10. ^ Tahmasebi, Pejman; Javadpour, Farzam; Sahimi, Muhammad (August 2016). "Stochastic shale permeability matching: Three-dimensional characterization and modeling". International Journal of Coal Geology. 165: 231–242. doi:10.1016/j.coal.2016.08.024. 
  11. ^ Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. p. 626. Monographs on Statistics & Applied Probability 
  12. ^ Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. p. 575. Series: Probability and Applications 
  13. ^ Del Moral, Pierre; Miclo, Laurent (2000). Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering. (PDF). Lecture Notes in Mathematics. 1729. pp. 1–145. doi:10.1007/bfb0103798. 
  14. ^ "Sequential Monte Carlo samplers - P. Del Moral - A. Doucet - A. Jasra - 2006 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library". Retrieved 2015-06-11. 
  15. ^ Chen, S., Josef Dick, and Art B. Owen. "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces." The Annals of Statistics 39.2 (2011): 673-701.
  16. ^ Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007.
  17. ^ Papageorgiou, Anargyros, and J. F. Traub. "Beating Monte Carlo." Risk 9.6 (1996): 63-65.
  18. ^ Sobol, Ilya M. "On quasi-monte carlo integrations." Mathematics and Computers in Simulation 47.2 (1998): 103-112.
  19. ^ See Neal 2003.
  20. ^ See Stramer 1999.