Markov Chain Monte Carlo


Markov Chain Monte Carlo

Markov-Chain-Monte-Carlo-Verfahren (kurz MCMC-Verfahren; seltener auch Markov-Ketten-Monte-Carlo-Verfahren) sind eine Klasse von Algorithmen, die Stichproben aus Wahrscheinlichkeitsverteilungen ziehen. Dies geschieht auf der Basis der Konstruktion einer Markow-Kette, welche die erwünschte Verteilung als ihre stationäre Verteilung aufweist. Der Zustand der Kette nach einer großen Zahl von Schritten wird dann als Stichprobe der erwünschten Verteilung benutzt. Die Qualität der Stichprobe steigt mit zunehmender Zahl der Schritte.

MCMC-Verfahren erzeugen Systeme im kanonischen Zustand. Eine ausreichende, aber nicht nötige, Bedingung, dass ein MCMC-Verfahren den kanonischen Zustand als stationäre Verteilung aufweist, ist die Detailed Balance-Eigenschaft.

Üblicherweise gelingt es leicht, eine Markow-Kette mit den erwünschten Eigenschaften zu konstruieren. Das schwierigere Problem ist es, zu ermitteln, wie viele Schritte nötig sind, um Konvergenz zur stationären Verteilung mit akzeptablem Fehler zu erreichen bzw. den Algorithmus so zu gestalten, dass möglichst effektiv, unabhängige Systemzustände generiert werden. Eine gute Kette mit einer gut gewählten Anfangsverteilung wird schnell konvergieren, d.h. die stationäre Verteilung wird schnell erreicht. Bei typischer Anwendung von MCMC-Verfahren kann die Zielverteilung nur näherungsweise erreicht werden, da es immer einen gewissen Resteffekt der Anfangsverteilung gibt.

Häufige Anwendungen dieser Algorithmen findet sich bei der numerischen Berechnung mehrdimensionaler Integrale. Diese finden sich oft im Rahmen der Bayesianischen Statistik sowie rechnerischen Anwendungen in der Physik (beispielsweise der Statistischen Physik oder Pfadintegrale in der Quantenfeldtheorie) und der Biologie.

Algorithmen

Beispiele für Markov-Chain-Monte-Carlo-Verfahren sind:

  • Metropolisalgorithmus: Das lokale Verfahren erzeugt Zufallsbewegungen, die mit einer gewissen Wahrscheinlichkeit akzeptiert oder zurückgewiesen werden. Es ist einfach zu implementieren, hat jedoch den Nachteil einer hohen Autokorrelation der erzeugten Systemzustände.
  • Gibbs-Sampling (auch Wärmebadalgorithmus genannt): Das lokale Verfahren ist ein Sonderfall des Metropolis-Hastings-Algorithmus, bei der die Zustände entsprechend der lokalen Wahrscheinlichkeitsverteilung erzeugt werden.
  • Hybrid-Monte-Carlo-Algorithmus: Das Verfahren stellt eine Kombination aus Molekulardynamik und Zufallsbewegung her. Die Molekulardynamik wird benutzt, um effizient neue, unabhängige Zustände zu erzeugen, die mit einer gewissen Wahrscheinlichkeit akzeptiert oder zurückgewiesen werden.
  • Clusteralgorithmen: Hierbei handelt es sich um spezielle, nicht-lokale Verfahren, die die Autokorrelationzeiten und damit das so genannte Critical Slowing down, vermeiden. Sie wurden erstmal von Swendsen und Wang für das Potts-Modell eingeführt. Allerdings sind nur wenige Systeme bekannt,für welche das Verfahren implementiert werden konnte.
  • Over-Relaxation-Verfahren

Literatur

  • Jeff Gill: Bayesian methods: a social and behavioral sciences approach. Second Edition, Chapman and Hall/CRC, London 2008, ISBN 978-1-58488-562-7.
  • N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller und E. Teller: Equation of State Calculations by Fast Computing Machines. In: Journal of Chemical Physics. 21, 1953, S. 1087-1092 (doi:10.1063/1.1699114). 
  • W.K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. 57, 1970, S. 97-109. 
  • R.H. Swendsen, J.-S. Wang: Nonuniversal critical dynamics in Monte Carlo simulations. In: Phys. Rev. Lett.. 58, 1987, S. 86. 
  • S.L. Adler: Overrelaxation method for Monte Carlo evaluation of the partition function for multiquadratic actions. In: Phys. Rev. D. 23, 1988, S. 2901. 

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Markov chain Monte Carlo — 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… …   Wikipedia

  • Markov chain Monte Carlo — Les méthodes MCMC (pour Markov chain Monte Carlo) sont une classe de méthodes d échantillonnage à partir de distributions de probabilité. Ces méthodes se basent sur le parcours de chaînes de Markov qui ont pour lois stationnaires les… …   Wikipédia en Français

  • Markov chain — A simple two state Markov chain. A Markov chain, named for Andrey Markov, is a mathematical system that undergoes transitions from one state to another, between a finite or countable number of possible states. It is a random process characterized …   Wikipedia

  • Monte Carlo method — Not to be confused with Monte Carlo algorithm. Computational physics …   Wikipedia

  • Markov chain mixing time — In probability theory, the mixing time of a Markov chain is the time until the Markov chain is close to its steady state distribution. More precisely, a fundamental result about Markov chains is that a finite state irreducible aperiodic chain has …   Wikipedia

  • Monte Carlo molecular modeling — is the application of Monte Carlo methods to molecular problems. These problems can also be modeled by the molecular dynamics method. The difference is that this approach relies on statistical mechanics rather than molecular dynamics. Instead of… …   Wikipedia

  • Markov model — In probability theory, a Markov model is a stochastic model that assumes the Markov property. Generally, this assumption enables reasoning and computation with the model that would otherwise be intractable. Contents 1 Introduction 2 Markov chain… …   Wikipedia

  • Markov property — In probability theory and statistics, the term Markov property refers to the memoryless property of a stochastic process. It was named after the Russian mathematician Andrey Markov.[1] A stochastic process has the Markov property if the… …   Wikipedia

  • Markov network — A Markov network, or Markov random field, is a model of the (full) joint probability distribution of a set mathcal{X} of random variables having the Markov property. A Markov network is similar to a Bayesian network in its representation of… …   Wikipedia

  • Markov random field — A Markov random field, Markov network or undirected graphical model is a set of variables having a Markov property described by an undirected graph. A Markov random field is similar to a Bayesian network in its representation of dependencies. It… …   Wikipedia