Universität Bielefeld

Fakultät für Mathematik

MCMC-Methoden
Masterarbeit im Rahmen des Seminars
,,Elementare Wahrscheinlichkeitsrechnung"
Sommersemester 2007

vorgelegt von:
Thomas Plehn

1

Inhaltsverzeichnis

1 Grundlagen zu Markov-Ketten 4
1.1 Definition 4
1.2Irreduzibilität und Aperiodizität 9
1.3 Stationäre Verteilungen und Reversibilität 11
1.3.1 Existenz der stationären Verteilung 11
1.3.2 Reversibilität einer Verteilung 18
1.4 Konvergenzsatz 19
1.4.1 Konvergenz gegen die stationäre Verteilung 19
1.4.2 Eindeutigkeit der stationären Verteilung 21
2 Metropolis-Hastings Algorithmus 23
2.1 Allgemeine Beschreibung des Metropolis-Hastings Algorithmus 23
2.2 Implementierung des Metropolis-Algorithmus im Beispiel der Exponentialverteilung 26
2.3 Fehler-Abschätzung im Beispiel der Exponetialverteilung 28
3 Gibbs-Sampler 30
3.1 Allgemeine Beschreibung des Gibbs-Samplers 30
3.2 Implementierung des Gibbs-Sampler Beispiels 33
3.3 Verallgemeinerung auf q-Färbungen 34
4 Approximate counting 36
4.1 Problemstellung 36
4.2 Existenz-Theorem 37
4.3 Beweis: erster Teil 38
4.4 Beweis: zweiter Teil 41
4.5 Implementierung 45
5 Literatur 49
6 Quelltexte 50
6.1 Metropolis-Hastings Algorithmus 50

2

6.2 Gibbs-Sampler 51

6.3 Approximate-Counting Algorithmus 52

3

1 Grundlagen zu Markov-Ketten

1.1 Definition

Wir beginnen mit einem sehr einfachen Beispiel: Denken wir an einen zufälligen Läufer in einer sehr kleinen Stadt, die nur aus vier Straßen besteht. Dabei werden die vier Straßenecken wie in der untenstehenden Abbildung mit v1, v2, v3 und v4 bezeichnet. Zum Zeitpunkt 0 steht der zufällige Läufer in der Ecke v1. Zum Zeitpunkt 1 wirft er eine faire Münze und entscheidet je nach Ausfall, ob er weiter nach v2 oder v4 geht. Zum Zeitpunkt 2 wirft er wieder eine faire Münze, um zu entscheiden, zu welcher benachbarten Ecke er gehen soll. Dabei verwendet er die Entscheidungsregel, wenn die Münze Kopf zeigt, einen Schritt im Uhrzeigersinn zu gehen und andernfalls, wenn die Münze Zahl zeigt, einen Schritt gegen den Uhrzeigersinn zu gehen. Diese Prozedur wird fortgeführt für die Zeiten 3, 4, usw.

[Abbildung]

Für jedes n bezeichnet Xn den Index der Straßenecke an der sich der Läufer zur Zeit n befindet. Deswegen ist (X0, X1, ...) ein Zufallsprozess der Werte aus {v1,v2,v3,v4} annimmt. Weil der Läufer zur Zeit 0 in v1 startet, ergibt sich:

P (X0 = v1) = 1

Danach bewegt er sich nach v2 oder v4 mit jeweils der Wahrscheinlichkeit 1/2, so dass:

P (X1 = v2) = 2

4