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