Share on Facebook Share on Twitter Email
Answers.com

Markov chain Monte Carlo

 
Statistics Dictionary: Markov chain Monte Carlo
Home > Library > Science > Statistics Dictionary

Variant: MCMC methods

Methods, making heavy use of computers, that are very useful in the analysis of large arrays of correlated observations, such as satellite images of the Earth. Suppose we wish to calculate θ, the expected value of a function h of r correlated random variables. Let X be the r×1 vector of random variables. A standard Monte Carlo method would generate a sequence of numerical values, X1, X2,..., Xn, from which θ could be estimated by θ̂, given by




.
However, it can be difficult to generate a vector Xj when the joint distribution of the r variables involves a complex correlation structure — for example, when the variables refer to the values displayed in an array of neighbouring pixels in a satellite image of the Earth's surface.

Let Xjk be the kth random variable in Xj. MCMC methods aim to generate r Markov chains, where the kth chain is the sequence of values x1k, x2k,.... An arbitrary set of values is chosen for the first chain, subsequent chains being generated from their predecessors by Monte Carlo methods. In calculating θ̂ it is necessary to ignore the early chains in the sequence, since these will be affected by the initial choice of values. This is called the burn-in period.

A popular method for obtaining the required Markov chains, which need to be stationary, is the Metropolis–Hastings algorithm. Let the stationary probability for the random variable Xj being in state m be pm and let Q be a known matrix with non-negative elements. The transition probability matrix governing the sequence X1, X2,...is defined by



,
where ajk is given by



,
and each cj is chosen so that Σkpjk=1.

The most used version of the Metropolis–Hastings algorithm incorporates the Gibbs sampler. The aim is to generate a random vector X with elements satisfying a specified relationship. Denote the initial values in X by x1(0), x2(0),.... A single element of the vector (element j, say) is chosen at random, and a potential new value, x, is generated by random selection from the conditional distribution of Xj given the values of the remaining variables, {Xk, k≠j}. If the new value is in accord with the specified relationship, then it replaces the previous value so that xj(1)=x; otherwise the previous value is retained: xj(1)=xj(0). This process is repeated until approximate equilibrium has been reached.

The procedure was originally proposed in the context of statistical mechanics by Metropolis and others in 1953, and was introduced into statistics in 1970 by Hastings.


Search unanswered questions...

Enter a question here...
Search: All sources Community Q&A Reference topics

Wikipedia: Markov chain Monte Carlo
Top
Home > Library > Miscellaneous > Wikipedia
"MCMC" redirects here. For the organization, see Malaysian Communications and Multimedia Commission.

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

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—described further under Markov chain mixing time.

Typical use of 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.

The most common application of these algorithms is numerically calculating multi-dimensional integrals. In these methods, an ensemble of "walkers" moves around randomly. At each point where the 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 reasonably high contribution to the integral to move into next. Random walk 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 are correlated. A Markov chain is constructed in such a way as to have the integrand as its equilibrium distribution. Surprisingly, this is often easy to do.

Multi-dimensional integrals often arise in Bayesian statistics, computational physics, computational biology and computational linguistics, so Markov chain Monte Carlo methods are widely used in those fields. For example, see Gill[1] and Robert & Casella.[2]

Contents

Random walk algorithms

Many Markov chain 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 analyse, 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. Here are some random walk MCMC methods:

  • Metropolis–Hastings algorithm: Generates a random walk using a proposal density and a method for rejecting proposed moves.
  • Gibbs sampling: Requires that all the conditional distributions of the target distribution can be sampled exactly. Popular partly because when this is so, the method does not require any `tuning'.
  • Slice sampling: Depends on the principle that one can sample from a distribution by sampling uniformly from the region under the plot of its density function. This method alternates uniform sampling in the vertical direction with uniform sampling from the horizontal `slice' defined by the current vertical position.
  • Multiple-try Metropolis: A variation of the Metropolis–Hastings algorithm that allows multiple trials at each point. This allows the algorithm to generally take larger steps at each iteration, which helps combat problems intrinsic to large dimensional problems.

Avoiding random walks

More sophisticated algorithms use some method of preventing the walker from doubling back. These algorithms may be harder to implement, but may exhibit faster convergence (i.e. fewer steps for an accurate result).

  • Successive over-relaxation: A Monte Carlo version of this technique can be seen as a variation on Gibbs sampling; it sometimes avoids random walks.
  • Hybrid Monte Carlo (HMC) (Would be better called `Hamiltonian Monte Carlo'): Tries to avoid random walk behaviour by introducing an auxiliary momentum vector and implementing Hamiltonian dynamics where the potential function is the target density. The momentum samples are discarded after sampling. The end result of Hybrid MCMC is that proposals move across the sample space in larger steps and are therefore less correlated and converge to the target distribution more rapidly.
  • Some variations on slice sampling also avoid random walks.[3]

Changing dimension

The Reversible Jump method is a variant of Metropolis-Hastings that allows proposals that change the dimensionality of the space. This method was proposed in 1995 by Peter Green of Bristol University[4]. Markov chain Monte Carlo methods that change dimensionality have also 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).

See also

Notes

  1. ^ Jeff Gill (2008). Bayesian methods: a social and behavioral sciences approach (Second Edition ed.). London: Chapman and Hall/CRC. ISBN 1-58488-562-9. http://worldcat.org/isbn/1-58488-562-9. 
  2. ^ Christian P Robert & Casella G (2004). Monte Carlo statistical methods (Second Edition ed.). New York: Springer. ISBN 0-387-21239-6. http://worldcat.org/isbn/0-387-21239-6. 
  3. ^ Radford M. Neal, "Slice Sampling". The Annals of Statistics, 31(3):705-767, 2003.
  4. ^ P. J. Green. Reversible jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika, 82(4):711–732, 1995

References

  • Christophe Andrieu et al., "An Introduction to MCMC for Machine Learning", 2003
  • Bernd A. Berg. "Markov Chain Monte Carlo Simulations and Their Statistical Analysis". Singapore, World Scientific 2004.
  • George Casella and Edward I. George. "Explaining the Gibbs sampler". The American Statistician, 46:167-174, 1992. (Basic summary and many references.)
  • A.E. Gelfand and A.F.M. Smith. "Sampling-Based Approaches to Calculating Marginal Densities". J. American Statistical Association, 85:398-409, 1990.
  • Andrew Gelman, John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis. London: Chapman and Hall. First edition, 1995. (See Chapter 11.)
  • S. Geman and D. Geman. "Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images". IEEE Transactions on Pattern Analysis and Machine Intelligence, 6:721-741, 1984.
  • Radford M. Neal, Probabilistic Inference Using Markov Chain Monte Carlo Methods, 1993.
  • Gilks W.R., Richardson S. and Spiegelhalter D.J. "Markov Chain Monte Carlo in Practice". Chapman & Hall/CRC, 1996.
  • C.P. Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
  • R. Y. Rubinstein and D. P. Kroese. Simulation and the Monte Carlo Method (second edition). New York: John Wiley & Sons, 2007. ISBN 978-0470177945
  • R. L. Smith "Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions", Operations Research, Vol. 32, pp. 1296–1308, 1984.
  • Asmussen and Glynn "Stochastic Simulation: Algorithms and Analysis", Springer. Series: Stochastic Modelling and Applied Probability, Vol. 57, 2007.
  • P. Atzberger, "An Introduction to Monte-Carlo Methods." [1].

External links


This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

 
 

 

Copyrights:

Statistics Dictionary. A Dictionary of Statistics. Second edition revised. Copyright © Oxford University Press, 2008. All rights reserved.  Read more
Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Markov chain Monte Carlo".  Read more