This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0000236801 Reproduction Date:
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.
Random walk Monte Carlo methods make up a large subclass of MCMC methods.
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:
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.^{[5]} 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,^{[6]}^{[7]} also called Sequential Monte Carlo or particle filter methods in Bayesian inference and signal processing communities.^{[8]} Interacting MCMC methods can also be interpreted as a mutation-selection genetic particle algorithm with MCMC mutations.
Markov Chain quasi-Monte Carlo (MCQMC)^{[9]}^{[10]} The advantage of low-discrepancy sequences in lieu of random numbers for simple independent Monte Carlo sampling is well-known.^{[11]} This procedure, known as Quasi-Monte Carlo method (QMC),^{[12]} yields an integration error that decays at a superior rate to that obtained by IID sampling, by the Koksma-Hlawka inequality. Empirically it allows to reduce both estimation error and convergence time by an order of magnitude.
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:
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.
Monographs on Statistics & Applied Probability
Series: Probability and Applications
Statistics, Probability interpretations, Bayesian inference, Bayesian probability, Hyperparameter
Probability theory, Regression analysis, Mathematics, Observational study, Calculus
Probability distribution, Statistics, Adaptive rejection sampling, Bayesian statistics, Random walk
Statistics, Science, Regression analysis, Bayes' theorem, Bayes' rule
Computer science, Statistics, Discrete mathematics, Mathematical analysis, Interpolation
Markov chain Monte Carlo, Queueing theory, Google, Statistics, Ergodic theory
Population genetics, Bayesian inference, Markov chain Monte Carlo, Evolution, Genetic recombination
University of Warwick, University of Cambridge, Jesus College, Oxford, Guy Medal, University of Nottingham
Markov chain Monte Carlo, Rejection sampling, Computational statistics, Normal distribution, Algorithm
Statistics, Markov chain Monte Carlo, Marginal distribution, Parameter, Statistical inference