MCMC-Verfahren

Häufige Anwendungen dieser Algorithmen finden sich bei der numerischen Berechnung mehrdimensionaler Integrale. Diese finden sich z. B.

• im Rahmen der bayesschen Statistik[1] (z. B. bei Approximate Bayesian Computation)
• in Computersimulationen in der statistischen Physik: MCMC-Verfahren können z. B. zur Simulation von Systemen im 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-Eigenschaft.
• oder zur Auswertung von Pfadintegralen in Quantenfeldtheorien[2].

Angenommen, wir können eine diskrete Gleichverteilung auf ${\displaystyle \{0,1\}}$ simulieren. Dies entspricht dem Wurf einer fairen Münze mit ${\displaystyle P(\{1\})=P(\{0\})=0{,}5}$, wobei „1=Kopf“ und „0=Zahl“ sein soll. Nun wollen wir aber eine Verteilung auf ${\displaystyle S=\{1,2,3\}}$ simulieren mit ${\displaystyle P_{Z}(\{1\})=0{,}2}$ und ${\displaystyle P_{Z}(\{2\})=P_{Z}(\{3\})=0{,}4}$. 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 ${\displaystyle P_{Z}}$ 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:

${\displaystyle M={\begin{bmatrix}0&1&0\\0&0{,}5&0{,}5\\0{,}5&0&0{,}5\end{bmatrix}}=((P(i|k))_{k,i})}$.

Da alle Einträge der Matrix ${\displaystyle M^{t}>0}$ positiv sind ab ${\displaystyle t\geq 3}$, ist die Markow-Kette irreduzibel und aperiodisch. Daher konvergiert die Markow-Kette für jede beliebige Startverteilung ${\displaystyle v_{0}}$ gegen die stationäre Verteilung ${\displaystyle \pi =P_{Z}}$

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: ${\displaystyle P(X_{k}=1)=\sum _{i=1}^{3}P(1|i)P(X_{k-1}=i)}$

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 ${\displaystyle P_{Z}}$ verteilt.

Schritte ${\displaystyle k}$	${\displaystyle P(X_{k}=1)}$	Relative Häufigkeit der 1 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 linksseitigen Eigenvektors von ${\displaystyle M}$ 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.

Beispiele für MCMC-Verfahren sind:

• Metropolis-Algorithmus: 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: 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übergängen, reduzieren. Ein solcher Algorithmus wurde erstmals 1987 von R. Swendsen und 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

• Bayessches Netz

1. Sudipto Banerjee, Bradley P. Carlin, Alan E. Gelfand: Hierarchical Modeling and Analysis for Spatial Data. Chapman and Hall/CRC, 2014, ISBN 978-0-429-13717-4, doi:10.1201/b17115 (englisch, taylorfrancis.com [abgerufen am 4. Juli 2023]).
2. Ankur Gupta, James B. Rawlings: Comparison of parameter estimation methods in stochastic chemical kinetic models: Examples in systems biology. In: AIChE Journal. Band 60, Nr. 4, April 2014, S. 1253–1268, doi:10.1002/aic.14409, PMID 27429455 (englisch).