Nächste Seite: Stationäre Anfangsverteilungen
Aufwärts: Ergodizität und Stationarität
Vorherige Seite: Abschätzung der Konvergenzgeschwindigkeit; Perron-Frobenius-Theorem
  Inhalt
Irreduzibilität und Aperiodizität
- Zur Erinnerung
- In Theorem 2.4 hatten wir die Ergodizität der
Markov-Kette
durch die Quasi-Positivität ihrer
Übergangsmatrix
charakterisiert.
- Es kann sich jedoch als schwierig erweisen, diese Eigenschaft von
direkt nachzuweisen (insbesondere dann, wenn ).
- Wir leiten deshalb noch eine andere (probabilistische)
Charakterisierung der Ergodizität von Markov-Ketten mit endlichem
Zustandsraum her. Dabei benötigen wir den folgenden Begriff.
- Für beliebige, jedoch fest vorgegebene Zustände sagen
wir, dass der Zustand vom Zustand erreichbar ist,
falls
für ein gilt, wobei
. (Schreibweise: )
- Eine andere (äquivalente) Definitionsmöglichkeit der
Erreichbarbeit von Zuständen ist folgendermaßen gegeben.
- Hierfür sei
die Anzahl der Schritte
bis die Markov-Kette zum ersten Mal den Zustand
erreicht. Dabei setzen wir
, falls für
jedes .
Theorem 2.7
Sei
so gewählt, dass
. In diesem Fall ist der
Zustand
genau dann von
erreichbar, wenn
.
- Beweis
-
- Beachte
-
- Die Eigenschaft der Erreichbarkeit ist
- transitiv, d.h., aus und folgt .
- Dies ergibt sich unmittelbar aus der Ungleichung
(vgl.
Korollar 2.2) und aus der Definition der
Erreichbarkeit.
- Falls darüber hinaus und , dann sagen wir, dass
die Zustände und kommunizieren. (Schreibweise:
)
- Die Eigenschaft des Kommunizierens ist eine Äquivalenzrelation, denn es gilt
- (a)
-
(Reflexivität),
- (b)
-
genau dann, wenn
(Symmetrie),
- (c)
-
und
implizieren, dass
(Transitivität).
- Dies bedeutet insbesondere,
- dass der Zustandsraum in (disjunkte und ausschöpfende)
Äquivalenzklassen bezüglich der Äquivalenzrelation
zerlegt werden kann.
- Dabei heißt die Markov-Kette bzw. ihre Übergangsmatrix
irreduzibel, wenn der Zustandsraum nur
aus einer solchen Äquivalenzklasse besteht, d.h., wenn
für sämtliche gilt.
- Beispiele
-
- Unmittelbar aus der Definition der Irreduzibilität ergibt sich,
dass die Matrizen
und
irreduzibel sind.
- Die aus
und
gebildete Matrix
mit der folgenden Blockstruktur
ist jedoch nicht irreduzibel.
Neben der Irreduzibilität benötigen wir noch eine weitere
Eigenschaft der Zustände, nämlich die sogenannte Aperiodizität, um die Ergodizität von Markov-Ketten auf
einfache Weise charakterisieren zu können.
- Definition
-
- Die Periode des Zustandes ist gegeben durch
, wobei ,,ggt'' den
größten gemeinsamen Teiler bezeichnet. Dabei setzen wir
, falls
für jedes .
- Der Zustand heißt aperiodisch, falls .
- Die Markov-Kette bzw. ihre Übergangsmatrix
heißt aperiodisch, wenn sämtliche Zustände
von aperiodisch sind.
Wir zeigen nun, dass die Perioden und übereinstimmen,
wenn die Zustände zu einundderselben Äquivalenzklasse von
kommunizierenden Zuständen gehören. Dabei verwenden wir die
Schreibweise , falls
.
Theorem 2.8
Falls die Zustände
kommunizieren, dann gilt
.
- Beweis
-
- Falls , und for gewisse
gilt, dann ergibt sich aus den Ungleichungen in
Korollar 2.2, dass
und
.
- Dies bedeutet, dass die natürlichen Zahlen and durch
teilbar sind.
- Dann ist auch
durch teilbar.
- Somit ist ein gemeinsamer Teiler für diejenigen natürlichen
Zahlen , für die
gilt, d.h.
.
- Auf die gleiche Weise ergibt sich (aus Symmetriegründen), dass
auch
gilt.
Korollar 2.5
Die Markov-Kette
sei
irreduzibel. Dann besitzen sämtliche Zustände von
die
gleiche Periode.
Um zeigen zu können,
- dass die in Abschnitt 2.2.1 betrachtete
Charakterisierung (vgl. Theorem 2.4) der
Ergodizität von Markov-Ketten gleichbedeutend mit ihrer
Irreduzibilität und Aperiodizität ist,
- benötigen wir noch den folgenden elementaren Hilfssatz aus der
Zahlentheorie.
Lemma 2.3
Sei
eine beliebige, jedoch fest vorgegebene
natürliche Zahl. Dann gibt es eine natürliche Zahl
, so
dass
- Beweis
-
Theorem 2.9
Die Übergangsmatrix
ist genau dann quasi-positiv, wenn
irreduzibel und aperiodisch ist.
- Beweis
-
- Wir nehmen zunächst an, dass die Übergangsmatrix
irreduzibel und aperiodisch ist.
- Für jedes betrachten wir die Menge
, deren größter gemeinsamer Teiler wegen der
Aperiodizität von
gleich ist.
- Aus den Ungleichungen in Korollar 2.2 ergibt sich, dass
und somit
|
(50) |
- Wir zeigen, dass die Menge zwei aufeinanderfolgende Zahlen
enthält.
- Falls umgekehrt nicht zwei aufeinanderfolgende Zahlen
enthalten würde, dann würde es einen Minimalabstand
zwischen den Zahlen in geben.
- Hieraus würde die Gültigkeit von
für gewisse
und
folgen, weil ansonsten
für alle gelten würde.
- Dies würde jedoch ein Widerspruch zu unserer Annahme sein, dass
ggt.
- Sei nun
. Wegen (50) gilt dann
auch
und
für beliebige
, wobei
|
(51) |
- Wir zeigen jedoch,
- dass es dann natürliche Zahlen
gibt, so
dass die Differenz zwischen
und
kleiner als ist.
- Und zwar ergibt sich aus (51), dass
und somit für
- Deshalb enthält die Menge zwei aufeinanderfolgende Zahlen.
- Aus (50) und aus Lemma 2.3 ergibt sich
nun, dass es für jedes ein gibt, so dass
|
(52) |
- Hieraus, aus der Irreduzibilität von
und aus der
Ungleichung (25) in Korollar 2.2, d.h.,
folgt, dass es für jedes Paar von Zuständen eine
natürliche Zahl
gibt, so dass
d.h.,
ist quasi-positiv.
- Umgekehrt ergibt sich die Irreduzibilität und Aperiodizität von
quasi-positiven Übergangsmatrizen unmittelbar aus den Definitionen
dieser Begriffe.
- Beachte
-
- Ein einfaches Beispiel einer Markov-Kette, die nicht
irreduzibel ist,
- kann durch das bereits mehrfach betrachtete Modell der Wettervorhersage gegeben werden, wobei und
- Falls oder
, dann ist die zugehörige
Markov-Kette offenbar nicht irreduzibel (und damit wegen
Theorem 2.9 auch nicht ergodisch).
- Es ist dennoch möglich, dass das lineare Gleichungssystem
|
(53) |
eine (oder unendlich viele)
Wahrscheinlichkeitslösungen
besitzt.
- Wenn beispielsweise und
gilt, dann ist
ein sogenannter absorbierender Zustand, und
ist die (eindeutig bestimmte) Lösung des
linearen Gleichungssystems (53).
- Wenn und
, dann ist jede
Wahrscheinlichkeitsfunktion
Lösung des linearen Gleichungssystems (53).
- Wir geben nun noch Beispiele von Markov-Ketten
an, die nicht aperiodisch sind.
- Dabei sind die Zufallsvariablen
nicht durch eine stochastische Rekursionsgleichung
der Form (14) gegeben,
so dass die ,,Zuwächse''
unabhängige
und identisch verteilte Zufallsvariablen sind.
- Wir setzen nämlich lediglich voraus, dass die Zufallsvariablen
in dem folgenden Sinne ,,bedingt
unabhängig'' sind.
- Wie in Abschnitt 2.1.3 gezeigt wurde, kann man jedoch
stets eine zu
stochastisch äquivalente
Markov-Kette konstruieren, deren Zuwächse unabhängig sind, vgl.
das in (17)-(19) betrachtete
Konstruktionsprinzip.
- Seien also und beliebige endliche (oder abzählbar
unendliche) Mengen, sei
eine beliebige
Funktion, und seien
bzw.
Zufallsvariablen,
- Man kann zeigen (vgl. Übungsaufgabe 4.2), dass die durch
(54) rekursiv gegebene Folge
eine Markov-Kette ist, deren
Übergangsmatrix
gegeben ist durch
falls
für jedes .
- Beispiel
- (Diffusionsmodell)
vgl. P. Brémaud (1999)
Markov Chains. Springer-Verlag, New York, S.76
- Beachte
-
Nächste Seite: Stationäre Anfangsverteilungen
Aufwärts: Ergodizität und Stationarität
Vorherige Seite: Abschätzung der Konvergenzgeschwindigkeit; Perron-Frobenius-Theorem
  Inhalt
Ursa Pantle
2003-09-29