Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung
©2007
Examensarbeit
54 Seiten
Zusammenfassung
In seiner Arbeit beschäftigt sich der Autor mit der ‘Markov Chain Monte Carlo‘, auch abgekürzt als MCMC. Dabei handelt es sich um eine Monte Carlo Methode. Allen Monte Carlo Methoden ist gemein, dass sie von einer mehr oder minder komplizierten Verteilung zufällige Szenarien erzeugen. Diese Szenarien werden dann genutzt um Aussagen über Erwartungswerte oder andere Kennzahlen der Verteilung zu treffen. Diese Aussagen sind natürlich nur zu gebrauchen, wenn man sehr viele zufällig erzeugte Szenarien auswertet. Die Methode kommt also immer dann zum Einsatz, wenn es nicht möglich ist, aus der Verteilung der Szenarien direkt Rückschlüsse auf die statistischen Kennzahlen der Verteilung zu ziehen, weder auf analytischem Wege, noch durch numerische Integration (bei sehr vielen Dimensionen steigt der Aufwand rapide an).
Markov Chain Monte Carlo ist nun eine spezielle Monte Carlo Methode unter Zuhilfenahme von Markovketten. Diese kommt immer dann zum Einsatz, wenn es nicht möglich ist, von einer Verteilung auf einfache Weise Szenarien zu erzeugen. Eine Markovkette fängt bei einem Zustand an und geht von einem bestimmten Zustand mit einer bestimmten Wahrscheinlichkeit zu einem anderen Zustand über. Diese Übergangswahrscheinlichkeiten stehen in einer Übergangsmatrix. Der Knackpunkt ist nun, dass diese Form der Zustandsgenerierung oft einfacher zu implementieren ist, als direkt auf eine Verteilung zurückzugreifen. In der Arbeit gibt es mehrere konkrete Beispiele für den Einsatz solcher Methoden. Quelltexte der Implementierungen sind beigefügt.
Markov Chain Monte Carlo ist nun eine spezielle Monte Carlo Methode unter Zuhilfenahme von Markovketten. Diese kommt immer dann zum Einsatz, wenn es nicht möglich ist, von einer Verteilung auf einfache Weise Szenarien zu erzeugen. Eine Markovkette fängt bei einem Zustand an und geht von einem bestimmten Zustand mit einer bestimmten Wahrscheinlichkeit zu einem anderen Zustand über. Diese Übergangswahrscheinlichkeiten stehen in einer Übergangsmatrix. Der Knackpunkt ist nun, dass diese Form der Zustandsgenerierung oft einfacher zu implementieren ist, als direkt auf eine Verteilung zurückzugreifen. In der Arbeit gibt es mehrere konkrete Beispiele für den Einsatz solcher Methoden. Quelltexte der Implementierungen sind beigefügt.
Leseprobe
Inhaltsverzeichnis
und
P (X
1
= v
4
) =
1
2
Die Verteilung von X
n
f¨
ur n
2 zu berechnen, setzt ein wenig mehr Nachdenken
voraus. An dieser Stelle ist es sinnvoll, sich auf bedingte Wahrscheinlichkeiten zu beziehen.
Nehmen wir an, dass der L¨
aufer zur Zeit n an der Ecke v
2
steht. Dann erhalten wir die
bedingten Wahrscheinlichkeiten
P (X
n
+1
= v
1
|X
n
= v
2
) =
1
2
und
P (X
n
+1
= v
3
|X
n
= v
2
) =
1
2
wegen des M¨
unzwurf-Mechanismus zur Entscheidung ¨
uber den n¨
achsten Schritt. Tats¨
achlich
erhalten wir dieselben bedingten Wahrscheinlichkeiten, wenn wir in den Bedingungen die
vollst¨
andige Vergangenheit des Prozesses bis zur Zeit n ber¨
ucksichtigen:
P (X
n
+1
= v
1
|X
0
= i
0
, X
1
= i
1
, ..., X
n
-1
= i
n
-1
, X
n
= v
2
) =
1
2
und
P (X
n
+1
= v
3
|X
0
= i
0
, X
1
= i
1
, ..., X
n
-1
= i
n
-1
, X
n
= v
2
) =
1
2
Dies gilt f¨
ur jede Wahl von i
0
, ..., i
n
-1
, vorausgesetzt, dass der Pfad i
0
, i
1
, ..., i
n
-1
ei-
ne positive Wahrscheinlichkeit besitzt. Dieses Ph¨
anomen wird die Ged¨
achnislosigkeits-
Eigenschaft genannt, die auch als Markov-Eigenschaft bekannt ist: Die bedingte Verteilung
von X
n
+1
gegeben (X
0
, ..., X
n
) h¨
angt nur von X
n
ab. Eine andere interessante Eigenschaft
dieses Zufallsprozesses besteht darin, dass die bedingte Verteilung von X
n
+1
, gegeben dass
beispielsweise X
n
= v
2
, f¨
ur alle n dieselbe ist. Diese Eigenschaft heißt Zeit-Homogenit¨
at,
oder einfach Homogenit¨
at. Derartige Prozesse lassen sich mit Hilfe sogenannter ¨
Uber-
gangsmatrizen beschreiben:
Definition
Sei P eine k
× k Matrix mit den Elementen {P
i,j
: i, j = 1, ..., k
}. Ein Zu-
fallsprozess (X
0
, X
1
, ...) mit endlichem Zustandsraum S =
{s
1
, ..., s
k
} heißt dann (homo-
gene) Markovkette mit ¨
Ubergangsmatrix P , wenn f¨
ur alle n, alle i, j
{1, ..., k} und alle
i
0
, ..., i
n
-1
{1, ..., k} gilt:
4
P (X
n
+1
= s
j
|X
0
= s
i
0
, X
1
= s
i
1
, ..., X
n
-1
= s
i
n-1
, X
n
= s
i
)
= P (X
n
+1
= s
j
|X
n
= s
i
) = P
i,j
Zum Beispiel ist das Beispiel mit dem zuf¨
alligen L¨
aufer von oben eine Markovkette, mit
dem Ereignisraum
{1, ..., 4} und der ¨Ubergangsmatrix
P =
0
1
2
0
1
2
1
2
0
1
2
0
0
1
2
0
1
2
1
2
0
1
2
0
Jede ¨
Ubergangsmatrix erf¨
ullt dabei:
P
i,j
0 i, j {1, ..., k}
und
k
j
=1
P
i,j
= 1
i {1, ..., k}
Die erste Eigenschaft bedeutet nur, dass alle bedingten Wahrscheinlichkeiten stets nicht-
negativ sind und die zweite Eigenschaft besagt, dass sie sich zu 1 aufsummieren.
Wir wenden uns nun einer anderen wichtigen Charakteristik von Markovketten zu,
n¨
amlich der sogenannten Anfangsverteilung, die beschreibt, wie die Markovkette startet.
Die Anfangsverteilung ist gegeben durch einen Zeilenvektor
(0)
, der sich folgendermaßen
zusammensetzt:
(0)
= (
(0)
1
,
(0)
2
, ...,
(0)
k
)
= (P (X
0
= s
1
), P (X
0
= s
2
), ..., P (X
0
= s
k
)).
Da
(0)
eine Wahrscheinlichkeitsverteilung repr¨
asentiert, ergibt sich:
k
i
=1
(0)
i
= 1
In unserem Beispiel mit dem zuf¨
alligen L¨
aufer gilt:
5
(0)
= (1, 0, 0, 0)
Auf ¨
ahnliche Weise bezeichen die Zeilenvektoren
(1)
,
(2)
, ... die Verteilungen der Mar-
kovkette zu den Zeiten 1, 2, ..., so dass:
(n)
= (
(n)
1
,
(n)
2
, ...,
(n)
k
)
= (P (X
n
= s
1
), P (X
n
= s
2
), ..., P (X
n
= s
k
))
Im Beispiel mit dem zuf¨
alligen L¨
aufer ergibt sich beispielsweise:
(1)
= (0,
1
2
, 0,
1
2
)
Wenn wir die Anfangsverteilung
(0)
und die ¨
Ubergangsmatrix P der Markovkette
kennen, k¨
onnen wir alle Verteilungen
(1)
,
(2)
, ... der Markovkette berechnen: Das folgende
Resultat zeigt uns, dass dies lediglich eine Anwendung der Matrix-Multiplikation darstellt.
Wir schreiben P
n
f¨
ur die n-te Potenz der Matrix P .
Theorem
F¨
ur eine Markovkette (X
0
, X
1
...) mit dem Zustandsraum
{s
1
, ..., s
k
}, Anfangs-
verteilung
(0)
und ¨
Ubergangsmatrix P , gilt f¨
ur jedes n, dass die Verteilung
(n)
zur Zeit
n Folgendes erf¨
ullt:
(n)
=
(0)
P
n
Beweis
Wenden wir uns dem ersten Fall, n = 1 zu. F¨
ur j = 1, ..., k erhalten wir: Aus
dem Satz ¨
uber die totale Wahrscheinlichkeit folgt, dass
(1)
j
= P (X
1
= s
j
) =
k
i
=1
P (X
0
= s
i
, X
1
= s
j
),
denn die s
i
liefern eine disjunkte Zerlegung des Ereignisraumes S =
{s
1
, ..., s
k
}. Nach
Definition der bedingten Wahrscheinlichkeit folgt, dass
(1)
j
=
k
i
=1
P (X
0
= s
i
)P (X
1
= s
j
|X
0
= s
i
)
6
Nach Definition von und P gilt somit
(1)
j
=
k
i
=1
(0)
i
P
i,j
oder anders geschrieben
(1)
j
= (
(0)
P )
j
Hierzu ist ein wenig Wissen ¨
uber Matrix-Arithmetik n¨
otig. Schreibt man die Multiplika-
tion nach dem Falk-Schema
1
aus, ergibt sich:
... P
1,j
...
... P
2,j
...
..
.
... P
k,j
...
(0)
1
(0)
2
...
(0)
k
...
(1)
j
...
Da wir die G¨
ultigkeit der Gleichung f¨
ur jede Komponente j einzeln nachweisen konnten,
gilt also insgesamt:
(1)
=
(0)
P
Um diesen Sachverhalt f¨
ur den generellen Fall zu beweisen, benutzen wir vollst¨
andige
Induktion. Wir fixieren ein m und nehmen an, dass die Behauptung f¨
ur n = m gilt. F¨
ur
n = m + 1 erhalten wir dann analog zum Induktionsanfang:
(m+1)
j
= P (X
m
+1
= s
j
) =
k
i
=1
P (X
m
= s
i
, X
m
+1
= s
j
)
=
k
i
=1
P (X
m
= s
i
)P (X
m
+1
= s
j
|X
m
= s
i
)
=
k
i
=1
(m)
i
P
i,j
= (
(m)
P )
j
Da wir auch f¨
ur den allgemeinen Fall die G¨
ultigkeit der Gleichung f¨
ur jede Komponente
j einzeln nachweisen konnten, folgt insgesamt:
(m+1)
=
(m)
P =
(0)
P
m
P =
(0)
P
m
+1
1
Siehe hierzu beispielsweise Seite 144 in: Gerd Fischer: Lineare Algebra: Eine Einf¨
uhrung f¨
ur Studi-
enanf¨
anger, Vieweg Verlag
7
Das erste Gleichheitszeichen wurde zuvor bewiesen. Das zweite Gleichheitszeichen gilt
nach Induktionsvoraussetzung.
1.2 Irreduzibilit¨
at und Aperiodizit¨
at
Wir beginnen mit der Irreduzibilit¨
at, was salopp gesprochen bedeutet, dass jedes Element
s
i
des Ereignisraums S der Markovkette von jedem anderen Element s
j
aus erreicht wer-
den kann. Um diese Beschreibung pr¨
aziser zu machen, stellen wir uns eine Markovkette
(X
0
, X
1
, ...) mit Ereignisraum S =
{s
1
, ..., s
k
} und ¨Ubergangsmatrix P vor. Wir sagen,
dass das Ereignis s
i
mit s
j
kommuniziert, geschrieben s
i
s
j
, wenn die Kette eine positi-
ve Wahrscheinlichkeit hat, irgendwann s
j
zu erreichen, wenn sie von s
i
startet. In anderen
Worten: s
i
kommuniziert mit s
j
, wenn ein n existiert, so dass gilt:
P (X
m
+n
= s
j
|X
m
= s
i
) > 0
Diese Wahrscheinlichkeit l¨
asst sich auch schreiben als (P
n
)
i,j
. Wenn sogar s
i
s
j
und
s
j
s
i
gilt, sagen wir, dass s
i
und s
j
interkommunizieren und schreiben daf¨
ur s
i
s
j
.
Dies leitet uns zu folgender Definition der Irreduzibilit¨
at:
Definition
Eine Markovkette (X
0
, X
1
, ...) mit Ereignisraum S =
{s
1
, ..., s
k
} und ¨Uber-
gangsmatrix P heißt irreduzibel, wenn f¨
ur alle s
i
, s
j
S gilt, dass s
i
s
j
. Ansonsten
heißt die Kette reduzibel.
Wir kommen nun zum Konzept der Aperiodizit¨
at. F¨
ur eine endliche oder unendli-
che Menge
{a
1
, a
2
, ...
} von positiven ganzen Zahlen, schreiben wir gcd{a
1
, a
2
, ...
} f¨ur den
gr¨
oßten gemeinsamen Teiler von a
1
, a
2
, ... Die Periode d(s
i
) von einem Zustand s
i
S ist
nun definiert als:
d(s
i
) = gcd
{n 1 : (P
n
)
i,i
> 0
},
d.h. die Periode von s
i
ist der gr¨
oßte gemeinsame Teiler der Menge von Zeiten, zu denen
die Kette nach s
i
zur¨
uckkehren kann, gegeben dass wir bei s
i
gestartet sind
2
. Wenn
d(s
i
) = 1 gilt, dann sagen wir, dass der Zustand s
i
aperiodisch ist.
2
Diese Menge k¨
onnte f¨
ur eine ung¨
unstige Wahl der Markovkette auch leer sein. Diesen Sonderfall be-
trachten wir nicht als aperiodisch.
8
Definition
Eine Markovkette heißt aperiodisch, wenn alle Elemente ihres Zustandsraums
aperiodisch sind. Andernfalls heißt die Kette periodisch.
Theorem
Angenommen, wir haben eine aperiodische Markovkette (X
0
, X
1
, ...) mit dem
Ereignisraum S =
{s
1
, ..., s
k
} und der ¨Ubergangsmatrix P . Dann existiert stets ein N N,
so dass
(P
n
)
i,i
> 0
n N i {1, ..., k}
Lemma
Sei A =
{a
1
, a
2
, ...
} eine Menge von positiven ganzen Zahlen, f¨ur die gilt:
1. Die Elemente von A sind teilerfremd, d.h. gcd
{a
1
, a
2
, ...
} = 1, und
2. A ist abgeschlossen unter der Addition, d.h. wenn a
A und a A, gilt a + a A.
Dann existiert stets eine ganze Zahl N
N, so dass n A n N
3
.
Beweis des Theorems
F¨
ur s
i
S, sei A
i
=
{n 1 : (P
n
)
i,i
> 0
}, so dass A
i
in anderen
Worten die Menge der m¨
oglichen R¨
uckkehr-Zeitpunkte zu s
i
darstellt, wenn von s
i
gestar-
tet wird. Wir haben angenommen, das die Markovkette aperiodisch ist und deswegen ist
auch das Ereignis s
i
aperiodisch, so dass die Elemente von A
i
teilerfremd sind. Außerdem
ist A
i
abgeschlossen unter der Addition, aus dem folgenden Grund: Wenn a, a
A
i
, dann
gilt P (X
a
= s
i
|X
0
= s
i
) > 0 und P (X
a
+a
= s
i
|X
a
= s
i
) > 0. Dies bedeutet aber dass
P (X
a
+a
= s
i
|X
0
= s
i
)
P (X
a
= s
i
, X
a
+a
= s
i
|X
0
= s
i
),
=
P (X
a
+a
= s
i
, X
a
= s
i
, X
0
= s
i
)
P (X
0
= s
i
)
,
=
P (X
a
+a
= s
i
|X
a
= s
i
)P (X
a
= s
i
|X
0
= s
i
)P (X
0
= s
i
)
P (X
0
= s
i
)
,
= P (X
a
+a
= s
i
|X
a
= s
i
)P (X
a
= s
i
|X
0
= s
i
) > 0,
da beide Faktoren nach Voraussetzung gr¨
oßer als 0 sind. Insgesamt folgt nun, dass a +
a
A
i
. Zusammenfassend erf¨
ullt nun A
i
die Voraussetzungen 1 und 2 des Lemmas, was
bedeutet, dass eine ganze Zahl N
i
<
existiert, so dass n A
i
n N
i
. Dies bedeutet
3
Ein Beweis dieses Lemmas befindet sich in: Br´
emaud, P. (1998) Markov Chains: Gibbs fields, Monte
Carlo Simulation, and Queues, Springer, New York.
9
aber, dass (P
n
)
i,i
> 0
n N
i
. Das Theorem folgt nun, indem wir N folgendermaßen
w¨
ahlen:
N = max
{N
1
, ..., N
k
}
Korollar
Sei (X
0
, X
1
, ...) eine irreduzible und aperiodische Markovkette mit Ereignis-
raum S =
{s
1
, ..., s
k
} und ¨Ubergangsmatrix P . Dann existiert stets ein M N, so dass
(P
n
)
i,j
> 0
n M i, j {1, ..., k}.
Beweis
Wegen der vorausgesetzten Aperiodizit¨
at existiert eine ganze Zahl N
N, so
dass (P
n
)
i,i
> 0
n N i {1, ..., k}. Fixiere nun zwei Zust¨ande s
i
, s
j
S. Wegen der
vorausgesetzten Irreduzibilit¨
at k¨
onnen wir nun ein n
i,j
finden, so dass (P
n
i,j
)
i,j
> 0 gilt.
Sei nun M
i,j
= N + n
i,j
. F¨
ur jedes m
M
i,j
ergibt sich nun:
P (X
m
= s
j
|X
0
= s
i
)
P (X
m
-n
i,j
= s
i
, X
m
= s
j
|X
0
= s
i
),
=
P (X
m
= s
j
, X
m
-n
i,j
= s
i
, X
0
= s
i
)
P (X
0
= s
i
)
,
=
P (X
m
= s
j
|X
m
-n
i,j
= s
i
)P (X
m
-n
i,j
= s
i
|X
0
= s
i
)P (X
0
= s
i
)
P (X
0
= s
i
)
,
= P (X
m
= s
j
|X
m
-n
i,j
= s
i
)P (X
m
-n
i,j
= s
i
|X
0
= s
i
) > 0,
wobei der erste Faktor wegen der geeigneten Wahl von n
i,j
gr¨
oßer 0 ist und der zweite
Faktor positiv ist, weil m
- n
i,j
N. Gezeigt wurde also, dass (P
m
)
i,j
> 0
m M
i,j
.
Das Korollar folgt nun, wenn wir M folgendermaßen festsetzen:
M = max
{M
1,1
, M
1,2
, ..., M
1,k
, M
2,1
, M
2,2
, ..., M
2,k
, ..., M
k,k
}
1.3 Station¨
are Verteilungen und Reversibilit¨
at
1.3.1 Existenz der station¨
aren Verteilung
In diesem Abschnitt geht es um einige wichtige Aspekte der Markov-Ketten: Asymptoti-
sches Verhalten bei der Langzeit-Betrachtung von Markov-Ketten. Was k¨
onnen wir also
¨
uber eine Markov-Kette sagen, die schon lange Zeit gelaufen ist? Wenn (X
0
, X
1
, ...) eine
nichttriviale
4
Markov-Kette ist, dann wird der Wert von X
n
unendlich oft fluktuieren
4
Wir gehen hier von den ¨
ublicherweise auftretenden Markov-Ketten aus und betrachten nicht Beson-
derheiten wie absorbierende Zust¨
ande.
10
wenn n
und deswegen k¨onnen wir nicht davon ausgehen, dass X
n
gegen irgend-
einen Wert konvergiert. Trotzdem k¨
onnen wir hoffen, dass die Verteilung von X
n
gegen
einen Grenzwert konvergiert. Dies ist in der Tat der Fall, wenn die Markovkette irredu-
zibel und aperiodisch ist, was das zentrale Resultat dieser Betrachtung sein wird. Man
spricht hier von dem so genannten Markovketten-Konvergenz-Theorem. Dies motiviert
uns, nach Verteilungen zu suchen, die erhalten bleiben sofern sie jemals erreicht werden.
Wir k¨
onnen uns durch ein wenig Experimentieren davon ¨
uberzeugen, dass es solche Ver-
teilungen tats¨
achlich gibt. Solche Verteilungen heißen station¨
are Verteilungen, die wir wie
folgt definieren:
Definition
Sei (X
0
, X
1
, ...) eine Markovkette mit Zustandsraum
{s
1
, ..., s
k
} und ¨Uber-
gangsmatrix P . Ein Zeilenvektor = (
1
, ...,
k
) heißt dann station¨
are Verteilung der
Markovkette, wenn er folgendes erf¨
ullt:
1.
i
0 f¨ur i = 1, ..., k, und
k
i
=1
i
= 1, und
2. P = , d.h.
k
i
=1
i
P
i,j
=
j
f¨
ur j = 1, ..., k.
Eigenschaft 1 heißt einfach, dass es sich bei um eine Wahrscheinlichkeitsverteilung auf
{s
1
, ..., s
k
} handelt. Eigenschaft 2 heißt, dass bei der Wahl
(0)
= der Anfangsverteilung,
dies auch f¨
ur
(1)
gilt, und zwar mit dem folgenden Argument:
(1)
=
(0)
P = P =
Mit Hilfe einer vollst¨
andigen Induktion sehen wir auch, dass
(n)
= f¨
ur jedes n. Zu-
sammen mit dem Induktionsanfang zeigt dies, dass die station¨
are Verteilung, sofern sie
einmal erreicht wird, f¨
ur immer beibehalten wird. Weil die Definition einer station¨
aren
Verteilung eigentlich nur von der ¨
Ubergangsmatrix P abh¨
angt, sagen wir manchmal ein-
fach, dass die Verteilung station¨
ar f¨
ur die Matrix P ist (anstelle von station¨
ar f¨
ur die
Markovkette). Nachfolgend werden wir uns mit der Frage der Existenz der station¨
aren
Verteilung besch¨
aftigen.
Theorem
F¨
ur jede irreduzible und aperiodische Markovkette gibt es mindestens eine
station¨
are Verteilung.
11
Um dieses Existenz-Theorem zu beweisen, m¨
ussen wir zun¨
achst ein Lemma ¨
uber Warte-
zeiten f¨
ur Markovketten beweisen. Wenn eine Markovkette (X
0
, X
1
, ...) mit Zustandsraum
{s
1
, ..., s
k
} und ¨Ubergangsmatrix P beim Zustand s
i
startet, dann k¨
onnen wir die War-
tezeit folgendermaßen definieren:
T
i,j
= min
{n 1 : X
n
= s
j
}
mit der Konvention, dass T
i,j
=
falls die Markovkette niemals s
j
erreicht. Wir definieren
ebenso die mittlere Wartezeit auf folgende Weise:
i,j
= E[T
i,j
]
Das bedeutet, dass
i,j
die erwartete Zeit ist, die vergeht, bis der Zustand s
j
erreicht wird.
F¨
ur den Fall i = j nennen wir
i,i
die mittlere R¨
uckkehrzeit f¨
ur den Zustand s
i
.
Lemma
F¨
ur jegliche zwei Zust¨
ande s
i
, s
j
S einer irreduziblen und aperiodische Mar-
kovkette mit Zustandsraum S =
{s
1
, ..., s
k
} und ¨Ubergangsmatrix P gilt, wenn die Kette
im Zustand s
i
startet, dass:
P (T
i,j
<
) = 1
und
E[T
i,j
] <
Beweis des Lemmas
Wir k¨
onnen stets ein M
N finden, so dass (P
M
)
i,j
> 0 f¨
ur alle
i, j
{1, ..., k}. Fixiere solch ein M und setze = min{(P
M
)
i,j
: i, j
{1, ..., k}} und
bemerke, dass immer > 0 gilt. Fixiere zwei Zust¨
ande s
i
und s
j
und nehme an, dass die
Kette bei s
i
startet. Dann ergibt sich:
P (T
i,j
> M )
P (X
M
= s
j
) = 1
- (P
M
)
i,j
1 -
Betrachten wir nun die Wahrscheinlichkeit, dass T
i,j
> 2M : Dies ist ¨
aquivalent zu der
Wahrscheinlichkeit, dass T
i,j
> M und T
i,j
> 2M gleichzeitig eintritt, denn mit dem
Eintreten von T
i,j
> 2M ist auch immer T
i,j
> M impliziert. Mit Benutzung der Definition
der bedingten Wahrscheinlichkeit folgt also insgesamt, dass:
P (T
i,j
> 2M ) = P (T
i,j
> M )P (T
i,j
> 2M
|T
i,j
> M )
12
Die Forderung X
2M
= s
j
ist eine schw¨
achere Forderung als T
i,j
> 2M und hat daher eine
gr¨
oßere Wahrscheinlichkeit:
P (T
i,j
> 2M )
P (T
i,j
> M )P (X
2M
= s
j
|T
i,j
> M )
Analog zu oben sind beide Faktoren gleich (1
- ) (Beachte f¨ur den zweiten Faktor die
Zeit-Homogenit¨
at), insgesamt folgt also:
P (T
i,j
> 2M )
(1 - )
2
Dies k¨
onnen wir verallgemeinern f¨
ur T
i,j
> lM f¨
ur ein beliebiges l
N:
P (T
i,j
> lM ) = P (T
i,j
> M )P (T
i,j
> 2M
|T
i,j
> M )...
×P (T
i,j
> lM
|T
i,j
> (l
- 1)M)
(1 - )
l
Dieser Ausdruck konvergiert gegen 0, wenn l
. Deswegen ist P (T
i,j
=
) = 0 und
folglich P (T
i,j
<
) = 1.
Nun m¨
ussen wir noch beweisen, dass der Erwartungswert von T
i,j
immer endlich ist.
Dazu verwenden wir eine alternative Formel f¨
ur den Erwartungswert:
E[X] =
k
=1
kP (X = k) =
k
=1
P (X
k)
In unserem Fall bedeutet das:
E[T
i,j
] =
n
=1
P (T
i,j
n) =
n
=0
P (T
i,j
> n)
Diese Summe kann man nun geeignet in Teilsummen zerlegen:
E[T
i,j
] =
l
=0
(l+1)M-1
n
=lM
P (T
i,j
> n)
Weil nun stets lM
n ist, ist P (T
i,j
> lM ) eine schw¨
achere Forderung, die deswegen eine
h¨
ohere Wahrscheinlichkeit aufweist, daher:
E[T
i,j
]
l
=0
(l+1)M-1
n
=lM
P (T
i,j
> lM )
13
In der zweiten Summe stehen nun immer M Summanden, die f¨
ur ein fixiertes l alle gleich
sind, daher:
E[T
i,j
]
M
l
=0
P (T
i,j
> lM )
Nach unserer vorherigen Betrachtung kennen wir den Ausdruck (1
- )
l
f¨
ur P (T
i,j
> lM )
und berechnen die resultierende geometrische Reihe:
E[T
i,j
]
M
l
=0
(1
- )
l
= M
1
1
- (1 - )
=
M
<
Beweis des Theorems
Wie immer schreiben wir (X
0
, X
1
, ...) f¨
ur die Markovkette, S =
{s
1
, ..., s
k
} f¨ur den Zustandsraum und P f¨ur die ¨Ubergangsmatrix. Nehmen wir an, dass
die Kette im Zustand s
1
startet und definieren f¨
ur i = 1, ..., k:
i
=
n
=0
P (X
n
= s
i
, T
1,1
> n)
In anderen Worten ist also
i
die erwartete Anzahl an Besuchen des Zustands s
i
bis zur
Zeit T
1,1
- 1. Nun ist die mittlere R¨uckkehrzeit E[T
1,1
] =
1,1
endlich und deswegen muss
auch
i
endlich sein, denn
i
<
1,1
(dies ist der Fall, da nicht mehr Besuche zu Zustand
s
i
in der Zeit T
1,1
m¨
oglich sind als die Zeitspanne selbst lang ist). Wir schlagen nun einen
Kandidaten f¨
ur die station¨
are Verteilung vor:
= (
1
, ...,
k
) =
1
1,1
,
2
1,1
, ...,
k
1,1
Wir m¨
ussen nun ¨
uberpr¨
ufen, ob unser Kandidat die Forderungen der Definition einer
station¨
aren Verteilung erf¨
ullt. Wir zeigen dazu zun¨
achst, dass der Kandidat die Forderung
2 in der Definition erf¨
ullt, welche
k
i
=1
i
P
i,j
=
j
lautet. Zun¨
achst gehen wir auf den Fall
j = 1 ein, der Fall j = 1 wird nachher separat betrachtet. Nach Definition gilt:
j
=
j
1,1
=
1
1,1
n
=0
P (X
n
= s
j
, T
1,1
> n)
Nun beachten wir, dass X
0
= s
1
gesetzt wurde und daher X
0
= s
j
, da j = 1:
j
=
1
1,1
n
=1
P (X
n
= s
j
, T
1,1
> n)
Jetzt beachten wir, dass die Ereignisse X
n
= s
j
und T
1,1
= n nicht gleichzeitig einteffen
k¨
onnen, weil X
n
nicht gleichzeitig s
j
und s
1
sein kann, wenn j = 1. Daher reicht eine
14
schw¨
achere Forderung an T
1,1
:
j
=
1
1,1
n
=1
P (X
n
= s
j
, T
1,1
> n
- 1)
Nun gilt nach dem Satz ¨
uber die totale Wahrscheinlichkeit:
j
=
1
1,1
n
=1
k
i
=1
P (X
n
-1
= s
i
, X
n
= s
j
, T
1,1
> n
- 1)
Wir zerlegen dies jetzt nach der Definition der bedingten Wahrscheinlichkeit und beachten
dabei die Ged¨
achtnislosigkeit der Markovkette, deren momentaner Zustand nur von dem
vorherigen abh¨
angt (Beachte hierbei, dass T
1,1
> n
- 1 auch nur eine Aussage ¨uber die
letzten n-1 Zust¨
ande ist, wovon nur der letzte f¨
ur die Verteilung des aktuellen Zustands
relevant ist):
j
=
1
1,1
n
=1
k
i
=1
P (X
n
-1
= s
i
, T
1,1
> n
- 1)P (X
n
= s
j
|X
n
-1
= s
i
)
Nach Benutzung der Definition der ¨
Ubergangsmatrix folgt:
j
=
1
1,1
n
=1
k
i
=1
P
i,j
P (X
n
-1
= s
i
, T
1,1
> n
- 1)
Durch Vertauschung der Summen (Kommutativit¨
at) ergibt sich:
j
=
1
1,1
k
i
=1
P
i,j
n
=1
P (X
n
-1
= s
i
, T
1,1
> n
- 1)
Nun f¨
uhren wir eine Substitution von (n
- 1) gegen m aus:
j
=
1
1,1
k
i
=1
P
i,j
m
=0
P (X
m
= s
i
, T
1,1
> m)
Wir verwenden nun die Definition von
i
:
j
=
k
i
=1
i
P
i,j
1,1
Nach Benutzung der Definition von
i
folgt nun:
j
=
k
i
=1
i
P
i,j
Damit ist der Fall j = 1 verifiziert. Es folgt nun der Fall j = 1 separat: Dazu bemerken
wir zun¨
achst, dass
1
= 1, weil
1
die erwartete Anzahl der Besuche zu s
1
angibt, bis
15
Details
- Seiten
- Erscheinungsform
- Erstausgabe
- Erscheinungsjahr
- 2007
- ISBN (PDF)
- 9783956849510
- ISBN (Paperback)
- 9783956844515
- Dateigröße
- 5.4 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Universität Bielefeld
- Erscheinungsdatum
- 2015 (Februar)
- Note
- 1
- Schlagworte
- MCMC Implementierung Markov-Kette Metropolis-HastingsAlgorithmus Gibbs-Sampler
- Produktsicherheit
- BACHELOR + MASTER Publishing
