Product Design, Manufacturing & Innovation Resources
Home » Markov Chain Monte Carlo (MCMC)

Markov Chain Monte Carlo (MCMC)

1953
  • Nicholas Metropolis
  • Arianna W. Rosenbluth
  • Marshall N. Rosenbluth
  • Augusta H. Teller
  • Edward Teller
  • W. Keith Hastings
Researcher analyzing Markov Chain Monte Carlo simulations in a statistical analysis office.

(generated image for illustration only)

Markov Chain Monte Carlo (MCMC) methods are a class of algorithms for sampling from a probability distribution. A Markov chain is constructed that has the desired distribution as its equilibrium or stationary distribution. The state of the chain after a large number of steps is then used as a sample from the desired distribution, enabling computation of integrals and expectations.

MCMC methods are essential when direct sampling from a complex, high-dimensional probability distribution \(P(x)\) is intractable. Instead of generating independent samples, MCMC generates a sequence of correlated samples that form a Markov chain. A Markov chain is a stochastic process where the probability of transitioning to the next state depends only on the current state, not on the sequence of events that preceded it. The key is to design the transition probabilities of the chain such that its stationary distribution is the target distribution \(P(x)\).

The process starts at an arbitrary state \(x_0\). At each step \(t\), a new state \(x_{t+1}\) is generated based on the current state \(x_t\) using a specific algorithm (like Metropolis-Hastings). After an initial “burn-in” period, during which the chain converges from its starting point to the high-probability regions of the target distribution, the subsequent states \(x_t, x_{t+1}, …\) can be considered as (correlated) samples from \(P(x)\). These samples can then be used to estimate expectations of functions \(f(x)\) with respect to \(P(x)\) by averaging \(f(x_t)\) over the samples. This is particularly useful in Bayesian inference, where \(P(x)\) is a posterior distribution of model parameters, and direct calculation is often impossible due to a complex denominator (the evidence or marginal likelihood).

Moreover: MCMC differs from the basic Monte Carlo method in how it generates samples to estimate a desired distribution or integral. While Monte Carlo methods rely on drawing independent and identically distributed random samples directly from a target distribution or a proposal distribution, MCMC generates samples through a correlated sequence (a Markov chain) where each sample depends on the previous one. This dependency allows MCMC to efficiently explore complex, high-dimensional distributions that are difficult to sample from directly, by constructing a chain that converges to the target distribution over time. In contrast, traditional Monte Carlo methods may struggle with such problems due to inefficiencies in sampling or requiring explicit knowledge of the distribution’s form. Thus, MCMC extends Monte Carlo by harnessing dependence between samples to facilitate sampling in challenging statistical and computational settings.

UNESCO Nomenclature: 1209
– Statistics

Type

Software/Algorithm

Disruption

Incremental

Usage

Widespread Use

Precursors

  • theory of Markov chains (Andrey Markov)
  • foundations of Bayesian statistics (Thomas Bayes, Pierre-Simon Laplace)
  • original Monte Carlo method (Ulam, Von Neumann)
  • Ergodic theory

Applications

  • bayesian statistics for parameter estimation
  • computational biology for phylogenetic tree inference
  • machine learning for training probabilistic models
  • computational physics for simulating molecular systems
  • econometrics for modeling complex financial data

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: MCMC, Markov chain, Bayesian inference, statistics, sampling, stationary distribution, Metropolis-Hastings, Gibbs sampling, computational statistics, posterior distribution.

Historical Context

Markov Chain Monte Carlo (MCMC)

1943
1950
1950
1953
1960
1960
1967
1940
1950
1950
1952
1956
1960
1967
1967

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <