imported>Ziv: (GR) File renamed: File:Posterior-Approximation mit dem Metropolis-Hastings-Algorithmus.gif → File:Mcmc-posterior-approximation.gif Criterion 1 (original uploader’s request) · Das ist die erste Datei, die ich auf Wikipedia hochlade, und ich habe nicht verstanden, dass das Hochladeformular den Dateinamen, und nicht die Bildbeschreibung haben will.

2026-01-27T15:19:00Z

(GR) File renamed: File:Posterior-Approximation mit dem Metropolis-Hastings-Algorithmus.gif → File:Mcmc-posterior-approximation.gif Criterion 1 (original uploader’s request) · Das ist die erste Datei, die ich auf Wikipedia hochlade, und ich habe nicht verstanden, dass das Hochladeformular den Dateinamen, und nicht die Bildbeschreibung haben will.

Neue Seite

'''Markow-Chain-Monte-Carlo-Verfahren''' (kurz '''''MCMC-Verfahren''';'' seltener auch ''Markow-Ketten-Monte-Carlo-Verfahren'') sind eine Klasse von [[Algorithmus|Algorithmen]], die zufällige 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.
[[Datei:Mcmc-posterior-approximation.gif|mini|Die Animation zeigt approximierte Bayessche Inferenz mit dem Metropolis-Hastings-Algorithmus. Aus 100 Beobachtungen einer Variable <math>X \sim p(X|Z)p(Z)</math> werden Informationen über die Verteilung der latenten Variable <math>Z</math> gewonnen. Die Likelihood <math>p(X|Z)</math>, sowie die Proposal Verteilung für neue Stichproben <math>Q(Z_{t+1}|Z_t)</math> als nächstes Kettenglied ist als Normalverteilung <math>\mathcal{N}(Z,1)</math> gegeben. Angenommen wird ein gleichverteilter Prior <math>\mathcal{U}[-1.5;1.5]</math>. Mit jedem akzeptierten Kettenglied nähert sich der approximierte Posterior der wahren Verteilung von <math>Z</math> an.]]

[[Datei:Metropolis algorithm convergence example.png|mini|Konvergenz des Metropolis-Hastings-Algorithmus; die blaue Verteilung soll durch die orange approximiert werden.]]

Üblicherweise gelingt es leicht, eine Markow-Kette mit den erwünschten Eigenschaften zu konstruieren. Das Schwierigere ist, zu ermitteln, wie viele Schritte nötig sind, um Konvergenz zur stationären Verteilung mit akzeptablem Fehler zu erreichen, also 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. Stichproben, welche mit MCMC-Algorithmen generiert werden, weisen typischerweise hohe [[Autokorrelation]]en auf. Daher wird der Fehler des Mittelwerteschätzers bei Verwendung des [[Standardfehler]]s unterschätzt.

== Anwendungsgebiete ==
Häufige Anwendungen dieser Algorithmen finden sich bei der numerischen Berechnung mehrdimensionaler Integrale. Diese finden sich z. B.
* im Rahmen der [[Bayessche Statistik|bayesschen Statistik]]<ref>{{Literatur |Autor=Sudipto Banerjee, Bradley P. Carlin, Alan E. Gelfand |Titel=Hierarchical Modeling and Analysis for Spatial Data |Auflage= |Verlag=Chapman and Hall/CRC |Datum=2014-09-12 |Sprache=en |ISBN=978-0-429-13717-4 |DOI=10.1201/b17115 |Online=https://www.taylorfrancis.com/books/9781439819180 |Abruf=2023-07-04}}</ref> (z. B. bei [[Approximate Bayesian Computation]])
* in [[Computersimulation]]en in der [[Statistische Physik|statistischen Physik]]: MCMC-Verfahren können z. B. zur Simulation von Systemen im [[Kanonisches Ensemble|kanonischen Ensemble]] herangezogen werden. Simulationen nahe einem [[Phasenübergang]] konvergieren i. d. R. langsamer und erfordern eine längere [[Equilibrierung]]. Eine hinreichende, aber nicht notwendige Bedingung, dass ein MCMC-Verfahren den kanonischen Zustand als stationäre Verteilung aufweist, ist die [[Detailed Balance|Detailed-Balance]]-Eigenschaft.
* oder zur Auswertung von [[Pfadintegral]]en in [[Quantenfeldtheorie]]n<ref>{{Literatur |Autor=Ankur Gupta, James B. Rawlings |Titel=Comparison of parameter estimation methods in stochastic chemical kinetic models: Examples in systems biology |Sammelwerk=AIChE Journal |Band=60 |Nummer=4 |Datum=2014-04 |Sprache=en |DOI=10.1002/aic.14409 |PMID=27429455 |Seiten=1253–1268}}</ref>.

== Beispiel ==
Angenommen, wir können eine [[diskrete Gleichverteilung]] auf <math> \{0,1\} </math> simulieren. Dies entspricht dem Wurf einer fairen Münze mit <math> P(\{1\})=P(\{0\})=0{,}5 </math>, wobei „1=Kopf“ und „0=Zahl“ sein soll. Nun wollen wir aber eine Verteilung auf <math> S=\{1,2,3 \} </math> simulieren mit <math> P_Z(\{1\})=0{,}2 </math> und <math> P_Z(\{2\})=P_Z(\{3\})=0{,}4 </math>. Dazu definieren wir eine Markow-Kette, bei der alle Übergangswahrscheinlichkeiten simuliert werden können (sprich 0,5, 0 oder 1 sind) und die die Verteilung <math> P_Z </math> als stationäre Verteilung hat. Folgendes Vorgehen bildet eine Markow-Kette, welche die Voraussetzungen erfüllt: Befindet man sich im Zustand 1, gehe nach 2. Befindet man sich im Zustand 2, wirf eine Münze. Zeigt sie Kopf, gehe zu 3, ansonsten verharre in der 2. Befindet man sich im Zustand 3, wirf eine Münze. Zeigt sie Kopf, gehe zu 1, ansonsten verharre in der 3. Diese Markow-Kette wird durch die folgende [[Übergangsmatrix]] beschrieben:
:<math>M = \begin{bmatrix}
0 & 1 & 0 \\
0 & 0{,}5 & 0{,}5 \\
0{,}5 & 0 & 0{,}5
\end{bmatrix}=((P(i|k))_{k,i})</math>.

Da alle Einträge der Matrix <math> M^t >0 </math> positiv sind ab <math>t\geq 3</math>, ist die Markow-Kette [[Irreduzible Markow-Kette|irreduzibel]] und [[Periodische Markow-Kette|aperiodisch]]. Daher [[Stationäre Verteilung#Konvergenz|konvergiert die Markow-Kette]] für jede beliebige Startverteilung <math> v_0 </math> gegen die stationäre Verteilung <math> \pi=P_Z </math>

Für die Simulation starten wir nun im Zustand 1.
In der Tabelle findet sich jeweils der Simulationsschritt in der ersten Spalte, dann die exakte [[Aufenthaltswahrscheinlichkeit]] für den Zustand 1 in der 2. Spalte: <math>P(X_k=1)=\sum_{i=1}^3 P(1|i)P(X_{k-1}=i)</math>

Diese konvergiert nach Voraussetzung gegen 0,2. In der letzten Spalte steht die relative Häufigkeit des Zustandes 1, gemittelt über eintausend Simulationen. Diese nähert sich nach mehreren Simulationsschritten der stationären Verteilung an. Lässt man also die Simulation lange laufen, so ist die so erhaltene Stichprobe <math> P_Z </math> verteilt.

{| class="wikitable" style="text-align:right"
|-
! Schritte <math> k </math>
! <math> P(X_k=1) </math>
! Relative Häufigkeit der 1<br />in Tausend Simulationen
|-
| 0 || 1 || 1
|-
| 1 || 0 || 0
|-
| 2 || 0 || 0
|-
| 3 || 0,25 || 0,228
|-
| 4 || 0,25 || 0,271
|-
| 5 || 0,1875 || 0,173
|-
| 6 || 0,1875 || 0,176
|-
| 7 || 0,2031 || 0,236
|-
| 8 || 0,2031 || 0,180
|-
| 9 || 0,1992 || 0,202
|-
| 10 || 0,1992 || 0,171
|-
| 11 || 0,2002 || 0,205
|-
| 12 || 0,2002 || 0,198
|-
| 13 || 0,2000 || 0,190
|-
| 14 || 0,2000 || 0,206
|}

Normiert man die Summe der Einträge des [[Linkseigenvektor|linksseitigen Eigenvektors]] von <math>M</math> zum Eigenwert 1, so erhält man die Wahrscheinlichkeiten der Zustände der stationären Wahrscheinlichkeitsverteilung der Markow-Kette: hier 0,2, 0,4, 0,4.

== Algorithmen (Auswahl) ==
{{Siehe auch|Monte-Carlo-Algorithmus|Monte-Carlo-Simulation}}
Beispiele für MCMC-Verfahren sind:
* ''[[Metropolis-Algorithmus]]'': Das lokale Verfahren erzeugt [[Zufallsbewegung]]en, 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]]: Das lokale Verfahren ist ein Sonderfall des Metropolis-Hastings-Algorithmus, bei dem die Zustände entsprechend der lokalen [[Wahrscheinlichkeitsverteilung]] erzeugt werden.
* ''Wärmebadalgorithmus''
* ''[[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'', bei [[Phasenübergang|Phasenübergängen]], reduzieren. Ein solcher Algorithmus wurde erstmals 1987 von [[Robert Swendsen|R. Swendsen]] und [[Jian-Sheng Wang|J.-S.Wang]] für ein [[Potts-Modell]] benutzt, siehe [[Swendsen-Wang-Algorithmus]]. Eine populäre Variante dieser Clustermethode ist der 1989 eingeführte [[Wolff-Algorithmus]].
* ''Over-Relaxation-Verfahren''

== Siehe auch ==
* [[Bayessches Netz]]

== Literatur ==
{{Siehe auch|Monte-Carlo-Simulation|Monte-Carlo-Algorithmus}}

=== Fachliteratur (Originalarbeiten) ===

* {{Literatur
|Autor=N. Metropolis, A. Rosenbluth, [[Marshall Rosenbluth|M. Rosenbluth]], A. Teller und [[Edward Teller|E. Teller]]
|Titel=Equation of State Calculations by Fast Computing Machines
|Sammelwerk=Journal of Chemical Physics
|Band=21
|Datum=1953
|Seiten=1087–1092
|DOI=10.1063/1.1699114|Sprache=en}}
* {{Literatur |Autor=W. K. Hastings |Titel=Monte Carlo sampling methods using Markov chains and their applications |Sammelwerk=Biometrika |Band=57 |Nummer=1 |Datum=1970-04-01 |Sprache=en |DOI=10.1093/biomet/57.1.97 |Seiten=97–109}}
* {{Literatur |Autor=Robert H. Swendsen, Jian-Sheng Wang |Titel=Nonuniversal critical dynamics in Monte Carlo simulations |Sammelwerk=Physical Review Letters |Band=58 |Nummer=2 |Datum=1987-01-12 |Sprache=en |DOI=10.1103/PhysRevLett.58.86 |Seiten=86–88}}
* {{Literatur |Autor=Stephen L. Adler |Titel=Over-relaxation method for the Monte Carlo evaluation of the partition function for multiquadratic actions |Sammelwerk=Physical Review D |Band=23 |Nummer=12 |Datum=1981-06-15 |Sprache=en |DOI=10.1103/PhysRevD.23.2901 |Seiten=2901–2904}}

=== Fachbücher ===
* {{Literatur |Titel=Handbook of Markov Chain Monte Carlo |Hrsg=Steve Brooks, Andrew Gelman, Galin Jones, Xiao-Li Meng |Auflage= |Verlag=Chapman and Hall/CRC |Datum=2011 |Sprache=en |ISBN=978-0-429-13850-8 |DOI=10.1201/b10905 |Online=http://www.mcmchandbook.net |Abruf=2023-07-04}}
* {{Literatur |Autor=Jeff Gill |Titel=Bayesian Methods |Auflage=3. |Verlag=Chapman and Hall/CRC |Datum=2014 |Sprache=en |ISBN=978-1-4398-6249-0 |DOI=10.1201/b17888}}

== Einzelnachweise ==
<references />

[[Kategorie:Algorithmus]]
[[Kategorie:Stochastik]]

MCMC-Verfahren - Versionsgeschichte