Propp-Wilson-Algorithmus

Der Propp-Wilson-Algorithmus ist ein Algorithmus zur Simulation von Wahrscheinlichkeitsmaßen. Der Algorithmus wurde 1996 von James Gary Propp und David Bruce Wilson veröffentlicht. Mithilfe einer Kopplung in die Vergangenheit ermittelt der Propp-Wilson-Algorithmus ein exaktes Simulationsverfahren für ein Wahrscheinlichkeitsmaß. Der Algorithmus simuliert iterativ vorangehende Zustände samt der Zustandsübergänge anstatt die zukünftige Entwicklung.

Vorbereitung

Sei ${\displaystyle E}$ eine endliche Menge und ${\displaystyle \pi }$ ein Wahrscheinlichkeitsmaß auf ${\displaystyle E}$. Gesucht wird eine perfekte Simulation von ${\displaystyle \pi }$. Dafür bestimme eine Zufallsvariable ${\displaystyle X}$ mit Verteilung ${\displaystyle \pi }$ und ein exaktes Simulationsverfahren für ${\displaystyle X}$. Zunächst muss eine irreduzible und aperiodische Markow-Kette mit Übergangsmatrix ${\displaystyle P=(p_{ij})_{i,j\in E}}$ und invarianter Verteilung ${\displaystyle \pi }$ konstruiert werden, die ${\displaystyle X}$ nachbildet.

Für den Algorithmus wird eine Übergangsfunktion ${\displaystyle \varphi :E\times [0,1]\to E}$ für die Übergangsmatrix der Markow-Kette benötigt. Die Übergangsfunktion erfülle, dass für alle ${\displaystyle i,j\in E}$ sofern eine Zufallsvariable ${\displaystyle U\sim \mathrm {Uni} _{[0,1]}}$ auf dem Einheitsintervall gleichverteilt ${\displaystyle \mathbb {P} (\varphi (i,U))=p_{ij}}$ gelte. Diese Übergangsfunktion definiert eine Kopplung zwischen den Zustandsübergängen.

Ablauf

Sei ${\displaystyle 0=N_{0},N_{1},N_{2},\ldots }$ eine streng wachsende Folge in ${\displaystyle \mathbb {N} _{0}}$.

 FUNKTION Propp-Wilson
    1. Setze m:=1
    2. Simuliere u.i.v ${\displaystyle U_{-N_{m}},\ldots ,U_{-N_{m-1}}-1\sim \mathrm {Uni} _{[0,1]}}$ und bestimme die zufällige Menge ${\displaystyle M_{m}=\varphi (\cdot ,U_{1})\circ \ldots \circ \varphi (\cdot ,U_{-N_{m}})(E)}$
    3. WENN ${\displaystyle M_{m}=\{s\}}$ einelementig, DANN setze ${\displaystyle X:=s}$ und HALT, SONST GEHE ZU 4.
    4. Erhöhe m um 1 und GEHE ZU 2.

Für eine andere Formulierung siehe (Klenke, 2013).

Eigenschaften

Satz Die Wahrscheinlichkeit, dass der Algorithmus terminiert, ist 0 oder 1. Wenn er terminiert, dann gilt ${\displaystyle \mathbb {P} (X=i)=\pi _{i}}$ für alle ${\displaystyle i\in E}$.

Beweisskizze Für den ersten Teil genügt es anzunehmen, dass der Algorithmus mit Wahrscheinlichkeit ${\displaystyle p>0}$ terminiert und zu beobachten, dass somit ein Zeitpunkt ${\displaystyle {\bar {m}}\in \mathbb {N} }$ existiert, wofür der Algorithmus mit Wahrscheinlichkeit ${\textstyle {\frac {p}{2}}}$ terminiert. Für den letzten Teil wird eine angemessene Zufallsvariable mit Verteilung ${\displaystyle \pi }$ konstruiert.

Anmerkungen

Der Propp-Wilson-Algorithmus ermöglicht im Vergleich zu MCMC-Verfahren eine perfekte Simulation, die auch bestimmt endet, sofern sie endet. Die Simulation ist insofern perfekt, als dass die gesamte Verteilung simuliert wird und nicht nur einzelne Pfade. Der Propp-Wilson-Algorithmus benötigt jedoch erheblichen Speicherplatz und wendet viele Rechenoperationen auf. In Fällen, wo das zugrundeliegende Modell mehr Struktur aufweist (z. B. das Ising-Modell), ist der Einsatz des Propp-Wilson-Algorithmus sinnvoll.

Es lässt sich stets eine triviale Übergangsfunktion ${\displaystyle \varphi _{0}}$ konstruieren, sodass ${\displaystyle \mathbb {P} (\varphi _{0}(i,U)=j,\varphi _{0}(i^{\prime },U)=j^{\prime })=\mathbb {P} (\varphi _{0}(i,U)=j)\times \mathbb {P} (\varphi _{0}(i^{\prime },U)=j^{\prime })}$ und ${\displaystyle \varphi _{0}(i_{1},U),\varphi _{0}(i_{2},U),\ldots }$ unabhängig sind, wenn ${\displaystyle i_{1},i_{2},\ldots }$ verschieden sind. In der Praxis ist es jedoch unumgänglich die optimale Übergangsfunktion auszuwählen.

Für den Algorithmus wird rückwärts in der Zeit iteriert. Eine Vorwärtsiteration würde tatsächlich nicht garantieren, dass die invariante Verteilung korrekt genähert wird. Als Gegenbeispiel betrachte man eine zweielementige Menge und kreiere eine günstige Übergangsmatrix.

Literatur

• Michael Scheutzow: Stochastische Modelle. Vorlesungsskript. Berlin Februar 2016, 2.11 Perfekte Simulation: der Propp-Wilson-Algorithmus (tu-berlin.de [PDF; 795 kB; abgerufen am 2. Mai 2026]). 
• Wolfgang König: Stochastische Algorithmen. Vorlesungsskript. Köln 2003 (wias-berlin.de [PDF; 509 kB; abgerufen am 2. Mai 2026]). 

Weblinks

• Perfectly Random Sampling with Markov Chains (archiviert) – von David Bruce Wilson erstellte Übersichtsseite zur perfekten Simulation von Markow-Ketten
• Dead Leaves Simulation (archiviert) – Erklärungsseite von Wilfrid S. Kendall

Einzelnachweise

1. ↑ Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen (= Springer-Lehrbuch). Springer Berlin Heidelberg, Berlin, Heidelberg 2012, ISBN 978-3-540-89140-6, S. 226 ff. 
2. ↑ James Gary Propp, David Bruce Wilson: Exact sampling with coupled Markov chains and applications to statistical mechanics. In: Random Structures and Algorithms. Band 9, Nr. 1-2, August 1996, ISSN 1042-9832, S. 223–252, doi:10.1002/(SICI)1098-2418(199608/09)9:1/2<223::AID-RSA14>3.0.CO;2-O (wiley.com [abgerufen am 2. Mai 2026]). 
3. 1 2 3 Achim Klenke: Wahrscheinlichkeitstheorie (= Masterclass). 3. Aufl. 2013. Springer Berlin Heidelberg, Berlin, Heidelberg 2013, ISBN 978-3-642-36017-6, S. 412–413. 
4. ↑ James Allen Fill: An interruptible algorithm for perfect sampling via Markov chains. In: The Annals of Applied Probability. Band 8, Nr. 1, 1. Februar 1998, ISSN 1050-5164, doi:10.1214/aoap/1027961037 (projecteuclid.org [abgerufen am 2. Juni 2026]).