close

Вход

Забыли?

вход по аккаунту

?

4297.Stochastische Prozesse I 001 .pdf

код для вставкиСкачать
STOCHASTISCHE PROZESSE
I: Markovketten in diskreter und stetiger Zeit
Wolfgang König
Vorlesungsskript
Universität Leipzig
Sommersemester 2005
Inhaltsverzeichnis
1 Grundlagen
3
1.1
Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.2
Stochastische Prozesse und ihre Verteilung . . . . . . . . . . . . . . . . . . . . . .
4
1.3
Endlich-dimensionale Verteilungen . . . . . . . . . . . . . . . . . . . . . . . . . .
6
2 Markovketten in diskreter Zeit
9
2.1
Definition und einfache Eigenschaften . . . . . . . . . . . . . . . . . . . . . . . .
9
2.2
Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
2.3
Klasseneigenschaften, Rekurrenz, Transienz . . . . . . . . . . . . . . . . . . . . .
15
2.4
Stoppzeiten und die starke Markov-Eigenschaft . . . . . . . . . . . . . . . . . . .
19
2.5
Gleichgewichtsverteilungen
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
23
2.6
Konvergenz gegen die Gleichgewichtsverteilung . . . . . . . . . . . . . . . . . . .
27
2.7
Reversible Markovketten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
29
3 Markovketten in stetiger Zeit
33
3.1
Intuitive Konstruktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.2
Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.3
Definitionen und erste Ergebnisse . . . . . . . . . . . . . . . . . . . . . . . . . . .
41
3.4
Vorwärts- und Rückwärtsgleichungen . . . . . . . . . . . . . . . . . . . . . . . . .
48
3.5
Langzeitverhalten und invariante Maße . . . . . . . . . . . . . . . . . . . . . . . .
54
Literatur
63
i
Vorwort
Dies ist das Vorlesungsskript einer zweistündigen einführenden Vorlesung über stochastische
Prozesse. Es werden zunächst die grundlegenden Begriffe motiviert und entwickelt, wie endlich
dimensionale Verteilungen und die Verteilung eines stochastischen Prozesses. Der Rest dieses
Skriptes ist den Markovketten in diskreter und in stetiger Zeit auf endlichen oder höchstens
abzählbaren Zustandsräumen gewidmet. Wir führen die grundlegenden Begriffe und wichtigsten
Beispiele ein und diskutieren ausführlich die Rekurrenz- und Transienzeigenschaften, Klasseneinteilung der Zustände, invariante Maße und Konvergenz in das Gleichgewicht. Fast alle Aussagen
werden vollständig bewiesen.
Der Skriptteil über Markovketten in diskreter Zeit ist im Wesentlichen meinem Skript Stochastik I (Universität zu Köln, Sommersemester 2003) entnommen, der Teil über kontinuierliche
Zeit folgt einem Skript Stochastische Modelle (TU Berlin) von Michael Scheutzow, dem ich hiermit für die freundliche Überlassung danke.
Leipzig, im März 2005
1
Kapitel 1
Grundlagen
In diesem Kapitel wollen wir den Begriff des stochastischen Prozesses anschaulich und formal
einführen.
1.1
Einleitung
Ein stochastischer Prozess ist ein mathematisches Modell für einen realen Vorgang, der zufällig
ist und von einem Parameter (meist der Zeit) abhängt. Beispiele für zufällige reale Vorgänge,
auf die die Theorie der stochastischen Prozesse mit Erfolg angewendet wird, sind:
• Warteschlangen (auch Netze von Warteschlangen),
• Ausbreitung von Epidemien oder von Genen,
• Populationsentwicklung,
• Bewegung eines Elektrons in einem magnetischen Feld,
• Simulation einer Wahrscheinlichkeitsverteilung,
• Stochastisches Optimieren,
• Kartenmischen,
• Aktienkurse,
• Kapital eines Versicherungsunternehmens,
• Temperaturverteilung auf der Erdoberfläche.
Alle diese Beispiele sind zeitabhängig und in der Regel nicht mit Sicherheit vorhersagbar,
weswegen sich eine stochastische Modellierung anbietet. Zu stochastischen Prozessen werden
diese Beispiele erst dann, wenn man festlegt, mit welchen Wahrscheinlichkeiten die einzelnen
Realisierungen auftreten. Man kann einen stochastischen Prozess auffassen als eine Zufallsvariable mit Werten in einem geeigneten Raum von (Zeit-)funktionen, also eine zufällige Funktion.
Zu einem stochastischen Prozess gehört immer ein Zustandsraum E und eine Parametermenge I. Der Zustandsraum ist der Wertebereich oder eine Obermenge davon, die Parametermenge
3
4
KAPITEL 1. GRUNDLAGEN
ist der Definitionsbereich der zufälligen Funktion, meist ein Zeitintervall. Zustandsraum E und
Parametermenge I können im Prinzip beliebige nichtleere Mengen sein; für E werden wir aber
gleich eine zusätzliche Struktur fordern. Wichtig sind aber die Spezialfälle, wo E endlich oder
abzählbar unendlich ist oder E = R, Rn oder ein Funktionenraum und I diskret (also endlich oder z. B. gleich N, N0 oder Z) oder kontinuierlich ist (also etwa R, [0, ∞), R n oder die
Kugeloberfläche).
I ist in den meisten Anwendungsfällen eine Menge von Zeitpunkten. Es gibt aber auch interessante Beispiele, für die I nicht als “Zeit”, sondern als “Ort” zu interpretieren ist. Interessiert
man sich etwa für die Temperaturverteilung auf der gesamten Erdoberfläche zu einem festen
Zeitpunkt, dann ist der Definitionsbereich I z. B. die Kugeloberfläche.
Wenn man ein mathematisches Modell, d. h. einen stochastischen Prozess, festgelegt hat,
dann kann man je nach Anwendung an verschiedenen Fragen interessiert sein, zum Beispiel
an der Berechnung der Wahrscheinlichkeiten gewisser Ereignisse oder qualitativen Aussagen
wie Langzeitverhalten, Rückkehreigenschaften, Existenz von Gleichgewichtszuständen. In diesem
Skript werden wir diese Fragen und noch mehr für zwei der fundamentalen Typen von stochastischen Prozessen allgemein untersuchen und an Hand von Beispielen illustrieren: Markovketten
in diskreter und in stetiger Zeit. Doch zuvor legen wir noch die allgemeinen mathematischen
Fundamente der Theorie der stochastischen Prozesse.
1.2
Stochastische Prozesse und ihre Verteilung
Wir wollen nun formal den Begriff eines stochastischen Prozesses definieren. Zunächst geben wir
die Definition für reelle Werte.
Definition 1.2.1 (Stochastischer Prozess). Ein stochastischer Prozess ist eine Familie
(Xt )t∈I von reellwertigen Zufallsvariablen X t , t ∈ I, die auf demselben Wahrscheinlichkeitsraum (Ω, F, P) definiert sind. Dabei ist I eine beliebige nichtleere Indexmenge.
Meist ist I eine Teilmenge von R und wird als Zeit interpretiert.
Oft erlaubt man auch allgemeinere Zustandsräume E als nur die Menge R der reellen Zahlen. Um von der Verteilung einer E-wertigen Zufallsvariablen reden zu können, muss auf E
eine σ-Algebra E definiert werden. Das Paar (E, E) nennt man einen Messraum. Wir erinnern
daran, dass eine σ-Algebra E über einer nichtleeren Menge E eine Teilmenge der Potenzmenge
von E ist, die die leere Menge enthält und abgeschlossen gegen Komplement- und abzählbarer
Vereinigungsbildung ist. σ-Algebren sind die natürlichen Definitionsbereiche für Wahrscheinlichkeitsmaße.
Eine ausführlichere und allgemeine Definition eines stochastischen Prozesses lautet wie folgt:
Definition 1.2.2 (Stochastischer Prozess). Sei (E, E) ein Messraum. Ein stochastischer
Prozess mit Zustandsraum (E, E) ist eine Familie (X t )t∈I von messbaren Abbildungen Xt ,
t ∈ I, von demselben Wahrscheinlichkeitsraum (Ω, F, P) nach (E, E). Für festes ω ∈ Ω heißt
die Abbildung X· (ω) : I → E Pfad, Trajektorie oder Realisierung des stochastischen Prozesses.
Falls I = N0 oder I = [0, ∞), so heißt die Verteilung von X 0 die Startverteilung des Prozesses.
(Falls E diskret ist, so spricht man auch vom Startvektor.)
5
1.2. STOCHASTISCHE PROZESSE UND IHRE VERTEILUNG
Wir erinnern daran, dass eine Abbildung X : (E 1 , E1 ) → (E2 , E2 ) zwischen zwei Messräumen
messbar heisst, wenn alle Urbilder unter X von Elementen in E 2 in E1 liegen, also
B ∈ E2
=⇒
X −1 (B) = {ω ∈ E1 : X(ω) ∈ B} ∈ E1 .
(1.2.1)
Bekanntermaßen ist für Zufallsvariablen der Begriff der Verteilung sehr wichtig. Sehr oft
sind die Größen, die einen an einer Zufallsvariablen interessieren, Funktionen der Verteilung der
Zufallsvariablen, zum Beispiel Erwartungswert, Varianz oder die Überschreitungswahrscheinlichkeit einer Grenze. Für stochastische Prozesse gilt Ähnliches. Daher ist es unser nächstes Ziel,
die Verteilung eines stochastischen Prozesses zu definieren.
Wir erinnern an die Definition der Verteilung einer reellwertigen Zufallsvariable, d. h. des
Falls |I| = 1 und (E, E) = (R, B), wobei B die Borel-σ-Algebra über R ist, nämlich die von den
Intervallen erzeugte. Eine reelle Zufallsvariable X ist eine messbare Abbildung
X : (Ω, F, P) → (R, B),
(1.2.2)
und die Verteilung P ◦ X −1 von X ist das Bildmaß auf (R, B) von P unter X d. h.
P ◦ X −1 (B) = P(X −1 (B)) = P({ω ∈ Ω : X(ω) ∈ B}),
B ∈ B.
(1.2.3)
Man sieht hier, dass die Messbarkeit von X wichtig ist. Sie garantiert nämlich, dass X −1 (B) in
F liegt und somit P(X −1 (B)) überhaupt definiert ist.
In der Situation, wo X ein stochastischer Prozess ist, hat man statt der Wertemenge R
eine Menge von Funktionen I → E, also eine Teilmenge von E I , d. h. zufällige Funktionen statt
zufälliger Zahlen. Um wie im reellwertigen Fall wie oben eine Verteilung P ◦ X −1 definieren zu
können, braucht man auf E I eine σ-Algebra. Die am meisten verwendete und üblichste ist die
Produkt-σ-Algebra E ⊗I :
Definition 1.2.3 (Produkt-σ-Algebra). E ⊗I ist die kleinste σ-Algebra über E I , die alle
endlich-dimensionalen Rechtecke enthält, d. h. alle Mengen der Form
{f ∈ E I : f (i1 ) ∈ E1 , . . . , f (ik ) ∈ Ek },
mit k ∈ N, i1 , . . . , ik ∈ I, E1 , . . . , Ek ∈ E.
(1.2.4)
Dann stellt sich auf elementare Weise ( Übungsaufgabe) heraus, dass ein stochastischer Prozess nichts weiter als eine (E I , E ⊗I )-wertige Zufallsgröße ist:
Lemma 1.2.4. Sei (Xt )t∈I ein stochastischer Prozess mit Zustandsraum (E, E). Definiere eine
Abbildung X : (Ω, F, P) → (E I , E ⊗I ) durch
(X(ω))(t) := Xt (ω),
ω ∈ Ω, t ∈ I.
(1.2.5)
Dann ist X messbar, d. h. X −1 (B) ∈ F für alle B ∈ E ⊗I .
Wir schreiben auch X = (Xt )t∈I für die in (1.2.5) formal definierte Zufallsgröße, also den
stochastischen Prozess. Also können wir die seine Verteilung ganz analog zur Verteilung einer
Zufallsvariablen definieren.
Definition 1.2.5 ( Verteilung eines stochastischen Prozesses). Die Verteilung eines stochastischen Prozesses (Xt )t∈I auf (Ω, F, P ) mit Zustandsraum (E, E) ist das Bildmaß von P
unter der in (1.2.5) definierten Abbildung X; in Formeln:
P ◦ X −1 (B) = P(X −1 (B)) = P({ω : X(ω) ∈ B}),
B ∈ E ⊗I .
(1.2.6)
6
KAPITEL 1. GRUNDLAGEN
Aus der Verteilung eines Prozesses (X t )t∈I ist im Allgemeinen nicht erkennbar, ob zum
Beispiel im Fall I = R, E = R alle Pfade stetige Funktionen sind. Die frühere Bemerkung,
dass für Zufallsvariablen nahezu alle interessanten Fragen nur durch die Kenntnis der Verteilung beantwortet werden können, ist daher nur mit Einschränkungen auf stochastische Prozesse
übertragbar. Meist versucht man, zu einem gegebenen Wahrscheinlichkeitsmaß Pb auf (E I , E ⊗I )
einen stochastischen Prozess mit Verteilung Pb so zu konstruieren, dass die Pfade so “glatt” oder
“regulär” wie möglich sind, zumindest rechtsseitig stetig mit linksseitigen Grenzwerten. Wir
werden darauf in dieser Vorlesung aber nicht im Detail eingehen.
1.3
Endlich-dimensionale Verteilungen
Die Verteilung eines stochastischen Prozesses ist oft ein recht kompliziertes Objekt und ist meist
nicht – oder nur mit großer Mühe – explizit angebbar. Es stellt sich daher die Frage, ob man
Verteilungen implizit charakterisieren kann, etwa dadurch, dass man lediglich die gemeinsamen
Verteilungen zu endlich vielen Zeitpunkten angibt, was viel leichter und expliziter ist. Die Frage
ist dann, ob dadurch die Verteilung eindeutig festgelegt wird. Dies ist eine Frage nach der eindeutigen Fortsetzbarkeit zu einem Wahrscheinlichkeitsmaß, dessen Werte nur auf einer Teilmenge
der σ-Algebra gegeben sind.
Wir schreiben J < I, falls J eine endliche nichtleere Teilmenge von I ist.
Definition 1.3.1 (Endlich-dimensionale Verteilungen). Sei (X t )t∈I ein stochastischer
Prozess. Die Familie (PbJ )J<I aller (gemeinsamen) Verteilungen PbJ von (Xt )t∈J für alle J < I
heißt Familie der endlich dimensionalen Verteilungen von (X t )t∈I , bzw. von Pb, wenn dies die
Verteilung von (Xt )t∈I ist.
Eine endlich dimensionale Verteilung PbJ ist ein Wahrscheinlichkeitsmaß auf (E J , E ⊗J ). Offenbar ist PbJ durch Pb eindeutig bestimmt. Man kann PbJ als das Bildmaß von Pb unter der
Projektion πJ : (E I , E ⊗I ) → (E J , E ⊗J ) interpretieren, die f ∈ E I auf (πJ f )(j) := f (j) für j ∈ J
abbildet. Diese Abbildung πJ ist messbar.
Eine viel schwierigere Frage ist, unter welchen Umständen eine gegebene Familie von Wahrscheinlichkeitsmaßen PbJ auf (E J , E ⊗J ) mit J < I gerade die Familie der endlich dimensionalen
Verteilungen einer Verteilung Pb sind. Dies wird in dem wichtigen Satz 1.3.3 geklärt werden. Es
stellt sich heraus, dass die PbJ gewisse Konsistenzbedingungen erfüllen müssen:
Definition 1.3.2 (Konsistenz). Sei I eine nichtleere Indexmenge, (E, E) ein Messraum, und
für jedes J < I sei ein Wahrscheinlichkeitsmaß PbJ auf (E J , E ⊗J ) vorgegeben. Die Familie
(PbJ )J<I heißt konsistent, wenn für alle J1 < I und J2 < I mit J1 ⊂ J2 gilt, dass PbJ1 gleich der
Projektion von PbJ2 auf J1 ist.
Ein Beispiel für eine konsistente Folge ist etwa die Folge der Gleichverteilungen aller Nächstnachbarschaftspfade (X0 , . . . , Xn ) ∈ (Zd )n+1 , die in X0 = 0 starten (dies ist nichts Anderes als
die sogenannte gewöhnliche Irrfahrt), und ein Beispiel für eine nicht-konsistente Folge ist die
Folge der Gleichverteilungen auf der Menge aller solchen Pfade mit der Zusatzbedingung, dass
er keinen Punkt mehr als einmal besucht, also dass X i 6= Xj für i, j ∈ {0, 1, . . . , n} mit i 6= j ist
(dies nennt man die selbstvermeidende Irrfahrt).
1.3. ENDLICH-DIMENSIONALE VERTEILUNGEN
7
Es stellt sich in Satz 1.3.3 heraus, dass die geeignete Struktur auf dem Zustandsraum E
für unsere Frage nach der eindeutigen Charakterisierung eines stochastischen Prozesses durch
endlich dimensionale Verteilungen die eines polnischen Raumes ist. Ein polnischer Raum ist
ein vollständiger metrischer Raum mit abzählbarer Basis der Topologie. Falls nicht anders vermerkt, versehen wir einen polnischen Raum immer mit der σ-Algebra der Borelmengen, d. h.
der kleinsten σ-Algebra, die alle offenen Mengen enthält. Polnische Räume haben sich als sehr
natürliche Zustandsräume von stochastischen Prozessen erwiesen. Die meisten interessanten Zustandsräume (E, E) sind polnisch, z. B. R, Rn , Cn , RN , C([0, 1], Rn ).
Der folgende (theoretisch sehr wichtige) Satz stellt klar, dass zu konsistenten Familien von
Wahrscheinlichkeitsmaßen mit Werten in einem polnischen Raum in natürlicher Weise genau ein
stochastischer Prozess gehört.
Satz 1.3.3 (Existenzsatz von Kolmogorov). Wenn E ein polnischer Raum ist, I eine Indexmenge und (PbJ )J<I eine konsistente Familie von Wahrscheinlichkeitsmaßen, dann existiert
genau ein Wahrscheinlichkeitsmaß Pb auf (E I , E ⊗I ), so dass die PbJ die endlich dimensionalen
Verteilungen von Pb sind. Weiter existiert ein Wahrscheinlichkeitsraum und darauf ein stochastischer Prozess (Xt )t∈I mit Zustandsraum (E, E) und Verteilung Pb .
Der Beweis ist zu aufwendig, um ihn hier zu präsentieren. Der interessierte Leser sei auf
[Ba91] verwiesen. Die letzte Aussage ist allerdings recht leicht zu sehen. Man kann als Wahrscheinlichkeitsraum immer (E I , E ⊗I , Pb) wählen und Xi (f ) := f (i) für i ∈ I und f ∈ E I wählen.
Dann ist die in Lemma 1.2.4 definierte Abbildung X gerade die Identität und somit die Verteilung von X gleich Pb .
Eine Konsequenz von Satz 1.3.3 ist, dass, um einen Prozess (X n )n∈N0 oder (Xt )t∈[0,∞) mit
Werten in einem polnischen Raum zu definieren, es ausreicht, für jedes n ∈ N0 nur die Verteilung
des Vektors (X0 , . . . , Xn ) anzugeben bzw. von (Xt0 , . . . , Xtn ) für jede Wahl von 0 ≤ t0 < t1 <
· · · < tn unter der Voraussetzung, dass die Familie der so definierten Verteilungen konsistent ist.
Kapitel 2
Markovketten in diskreter Zeit
In diesem Kapitel behandeln wir einen der wichtigsten stochastischen Prozesse, die Markovketten
auf einem diskreten Raum in diskreter Zeit. Wir werden also immer die Parametermenge I = N 0
wählen, und der Zustandsraum E ist eine beliebige diskrete Menge, also endlich oder höchstens
abzählbar unendlich. Es ist üblich, den Zustandsraum in diesem Fall nicht E, sondern I zu
nennen, und das tun wir hier auch. Im gesamten Kapitel sei I eine nichtleere, endliche oder
höchstens abzählbar unendliche Menge, der Zustandsraum.
Man stelle sich ein Teilchen vor, das sich durch eine höchstens abzählbare Menge I zufällig
bewegt und zu den Zeitpunkten 1, 2, 3, . . . jeweils zu einem (eventuell anderen) Punkt springt.
Die besondere Eigenschaft der Sprungentscheidungen, die die Markoveigenschaft ausmacht, ist
die Tatsache, dass diese Entscheidung nur von der aktuellen Position des Teilchens abhängt,
aber (gegeben, man kennt diese Position) nicht von dem Verlauf des ganzen bisherigen Pfades,
den das Teilchen zurück gelegt hat.
Markovketten spielen eine wichtige Rolle bei der Modellierung vieler zeitlich sich entwickelnder Prozesse: bei Mischungsvorgängen, bei Sortieralgorithmen und anderen stochastischen Algorithmen, bei der Modellierung physikalischer Prozesse oder von Finanzmärkten und Vielem
mehr.
2.1
Definition und einfache Eigenschaften
Wir beginnen mit der Definition der Markoveigenschaft: Selbst wenn der gesamte bisherige
Verlauf bekannt ist, hat nur die aktuelle Position einen Einfluss auf die Sprungentscheidung.
Definition 2.1.1 (Markoveigenschaft). Wir sagen, eine (endliche oder unendliche) Folge
X0 , X1 , X2 , . . . von I-wertigen Zufallsgrößen besitzt die Markoveigenschaft, wenn für jedes n ∈
N und alle i0 , i1 , . . . , in+1 ∈ I gilt:
P(Xn+1 = in+1 | Xn = in , Xn−1 = in−1 , . . . , X0 = i0 ) = P(Xn+1 = in+1 | Xn = in ),
(2.1.1)
sofern alle auftretenden bedingten Wahrscheinlichkeiten wohldefiniert sind.
Das legt nahe, dass eine Markovkette im Wesentlichen durch die bedingten Wahrscheinlichkeiten P(Xn+1 = in+1 | Xn = in ) festgelegt wird. Ihre Kollektion ist also ein ganz wesentliches
Objekt:
9
10
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Definition 2.1.2 (stochastische Matrix).
Eine Matrix P = (p i,j )i,j∈I heißt stochastisch,
P
falls pi,j ∈ [0, 1] für alle i, j ∈ I gilt und j∈I pi,j = 1 für jedes i ∈ I gilt.
Wir werden im Folgenden immer still schweigend davon ausgehen, dass die Koeffizienten
einer stochastischen Matrix P mit p i,j bezeichnet sind.
Die Sprungwahrscheinlichkeiten einer Folge von Zufallsgrößen, die die Markoveigenschaft
besitzt, sind also durch stochastische Matrizen gegeben, die a priori noch von dem Zeitpunkt
des Sprunges abhängen dürfen. Wir werden im Folgenden nur solche Folgen betrachten, deren
Sprungwahrscheinlichkeiten nicht von diesem Zeitpunkt abhängen:
Definition 2.1.3 (Markovkette). Sei P eine stochastische Matrix. Eine (endliche oder unendliche) Folge X0 , X1 , X2 , . . . von I-wertigen Zufallsgrößen heißt eine (zeitlich homogene)
Markovkette mit Übergangsmatrix P , falls für alle n ∈ N und alle i0 , i1 , . . . , in+1 ∈ I mit
P(Xn = in , Xn−1 = in−1 , . . . , X0 = i0 ) > 0 gilt:
P(Xn+1 = in+1 | Xn = in , Xn−1 = in−1 , . . . , X0 = i0 ) = pin ,in+1 .
(2.1.2)
Die Einträge pi,j von P heißen die Übergangswahrscheinlichkeiten, und die Startverteilung ν
der Kette ist definiert durch ν(i) = P(X 0 = i) für i ∈ I.
Eine Startverteilung ist also eine Wahrscheinlichkeitsverteilung, oder kurz eine Verteilung,
auf I, genau wie jede Zeile einer stochastischen Matrix. Wir schreiben auch oft P ν an Stelle
von P, um die Startverteilung zu betonen. Im Fall, dass ν in einem i ∈ I konzentriert ist (also
ν(i) = 1), schreiben wir Pi . Die Elemente von I nennt man auch oft Zustände, die Menge I
selber den Zustandsraum.
Beispiel 2.1.4 (Irrfahrten). Es seien I eine kommutative additive Gruppe (etwa Z d oder
Rd ) und (Yn )n∈N eine Folge unabhängigerP
und identisch verteilter I-wertiger Zufallsgrößen. Wir
betrachten die durch X0 = 0 und Xn = nk=1 Yk definierte Partialsummenfolge (Xn )n∈N0 . Als
Übungsaufgabe beweist man, dass (X n )n∈N0 eine Markovkette ist, deren Übergangsmatrix die
Koeffizienten pi,j = P(Y1 = j − i) besitzt, die also nur von der Differenz der Indizes abhängt.
Man nennt (Xn )n∈N0 eine Irrfahrt auf I (wobei allerdings der englische Begriff random walk
sicherlich sinnvoller ist).
3
Es folgen Charakterisierungen von Markovketten. Notationell ist es angenehm, f ür s < t
den Pfad (Xs , Xs+1 , . . . , Xt ) mit X[s,t] abzukürzen, ebenso schreiben wir für (nicht zufällige)
Vektoren i[s,t] statt (is , is+1 , . . . , it ) ∈ I t−s+1 .
Satz 2.1.5. Es seien (Xn )n∈N0 eine Folge von I-wertigen Zufallsgrößen, ν eine Verteilung auf
I und P eine stochastische Matrix.
(a) (Xn )n∈N0 ist genau dann eine Markovkette mit Übergangsmatrix P und Startverteilung ν,
wenn für alle n ∈ N0 und alle i0 , i1 , . . . , in ∈ I gilt
P(X0 = i0 , X1 = i1 , . . . , Xn = in ) = ν(i0 )pi0 ,i1 pi1 ,i2 · · · pin−1 ,in .
(2.1.3)
(b) Falls (Xn )n∈N0 eine Markovkette ist, so gilt für alle n < m, in ∈ I und alle A ⊂ I n mit
P(X[0,n−1] ∈ A, Xn = in ) > 0 und für alle B ⊂ I m−n :
P(X[n+1,m] ∈ B | X[0,n−1] ∈ A, Xn = in ) = P(X[n+1,m] ∈ B | Xn = in ).
(2.1.4)
2.1. DEFINITION UND EINFACHE EIGENSCHAFTEN
11
Beweis. (a) Der Beweis von (2.1.3) wird leicht mit einer Vollständigen Induktion über n geführt,
und eine Folge (Xn )n∈N0 , die (2.1.3) für alle n ∈ N0 und alle i0 , i1 , . . . , in ∈ I erfüllt, wird mit
Hilfe der Definition der bedingten Wahrscheinlichkeit leicht als eine Markovkette identifiziert.
(b) Mit Hilfe der Definition der bedingten Wahrscheinlichkeit und Teil (a) errechnet man
P(X[n+1,m] ∈ B, X[0,n−1] ∈ A, Xn = in )
P(X[n+1,m] ∈ B | X[0,n−1] ∈ A, Xn = in ) =
P(X[0,n−1] ∈ A, Xn = in )
P
P
i[n+1,m] ∈B
i[0,n−1] ∈A ν(i0 )pi0 ,i1 · · · pim−1 ,im
P
=
i[0,n−1] ∈A ν(i0 )pi0 ,i1 · · · pin−1 ,in
X
=
pin ,in+1 pin+1 ,in+2 · · · pim−1 ,im .
i[n+1,m] ∈B
Der Ausdruck auf der rechten Seite hängt nicht von A ab. Wir können insbesondere A = I n
setzen und erhalten
X
P(X[n+1,m] ∈ B | Xn = in ) =
pin ,in+1 pin+1 ,in+2 · · · pim−1 ,im .
i[n+1,m] ∈B
Wenn wir dies in der obigen Rechnung wieder einsetzen, ist der Beweis von (2.1.4) beendet.
Die Aussage in (b) kann man auch einprägsam wie folgt formulieren:
Korollar 2.1.6 (Unabhängigkeit von Zukunft und Vergangenheit bei gegebener Gegenwart). Falls (Xn )n∈N0 eine Markovkette ist, so gilt für alle n < m, in ∈ I mit P(Xn = in ) >
0 und alle A ⊂ I n und B ⊂ I m−n :
P(X[0,n−1] ∈ A, X[n+1,m] ∈ B | Xn = in ) = P(X[0,n−1] ∈ A | Xn = in )P(X[n+1,m] ∈ B | Xn = in ).
(2.1.5)
Beweis. Im Fall P(X[0,n−1] ∈ A, Xn = in ) > 0 ergibt sich (2.1.5) direkt aus (2.1.4) nach
Multiplikation mit P(X[0,n−1] ∈ A | Xn = in ). Ansonsten steht Null auf beiden Seiten von
(2.1.5), und die Aussage gilt trivialerweise.
Man überlege sich an einem Beispiel, dass die Aussage von Korollar 2.1.6 im Allgemeinen
falsch wird, wenn man das Ereignis {X n = in } ersetzt durch {Xn ∈ C} für beliebige Teilmengen
C von I.
Wir schneiden kurz die Frage der Existenz und Konstruktion von Markovketten an.
Bemerkung 2.1.7 (Konstruktion von Markovketten). Eine endlich lange Markovkette
(X0 , X1 , . . . , Xn ) im Sinne von Definition 2.1.3 kann leicht auf einem diskreten Wahrscheinlichkeitsraum konstruiert werden. Wir setzen Ω n = I n+1 und definieren die Einzelwahrscheinlichkeiten als p((i0 , . . . , in )) = ν(i0 )pi0 ,i1 . . . pin−1 ,in , wobei ν eine Verteilung auf I ist und P eine
stochastische Matrix. Dann bilden die Projektionsabbildungen X i : I n+1 → I eine Markovkette
mit Startverteilung ν und Übergangsmatrix P .
Man beachte, dass dieser Wahrscheinlichkeitsraum von der Länge der Kette abhängt und
dass man genauer Pn statt P für das induzierte Wahrscheinlichkeitsmaß schreiben müsste. Allerdings überzeugt man sich leicht davon, dass die ersten n + 1 Zufallsgrößen einer Markovkette
der Länge m > n selber eine Markovkette der Länge n bilden. Mit anderen Worten, man kann
12
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
leicht zeigen, dass die so konstruierte Folge von Wahrscheinlichkeitsmaßen konsistent ist, siehe
Definition 1.3.2. Nach dem Existenzsatz 1.3.3 von Kolmogorov existiert eine unendliche lange
Markovkette, deren n-schrittiger Beginn gerade die oben konstruierten endlich langen Ketten
sind.
Bei der Untersuchung einer Markovkette in endlicher Zeit reicht es also für viele Zwecke aus,
eine genügend späte Zeit m zu fixieren und den für dieses m konstruierten Wahrscheinlichkeitsraum zu Grunde zu legen. Wir werden daher im Folgenden aus Bequemlichkeit immer von einer
unendlich langen Markovkette ausgehen und den benutzten Wahrscheinlichkeitsraum nicht mit
einer endlichen Länge indizieren.
3
Der Zusammenhang zwischen dem Markovschen Mechanismus und der Matrixmultiplikation
ist sehr eng, wie wir uns kurz klar machen wollen.
Bemerkung 2.1.8 (Potenzen stochastischer Matrizen). Stochastische Matrizen P und Q
kann man ohne Probleme im Sinne der Matrixmultiplikation mit einander multiplizieren, und
das Produkt ist ebenfalls eine stochastische Matrix. Die Koeffizienten der n-ten Potenz P n von
0
P bezeichnen wir mit P n = (p(n)
i,j )i,j∈I . Es ist P = (δi,j )i,j∈I die Einheitsmatrix, wobei δ i,j das
Kroneckersymbol bezeichnet. Wenn man die Gleichung P n P m = P n+m ausschreibt, erhält man
die sogenannten Chapman-Kolmogorov-Gleichungen:
=
p(n+m)
i,j
X
(m)
p(n)
i,k pk,j ,
i, j ∈ I.
(2.1.6)
k∈I
Insbesondere haben wir
(m)
p(n+m)
≥ p(n)
i,j
i,k pk,j ,
i, j, k ∈ I, n, m ∈ N0 .
(2.1.7)
n
Auf Grund des folgenden Lemmas 2.1.9 nennt man die Koeffizienten p (n)
i,j von P auch die nstufigen Übergangswahrscheinlichkeiten.
3
Wir stellen uns eine Verteilung ν als Zeilenvektoren vor (wie auch z. B. die Zeilen
P einer stochastischen Matrix), so dass das Matrixprodukt νP wohldefiniert ist, also (νP ) j = i∈I ν(i)pi,j .
Lemma 2.1.9. Es sei (Xn )n∈N0 eine Markovkette mit Startverteilung ν und Übergangsmatrix P .
Dann gilt Pν (Xn = j) = (νP n )j für alle n ∈ N und alle j ∈ I. Insbesondere gilt P i (Xn = j) = p(n)
i,j
für alle i, j ∈ I.
Beweis. Wir summieren die Gleichung (2.1.3) (mit j = i n ) über alle i0 , . . . , in ∈ I und beachten
die Regeln der Matrixmultiplikation.
Die Verteilung einer Markovkette zum Zeitpunkt n ist also nichts Anderes als die n-te Potenz
der Übergangsmatrix, multipliziert von links mit der Startverteilung. Wir halten noch fest, wie
sich dies auf zeitliche Verschiebung auswirkt:
Korollar 2.1.10. Es sei (Xn )n∈N0 eine Markovkette mit Übergangsmatrix P . Dann gilt für alle
n, m ∈ N0 und alle i, j ∈ I mit P(Xm = i) > 0:
P(Xm+n = j | Xm = i) = p(n)
i,j .
13
2.2. BEISPIELE
2.2
Beispiele
Ein sehr allgemeines Prinzip, nach dem man Markovketten konstruieren kann (siehe Übungsaufgabe), ist das folgende. Mit einer Folge von unabhängigen identisch verteilten Zufallsgrößen
Y1 , Y2 , Y3 , . . . mit Werten in einer beliebigen abzählbaren Menge J und mit einer Funktion
f : I × J → I setzt man rekursiv Xn+1 = f (Xn , Yn+1 ) für n ∈ N0 . Die Kette wird also rekursiv
fortgesetzt, indem man den aktuellen Wert der Kette mit einem festgelegten Mechanismus einem
unabhängigen Zufall unterwirft.
Beispiel 2.2.1 (unabhängige identisch verteilte Folgen). Wenn (X n )n∈N0 eine Folge unabhängiger und identisch verteilter I-wertiger Zufallsgrößen ist, so ist sie auch eine Markovkette. Die Übergangsmatrix ist gegeben durch p i,j = qj für alle i, j ∈ I, wobei q die Verteilung
von X0 ist. Natürlich ist q auch die Startverteilung. Andersherum ist eine Markovkette, deren
Übergangsmatrix identische Zeilen besitzt (d. h. deren p i,j nicht von i abhängen), eine Folge
unabhängiger und identisch verteilter Zufallsgrößen.
3
Beispiel 2.2.2 (Irrfahrten auf Gruppen). Es sei I = G eine abzählbare Gruppe, die wir
multiplikativ schreiben wollen und nicht unbedingt als kommutativ voraus setzen wollen. Ferner
sei µ eine beliebige Verteilung auf G. Wir definieren p g,h = µ(g −1 h) für alle g, h ∈ G. Wegen der
Gruppeneigenschaft ist für jedes g die Abbildung h 7→ g −1 h bijektiv auf G, und es gilt
X
X
X
pg,h =
µ(g −1 h) =
µ(h0 ) = 1,
h∈G
h∈G
h0 ∈G
also ist P = (pg,h )g,h∈G eine stochastische Matrix. Die zugehörige Markovkette heißt die µIrrfahrt auf G. Dieses Beispiel ist die multiplikative Variante der Irrfahrt von Beispiel 2.1.4 (bis
auf die dort voraus gesetzte Kommutativität). Mit Hilfe einer Folge von unabhängigen, nach
µ verteilten Zufallsgrößen Y1 , Y2 , Y3 , . . . erhält man eine µ-Irrfahrt, indem man rekursiv setzt:
X0 = 1 und Xn+1 = Xn Yn , denn dann gilt für alle n ∈ N0 und alle g, h ∈ G mit P(Xn = g) > 0:
P(Xn+1 = h | Xn = g) = P(gYn = h) = µ(g −1 h) = pg,h .
Die Wahl von I = G als die Menge der Permutationen einer endlichen Menge führt zum
Beispiel auf ein Modell für die Mischung eines Kartenstapels; man beachte, dass diese Gruppe
nicht kommutativ ist.
3
Beispiel 2.2.3 (eindimensionale Irrfahrt). Der folgende Spezialfall von Beispiel 2.1.4 wird
die eindimensionale Irrfahrt genannt. Setze I = Z, und Y n nehme die Werte 1 und −1 mit
Wahrscheinlichkeiten p und q = 1 − p an, wobei p ∈ [0, 1] ein Parameter sei. Dann beschreibt
die Markovkette (Xn )n∈N0 den Weg eines Teilchens durch die diskrete Achse mit unabhängigen
Sprüngen, wobei es zu jedem Zeitpunkt mit Wahrscheinlichkeit p um eine Einheit nach rechts
springt und sonst nach links. Die Übergangsmatrix besitzt die Einträge p auf der rechten Nebendiagonalen und 1 − p auf der linken, ansonsten besteht sie aus Nullen. Im Fall p = 12 wird
die Irrfahrt symmetrisch genannt.
3
Beispiel 2.2.4 (Irrfahrt auf Zd ). Die d-dimensionale Variante von Beispiel 2.2.3 (die ebenfalls
ein Spezialfall von Beispiel 2.1.4 ist) ist auf I = Z d gegeben, indem die Übergangsmatrix durch
1
für |i − j| = 1 fest gelegt wird. (Hier ist | · | die ` 1 -Norm auf Zd .) Die zugehörige Marpi,j = 2d
kovkette beschreibt einen Nächstnachbarschaftspfad durch Zd , wobei jeder Nachbar mit gleicher
Wahrscheinlichkeit ausgewählt wird, unabhängig von allen anderen Sprungentscheidungen. 3
14
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Beispiel 2.2.5 (Irrfahrten auf {0, . . . , N }). Ähnlich wie in Beispiel 2.2.3 soll ein Sprung
innerhalb von I = {0, . . . , N } mit Wahrscheinlichkeit p zum rechten Nachbarn und mit Wahrscheinlichkeit 1−p zum linken ausgeführt werden. Für die Sprungentscheidungen an den Rändern
0 und N müssen wir allerdings gesonderte Vereinbarungen treffen, und es gibt dafür mehrere
Möglichkeiten. Ein Randpunkt, sagen wir 0, heißt absorbierend, falls p 0,0 = 1 gilt, falls also das
springende Teilchen nie mehr von der 0 sich entfernen kann. Im Fall p 0,1 = 1, wenn also das
Teilchen sofort wieder unweigerlich zurück springen muss, heißt der Randpunkt 0 reflektierend.
3
Beispiel 2.2.6 (Polyas Urnenschema). In einer Urne liegen gewisse (endliche) Anzahlen roter
und schwarzer Kugeln. Zu jedem Zeitpunkt wird eine Kugel zufällig gezogen und zusammen mit
einer neuen Kugel der selben Farbe in die Urne zurück gelegt. Dann bildet das Paar der Anzahlen
der roten und der schwarzen Kugeln zu den Zeitpunkten 0, 1, 2, . . . eine Markovkette auf N 20 . Die
r
s
Übergangswahrscheinlichkeiten sind gegeben durch p (r,s),(r+1,s) = r+s
und p(r,s),(r,s+1) = r+s
;
alle anderen sind Null.
3
Beispiel 2.2.7 (Ehrenfests Urnenmodell). Insgesamt N Kugeln liegen in zwei Urnen. Zu
jedem Zeitpunkt 1, 2, . . . wählen wir eine der Kugeln mit gleicher Wahrscheinlichkeit und lassen
sie die Urne wechseln. Dann ist die Anzahl der Kugeln in der linken Urne zum Zeitpunkt n eine
Markovkette auf I = {0, . . . , N } im Zeitparameter n. Die Übergangsmatrix P ist gegeben durch
pk,k−1 = Nk und pk,k+1 = 1 − Nk , und alle anderen Übergangswahrscheinlichkeiten sind Null.
Siehe Beispiel 2.7.4 für interessante Eigenschaften dieses Modells.
3
Beispiel 2.2.8 (Bernoulli-Laplace-Diffusionsmodell). In zwei Behältern A und B befinden
sich insgesamt w weiße und s schwarze Kugeln, wobei s Kugeln in A liegen, und es sei w ≤ s.
Zu den diskreten Zeitpunkten n = 1, 2, 3, . . . wird jeweils in A und in B eine Kugel zufällig
ausgewählt und in den jeweils anderen Behälter gelegt. Dann ist die Anzahl der weißen Kugeln
in A eine Markovkette auf {0, 1, . . . , w} im Zeitparameter n. Siehe Beispiel 2.5.9 f ür interessante
Eigenschaften dieses Modells.
3
Beispiel 2.2.9 (Irrfahrten-Maxima). Falls (S n )n∈N0 eine Irrfahrt auf Z wie in Beispiel 2.1.4
ist, dann bildet die Folge der Maxima M n = max{S0 , S1 , . . . , Sn } im Allgemeinen keine Mar3
kovkette, aber die Folge (Mn , Sn )n∈N0 der Paare (Übungsaufgabe).
Beispiel 2.2.10 (Verzweigungsprozesse). Wir nehmen an, dass zur Zeit n = 0 ein Individuum existiert, das mit Wahrscheinlichkeit p k ∈ [0, 1] genau k ∈ N0 Nachkommen produziert.
Jeder der Nachkommen produziert wieder unabhängig voneinander Nachkommen mit derselben Verteilung. Sei Sn die Zahl der Individuen in der n-ten Generation. Offenbar ist (S n )n∈N0
eine Markovkette mit Zustandsraum N 0 und Startwert 1. Ein solcher Prozess heißt GaltonWatson-Prozess. Wir können diesen Prozess auch wie folgt konstruieren. Sei ξ i(n) die Anzahl der
Nachkommen des i-ten Individuums der n-ten Generation, dann gilt
Sn+1 =
Sn
X
ξi(n) ,
n ∈ N.
i=1
Wir können annehmen, dass die Familie (ξ i(n) )n∈N0 ,i∈N u. i. v. ist. Damit ist der Galton-WatsonProzess von der Form, die wir am Beginn dieses Abschnitts erwähnten.
3
2.3. KLASSENEIGENSCHAFTEN, REKURRENZ, TRANSIENZ
2.3
15
Klasseneigenschaften, Rekurrenz, Transienz
In diesem Abschnitt sei P eine stochastische Matrix auf I. Wir wollen die Frage untersuchen, ob
die zugehörige Markovkette gegebene Punkte in I mit Sicherheit besucht oder nicht. Es wird sich
in diesem Abschnitt heraus stellen, dass der Zustandsraum zerlegt werden kann in rekurrente
und transiente Klassen. Eine in einer rekurrenten Klasse gestartete Markovkette verlässt die
Klasse nie und besucht jeden Punkt dieser Klasse mit Sicherheit.
Wir müssen zunächst die Frage untersuchen, ob ein gegebener Punkt überhaupt mit positiver
Wahrscheinlichkeit jemals erreicht werden kann. Diese Unterscheidung induziert auf nat ürliche
Weise eine Einteilung von I in Klassen.
Definition 2.3.1 (erreichbar). Ein Punkt j ∈ I heißt von einem Punkt i ∈ I aus erreichbar,
falls ein n ∈ N0 existiert mit p(n)
j. Falls i
j und j
i, so
i,j > 0. Wir schreiben dann i
schreiben wir i ! j.
Bemerkung 2.3.2 (! als Äquivalenzrelation). Die Relation
auf I ist reflexiv und
transitiv, denn wegen p(0)
=
1
gilt
i
i
für
jedes
i
∈
I,
und
falls
i
j
und j
k gelten, so
i,i
folgt aus (2.1.7) leicht, dass auch i
k gilt. Also ist ! eine Äquivalenzrelation auf I und teilt I
folglich in Klassen ein. Für zwei Klassen A, B ⊂ I schreiben wir A
B, falls es i ∈ A und j ∈ B
gibt mit i
j, und wir sagen dann, dass B von A aus erreichbar ist. (Offensichtlich ist diese
Sprechweise wohldefiniert, d. h. die Definition unabhängig von den gewählten Repräsentanten.)
3
Definition 2.3.3 (abgeschlossen, irreduzibel). (a) Eine Teilmenge J von I heißt abgeschlossen, wenn J 6 I \ J gilt, d. h. wenn keine zwei Elemente j ∈ J und i ∈ I \ J
existieren mit j
i.
(b) P heißt irreduzibel, falls I aus einer einzigen Klasse besteht, d. h. wenn je zwei Elemente
aus I äquivalent sind.
Man sieht leicht, dass die Einschränkung PJ = (pi,j )i,j∈J von P auf eine abgeschlossene
Klasse J von I ihrerseits eine stochastische Matrix auf J ist. Falls P irreduzibel ist, so existieren
keine abgeschlossenen echten Teilmengen von I.
Beispiel 2.3.4.
(a) Die symmetrische Irrfahrt auf Z d ist irreduzibel.
(b) In Polyas Urnenschema (siehe Beispiel 2.2.6) sind keine zwei Elemente aus I = N 20 äquivalent. Für jede r0 , s0 ∈ N ist die Menge {(r, s) ∈ I : r ≥ r0 , s ≥ s0 } abgeschlossen.
(c) Die Irrfahrt auf {0, . . . , n} (siehe Beispiel 2.2.5) mit absorbierenden Rändern besitzt die
Äquivalenzklassen {0}, {1, . . . , n−1} und {n}. Die Mengen {0} und {n} sind abgeschlossen,
und es gelten {1, . . . , n − 1}
{0} und {1, . . . , n − 1}
{n}.
3
Es sei (Xn )n∈N0 die zur stochastischen Matrix gehörige Markovkette. Wir führen nun die
Ersteintrittszeit von i ∈ I ein:
Ti = inf{n ∈ N : Xn = i}.
(2.3.1)
Falls die Kette den Punkt i gar nicht besucht, dann setzen wir T i = ∞. Man beachte, dass die
Definition von Ti die gesamte unendlich lange Kette (X n )n∈N0 erfordert, deren Konstruktion wir
16
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
noch nicht durchgeführt haben (siehe Bemerkung 2.1.7). Allerdings hängt das Ereignis {Ti = n}
nur von der Zeit bis n ab, kann also mit unseren Mitteln korrekt behandelt werden. Wir definieren
(n)
fi,j
= Pi (Tj = n) = Pi (X1 6= j, X2 6= j, . . . , Xn−1 6= j, Xn = j),
i, j ∈ I, n ∈ N.
(2.3.2)
(n)
In Worten: fi,j
ist die Wahrscheinlichkeit, dass eine in i gestartete Kette zum Zeitpunkt n den
Punkt j zum ersten Mal trifft. Die Summe
fi,j =
∞
X
(n)
fi,j
(2.3.3)
n=1
liegt in [0, 1], da die Ereignisse {T j = 1}, {Tj = 2}, . . . disjunkt sind. Man kann (und sollte) die
unendliche Summe fi,j als Pi (Tj < ∞) interpretieren, d. h. als die Wahrscheinlichkeit, dass eine
in i gestartete Kette jemals den Punkt j besucht.
Satz 2.3.5 (Erneuerungsgleichung). Es gilt
p(n)
i,i =
n
X
(k) (n−k)
fi,i
pi,i ,
n ∈ N, i ∈ I.
(2.3.4)
k=1
Beweis. Gemäß Lemma 2.1.9 gilt p(n)
i,i = Pi (Xn = i). Wir spalten das Ereignis {X n = i} nach
dem ersten Zeitpunkt, an dem die Kette i erreicht, auf und erhalten
p(n)
i,i =
n
X
Pi (Ti = k, Xn = i) =
k=1
n
X
(k)
Pi (Xn = i | X1 6= i, . . . , Xk−1 6= i, Xk = i)fi,i
.
k=1
Nun wenden wir (2.1.4) und Korollar 2.1.10 an und erhalten
(n)
pi,i =
n
X
(k)
Pi (Xn = i | Xk = i)fi,i =
k=1
n
X
(k) (n−k)
fi,i
pi,i .
k=1
Nun kommen wir zu weiteren zentralen Begriffen der Theorie der Markovketten.
Definition 2.3.6 (Rekurrenz, Transienz). Ein Zustand i ∈ I heißt rekurrent, falls f i,i = 1,
und transient sonst.
Interpretationsgemäß heißt also i rekurrent, falls die in i gestartete Kette mit Sicherheit wieder irgendwann einmal zu i zurück kehrt. Wir können diese Eigenschaft in Termen der Potenzen
von P charakterisieren:
Satz 2.3.7. Ein Zustand i ∈ I ist genau dann rekurrent, wenn
P
n∈N0
p(n)
i,i = ∞ gilt.
Beweis. Für jedes s ∈ (0, 1) erhalten wir aus der Erneuerungsgleichung (siehe Satz 2.3.5)
X
n
p(n)
i,i s = 1 +
n∈N0
X
sn p(n)
i,i = 1 +
n∈N
=1+
X
k∈N
(k) k
fi,i
s
X
n∈N0
X
sn
n∈N
n
p(n)
i,i s .
n
X
k=1
(k) (n−k)
fi,i
pi,i = 1 +
X
k∈N
(k) k
fi,i
s
∞
X
n=k
p(n−k)
sn−k
i,i
2.3. KLASSENEIGENSCHAFTEN, REKURRENZ, TRANSIENZ
Also haben wir für die beiden Funktionen
X (n)
pi,i sn
π(s) =
und
φ(s) =
X
17
(k) k
fi,i
s
k∈N
n∈N0
die Beziehung π(s) = 1+π(s)φ(s) hergeleitet. Im Fall 1 = f i,i = φ(1) machen
P wir den Grenzübergang s ↑ 1 und erhalten π(1) = 1 + π(1), was natürlich impliziert, dass n∈N0 p(n)
i,i = π(1) = ∞.
1
Falls fi,i < 1, so formen wir zunächst um zu π(s) = 1−φ(s) und lassen dann s ↑ 1, was auf
P
(n)
1
n∈N0 pi,i = 1−fi,i < ∞ führt und den Beweis beendet.
Die in Satz 2.3.7 auftretende Reihe kann interpretiert werden:
X
X
X (n)
1l{Xn =i} ,
Ei (1l{Xn =i} ) = Ei
pi,i =
n∈N0
n∈N0
n∈N0
also ist sie gleich der erwarteten Anzahl der Besuche in i für die unendlich lange in i gestartete
Markovkette. Der Zustand i ist also nach Satz 2.3.7 genau dann transient, wenn diese Kette
ihren Startpunkt erwartungsgemäß nur endlich oft besucht.
Rekurrenz und Transienz sind Klasseneigenschaften:
Satz 2.3.8. Es seien i, j ∈ I mit i ! j. Dann ist i genau dann rekurrent, wenn j es ist.
Beweis. Übungsaufgabe.
Also können und werden wir in Zukunft auch von rekurrenten bzw. transienten Klassen
sprechen und bei Irreduzibilität von rekurrenten bzw. transienten Markovketten. Das Kriterium
aus Satz 2.3.7 kann man benutzen, um beispielsweise die Rekurrenz der d-dimensionalen Irrfahrt
aus Beispiel 2.2.4 zu entscheiden:
Satz 2.3.9. Die d-dimensionale symmetrische Irrfahrt auf Z d ist rekurrent für d ∈ {1, 2} und
transient für d ≥ 3.
Beweisskizze.
Wegen der Verschiebungsinvarianz genügt es, die Divergenz bzw. Konvergenz der
P
(n)
Reihe n∈N p(n)
0,0 zu untersuchen. Wir sind in der glücklichen Lage, den Wert von p 0,0 ausrechnen
zu können. Natürlich ist immer p(2n−1)
= 0 für alle n ∈ N.
0,0
−2n
(2n)
In d = 1 ist leicht zu sehen, dass p0,0 = 2n
2
für alle n ∈ N, und Stirlings Formel zeigt,
P n (n)
(2n)
−1/2
dass p0,0 ∼ (πn)
für n → ∞. Also ist n∈N p0,0 = ∞ für d = 1.
In d = 2 schreiben wir Xn = (Xn(1) , Xn(2) ) für die beiden Komponenten und nutzen die Beobachtung aus, dass die beiden Folgen (X n(1) − Xn(2) )n∈N0 und (Xn(1) + Xn(2) )n∈N0 zwei unabhängige
2n −2n 2
eindimensionale symmetrische Irrfahrten auf Z sind. Folglich ist p (2n)
, und wie
0,0 =
n 2
1
oben sieht man, dass dies sich wie πn verhält, also ebenfalls nicht summierbar ist.
Den Fall d ≥ 3 kann man auf den Grenzfall d = 3 zurück führen. Im Fall d = 3 stellt man
den Wert von p(2n)
0,0 mit Hilfe einer Doppelsumme dar (nach einer Aufspaltung, wieviele Schritte
jeweils in die drei Dimensionsrichtungen geschehen) und schätzt diese mit einiger Arbeit geeignet
−3/2 ist.
ab, bis man sieht, dass p(2n)
0,0 von der Ordnung n
Im Folgenden zeigen wir insbesondere, dass die Markovkette, wenn sie in einer rekurrenten
Klasse gestartet wird, jeden Zustand in dieser Klasse mit Sicherheit besucht, siehe Lemma 2.3.13.
Zunächst ziehen wir eine Folgerung aus der Erneuerungsgleichung.
18
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Lemma 2.3.10. Für alle i, j ∈ I gilt
X
p(n)
i,j = fi,j
n∈N0
X
p(n)
j,j .
n∈N0
Beweis. Genau wie im Beweis der Erneuerungsgleichung (Satz 2.3.5) leitet man die Beziehung
p(n)
i,j =
n
X
(k) (n−k)
fi,j
pj,j
k=1
für alle n ∈ N her. Nun summiert man diese Beziehung über n ∈ N, vertauscht auf der rechten Seite die beiden Summationen und verschiebt die eine davon (ähnlich wie im Beweis von
Satz 2.3.7).
Korollar 2.3.11. Für alle i, j ∈ I gilt:
j transient
=⇒
X
p(n)
i,j < ∞.
n∈N0
Aus dem folgenden Ergebnis folgt insbesondere, dass Klassen, die nicht abgeschlossen sind,
zwangsläufig transient sind. (Abgeschlossene Klassen können hingegen sowohl rekurrent als auch
transient sein.)
Lemma 2.3.12. Es seien i, j ∈ I mit i
dann ebenfalls rekurrent.
j. Falls i rekurrent ist, so gilt auch j
i, und j ist
Beweis. Wir dürfen i 6= j annehmen. Wir führen einen Widerspruchsbeweis und nehmen an,
dass i nicht von j aus erreichbar ist, d. h. dass p (n)
j,i = 0 für alle n ∈ N0 ist.
Sei N ∈ N die kleinste Zahl n mit p(n)
i,j > 0. Für alle n ∈ N gilt dann Pi (XN = j, Xn = i) = 0,
) (n)
denn für n > N gilt ja Pi (XN = j, Xn = i) = p(N
i,j pj,i = 0, und für n < N gilt Pi (XN = j, Xn =
(N −n)
i) = p(n)
= 0, denn N ist ja das kleinste n mit p(n)
i,i pi,j
i,j > 0. Daher haben wir
Pi (Ti ≤ M, XN = j) =
M
X
n=1
Pi (Ti = n, XN = j) ≤
M
X
Pi (Xn = i, XN = j) = 0.
n=1
Also folgt
M
X
(n)
)
fi,i
= Pi (Ti ≤ M ) = Pi (Ti ≤ M, XN 6= j) ≤ Pi (XN 6= j) = 1 − Pi (XN = j) = 1 − p(N
i,j .
n=1
Nun lassen wir M ↑ ∞ und beachten, dass die rechte Seite der Abschätzung
nicht von M
P
(n)
)
abhängt. Mit der Rekurrenz von i folgt der Widerspruch 1 = f i,i = n∈N fi,i ≤ 1 − p(N
i,j < 1.
Insbesondere sind rekurrente Klassen abgeschlossen. (Transiente Klassen müssen nicht abgeschlossen sein.) Insbesondere ist die Einschränkung von P auf eine rekurrente Klasse (siehe
die Bemerkung nach Definition 2.3.3) wieder eine stochastische Matrix, die dann nat ürlich auch
irreduzibel ist. Daher lassen sich also die einzelnen rekurrenten Klassen getrennt diskutieren.
19
2.4. STOPPZEITEN UND DIE STARKE MARKOV-EIGENSCHAFT
Lemma 2.3.13. Wenn i und j in der selben rekurrenten Klasse liegen, so gilt f i,j = fj,i = 1.
Beweis. Wir dürfen i 6= j annehmen. Sei N das kleinste n ∈ N mit p (n)
j,i > 0. Für M > N gilt
Pj (Tj ≤ M, XN = i) =
=
M
X
Pj (Tj = n, XN = i)
n=1
N
−1
X
(n) (N −n)
fj,j
pj,i
+
n=1
M
X
(n−N )
Pj (Tj ≥ N, XN = i)fi,j
.
n=N +1
(N −n)
Nach Definition ist aber pj,i
= 0 für jedes n ∈ {1, . . . , N − 1}, also ist die erste Summe auf
)
der rechten Seite gleich Null. In der zweiten schätzen wir ab: Pj (Tj ≥ N, XN = i) ≤ p(N
j,i , also
erhalten wir aus der obigen Rechnung
Pj (Tj ≤ M, XN = i) ≤
M
X
) (n−N )
)
p(N
≤ p(N
j,i fi,j
j,i fi,j .
n=N +1
Nun lassen wir M ↑ ∞ und beachten, dass lim M →∞ Pj (Tj ≤ M ) = limM →∞
1, also folgt
)
(N )
p(N
j,i = Pj (XN = i) = lim Pj (Tj ≤ M, XN = i) ≤ pj,i fi,j .
PM
(k)
k=1 fj,j
= fj,j =
M →∞
(N )
Wegen fi,j ≤ 1 und pj,i > 0 ergibt sich fi,j = 1, und dies beendet den Beweis.
Ein sehr handliches und simples hinreichendes Kriterium für Rekurrenz ist das Folgende.
Satz 2.3.14. Wenn I endlich ist, so ist jede irreduzible Kette rekurrent.
P
(n)
Beweis. Wegen
j∈I pi,j = 1 für jedes n ∈ N und jedes i ∈ I folgt, dass zu jedem i ein j
P
P
P
(n)
existiert mit n∈N p(n)
j∈I ( n∈N pi,j ) = ∞, und irgendeiner der endlich
i,j = ∞, denn es gilt ja
P
P
(n)
vielen Summanden n∈N p(n)
i,j muss gleich ∞ sein. Aus Lemma 2.3.10 folgt
n∈N pj,j = ∞, und
es folgt die Rekurrenz von j.
2.4
Stoppzeiten und die starke Markov-Eigenschaft
Stoppzeiten sind zufällige Zeiten, die nicht in die Zukunft blicken können. Im Zusammenhang
mit Markovketten sind Stoppzeiten die Eintrittszeitpunkte gewisser Ereignisse, deren Eintreten
durch die bisherige ‘Geschichte’ der Kette beurteilt werden kann.
Im Folgenden sei (Xn )n∈N0 eine Markovkette auf I mit Übergangsmatrix P . In diesem
Abschnitt empfiehlt es sich anzunehmen, dass alle Zufallsgrößen Xn mit n ∈ N auf einem gemeinsamen Wahrscheinlichkeitsraum Ω definiert sind, und das werden wir tun.
Definition 2.4.1 (Filtrierung, Stoppzeit). (a) Für jedes n ∈ N0 sei Fn die Menge der
Ereignisse von der Form {ω ∈ Ω : X[0,n] (ω) ∈ B} mit B ⊂ I n+1 , d. h. die Menge der
Ereignisse, die mit Hilfe der Zufallsgrößen X0 , . . . , Xn beschrieben werden können. Die
Familie F = (Fn )n∈N0 nennt man die zu (Xn )n∈N0 gehörige Filtrierung.
20
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
(b) Eine Abbildung T : Ω → N0 ∪{∞} heißt eine Stoppzeit, wenn für jedes n ∈ N0 das Ereignis
{T = n} in Fn liegt.
Eine Filtrierung ist immer aufsteigend, denn es gilt ja F n ⊂ Fn+1 für jedes n. Das Ereignis
{T = ∞} kann man interpretieren als das Ereignis, dass die Stoppzeit T nie eintritt. Ein Beispiel
von Stoppzeiten sind die Ersteintrittszeiten T i = inf{n ∈ N : Xn = i} in einen Punkt i für eine
Markovkette (Xn )n∈N0 . Etwas allgemeiner definiert man die Ersteintrittszeit in eine nichtleere
Menge A ⊂ I als
TA = inf{n ∈ N : Xn ∈ A}.
Falls man den Zeitpunkt 0 einbeziehen möchte, benutzt man die Stoppzeit
SA = inf{n ∈ N0 : Xn ∈ A}.
Falls i ∈ A, so gilt Pi (SA = 0) = 1. Ferner gilt für i ∈
/ A die Beziehung Pi (TA = SA ) = 1.
Wir beginnen mit einer technischen Vorbereitung.
Lemma 2.4.2. Für alle i ∈ I, n ∈ N0 und alle nichtleeren A ⊂ I gilt
X
Pi (TA ≤ n + 1) =
pi,j Pj (SA ≤ n).
j∈I
Beweis. Übungsaufgabe.
Sei A ⊂ I nicht leer. Die Funktion hA : I → [0, 1], definiert durch
hA (i) = Pi (SA < ∞),
spielt in der Theorie der Markovketten eine wichtige Rolle. Insbesondere ist sie die minimale
Lösung eines gewissen Systems von linearen Gleichungen:
Satz 2.4.3. Sei A ⊂ I nicht leer. Dann ist h A die kleinste Funktion I → [0, ∞), die das
Gleichungssystem
X
hA (i) =
pi,j hA (j),
i ∈ I \ A,
j∈I
löst mit Randbedingung hA (i) = 1 für alle i ∈ A.
Beweis. Dass hA die Randbedingung hA (i)
P = 1 für alle i ∈ A erfüllt, ist klar. Sei nun i ∈ I \ A,
und wir wollen die Gleichung hA (i) =
j∈I pi,j hA (j) beweisen. Zunächst benutzen wir die
Markoveigenschaft zum Zeitpunkt 1, um zu sehen, dass für alle N ∈ N gilt:
X
Pi (1 ≤ SA ≤ N ) =
Pi (X1 = j, 1 ≤ SA ≤ N )
j∈I
=
X
Pi (X1 = j)Pi (1 ≤ SA ≤ N | X1 = j)
j∈I
=
X
pi,j Pj (0 ≤ SA ≤ N − 1).
j∈I
Nun lassen wir auf beiden Seiten N → ∞ gehen und beachten, dass h A (i) = Pi (SA < ∞) =
limN →∞ Pi (1 ≤ SA ≤ N ). Da die Summanden der rechten Seite, P j (0 ≤ SA ≤ N − 1), monoton
2.4. STOPPZEITEN UND DIE STARKE MARKOV-EIGENSCHAFT
21
gegen hA (j) konvergieren, dürfen wir die Summation mit dem Grenzwert vertauschen, und es
folgt die behauptete Gleichung.
Als P
Letztes zeigen wir die Minimalität von hA . Sei also g : I → [0, ∞) eine Lösung von
g(i) =
j∈I pi,j g(j) für i ∈ I \ A mit Randbedingung g(i) = 1 für i ∈ A. Wir zeigen mit
Induktion nach n ∈ N0 , dass
g(i) ≥ Pi (SA ≤ n)
für alle i ∈ I.
(2.4.1)
(Daraus folgt durch Grenzübergang n → ∞, dass g(i) ≥ lim n→∞ Pi (SA ≤ n) = Pi (SA < ∞) =
hA (i), was zu zeigen war.)
Für n = 0 ist (2.4.1) offensichtlich, ebenso für alle i ∈ A. Sei (2.4.1) für ein n vorausgesetzt,
und sei i ∈ I \ A. Dann ist
X
X
g(i) =
pi,j g(j) ≥
pi,j Pj (SA ≤ n) = Pi (TA ≤ n + 1)
j∈I
j∈I
nach Lemma 2.4.2. Da i ∈
/ A ist, gilt aber P i (TA ≤ n + 1) = Pi (SA ≤ n + 1). Dies zeigt (2.4.1)
für n + 1 und beendet den Beweis.
Wir kommen nun zur starken Markov-Eigenschaft. Diese besagt im Wesentlichen, dass die
gewöhnliche Markov-Eigenschaft, die in Satz 2.1.5 formuliert wurde, auch an Stoppzeiten gilt,
d. h. dass die ab einer Stoppzeit T betrachtete Restkette (X T , XT +1 , . . . ), gegeben das Ereignis
{XT = i} für ein i ∈ I, wieder eine Markovkette mit der selben Übergangsmatrix und Start in i
ist und dass sie ferner unabhängig von der Kette vor dem Zeitpunkt T ist, also unabhängig von
(X0 , X1 , . . . , XT ). Die Menge aller Ereignisse, die der Kette (X 0 , X1 , . . . , XT ) zustoßen können,
ist ein wichtiges System von Ereignissen:
Definition 2.4.4 (Prä-T -Ereignis). Es sei T : Ω → N0 ∪ {∞} eine Stoppzeit. Wir nennen
ein Ereignis A ⊂ Ω ein Prä-T -Ereignis, falls das Ereignis A ∩ {T = n} für jedes n ∈ N0 in Fn
liegt. Die Menge aller Prä-T -Ereignisse bezeichnen wir mit F T .
Wir definieren die I-wertige Zufallsgröße XT als XT (ω) (ω), allerdings nur auf der Menge
{ω ∈ Ω : T (ω) < ∞}. Falls T (ω) = ∞, so ist also X T nicht definiert. Daraus folgt, dass das
Ereignis {XT = i} insbesondere impliziert, dass T < ∞.
Nun folgt eine exakte Formulierung der starken Markov-Eigenschaft.
Satz 2.4.5 (Starke Markov-Eigenschaft). Es sei (X n )n∈N0 eine Markovkette, T eine Stoppzeit, A ∈ FT und B ⊂ I m für ein m ∈ N. Falls P(XT = i, A) > 0, so gilt
P(X[T +1,T +m] ∈ B | XT = i, A) = Pi (X[1,m] ∈ B).
(2.4.2)
Beweis. Wir multiplizieren mit P(X T = i, A) und brauchen nur die Gleichung
P(X[T +1,T +m] ∈ B, XT = i, A) = Pi (X[1,m] ∈ B)P(XT = i, A)
zu zeigen. Dies tun wir durch Aufspaltung nach allen (endlichen) Werten, die T annehmen kann:
Die linke Seite ist gleich
X
P(X[n+1,n+m] ∈ B, Xn = i, A, T = n).
n∈N0
22
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Da A ∈ FT , liegt das Ereignis A ∩ {T = n} in Fn . Also können wir die gewöhnliche MarkovEigenschaft anwenden (siehe etwa Korollar 2.1.6) und erhalten
P(X[n+1,n+m] ∈ B, Xn = i, A, T = n) = P(Xn = i, A, T = n)Pi (X[1,m] ∈ B).
Aufsummation über n ∈ N0 beendet den Beweis.
Damit können wir die Intuition hinter Satz 2.3.7 (siehe die Bemerkung danach) verschärfen:
Die Anzahl der Besuche zu einem gegebenen rekurrenten Punkt hat nicht nur unendlichen
Erwartungswert, sondern ist sogar konstant gleich ∞:
P
Korollar 2.4.6. Es sei i ∈ I mit pi = Pi (Ti = ∞) < 1. Es sei Vi = n∈N0 1l{Xn =i} die Anzahl
der Besuche in i. Dann gilt Pi (Vi > k) = (1 − pi )k für jedes k ∈ N, d. h., Vi ist unter Pi
geometrisch verteilt, falls i transient ist, und konstant gleich ∞, falls i rekurrent ist.
Beweis. Wir definieren die sukzessiven Zeitpunkte der Besuche in i durch T i(0) = 0 und Ti(k+1) =
inf{n > Ti(k) : Xn = i} für k ∈ N0 . Das Ereignis {Vi > k} ist also gleich dem Ereignis {Ti(k) < ∞},
falls die Kette in i startet. Ferner gilt offensichtlich P i (XT (k) = i | Ti(k) < ∞) = 1. Also gilt für
i
alle k, l ∈ N:
Pi (Vi > k + l | Vi > l) = Pi (Ti(k+l) < ∞ | Ti(l) < ∞)
= lim Pi (Ti(k+l) ≤ Ti(l) + n | XT (l) = i, Ti(l) < ∞)
n→∞
i
= lim Pi (Ti(k) ≤ n) = Pi (Ti(k) < ∞)
n→∞
= Pi (Vi > k).
Im dritten Schritt benutzten wir die starke Markov-Eigenschaft (2.4.2) mit A = {T i(l) < ∞} und
B = {Ti(k) ≤ n}.
Also ist Vi auf N0 geometrisch verteilt, und zwar mit Parameter P i (Vi = 1) = 1 − Pi (Vi >
1) = 1 − Pi (Ti < ∞) = Pi (Ti = ∞) = pi . Wie man leicht sieht, gilt dies auch im Fall p i = 0,
wobei dann Vi = ∞ mit Pi -Wahrscheinlichkeit Eins.
Beispiel 2.4.7. Es sei (Xn )n∈N0 die Irrfahrt auf Z wie in Beispiel 2.2.3. Wir wollen berechnen, wie lange die Irrfahrt im Durchschnitt benötigt, um einen gegebenen Punkt zu erreichen.
Genauer: Wir wollen P0 (T1 < ∞) und E0 (T1 ) berechnen.
Zunächst sieht man mit Hilfe der starken Markov-Eigenschaft und der räumlichen Verschiebungsinvarianz der Irrfahrt ein, dass P 0 (T2 < ∞) = P0 (T1 < ∞)P1 (T2 < ∞) = P0 (T1 < ∞)2 gilt
(der formale Beweis ist eine Übungsaufgabe). Ferner benutzt man die (gewöhnliche) MarkovEigenschaft zum Zeitpunkt Eins, um die Gleichung P 0 (T1 < ∞) = p + (1 − p)P−1 (T1 < ∞)
aufzustellen. Wieder mit Hilfe der Verschiebungsinvarianz und der ersten Beobachtung erhält
man die quadratische Gleichung P0 (T1 < ∞) = p + (1 − p)P0 (T1 < ∞)2 . Diese hat die beiden
Lösungen

p
1
1 ± 1 − 4p(1 − p)
1 ± |2p − 1| 
=
= oder
P0 (T1 < ∞) =

2(1 − p)
2(1 − p)
 p
1−p .
Im Fall p ≥
1
2
ergibt sich sofort, dass P0 (T1 < ∞) = 1, denn
p
1−p
> 1 für p > 21 . Im Fall p <
1
2
23
2.5. GLEICHGEWICHTSVERTEILUNGEN
p
gilt P0 (T1 < ∞) = 1−p
< 1, aber unsere Mittel reichen derzeit noch nicht aus, dies zu beweisen. 1
Für p ≥ 12 erreicht die Irrfahrt also den Punkt 1 von 0 aus mit Sicherheit, und man zeigt mit der
starken Markov-Eigenschaft leicht, dass dann auch jedes andere i ∈ N mit Sicherheit erreicht
wird.
Mit der (gewöhnlichen) Markov-Eigenschaft leitet man im Fall p ≥ 12 auch leicht die Beziehung E0 (T1 ) = p + (1 − p)[1 + E−1 (T1 )] her, und die starke impliziert, dass E −1 (T1 ) = E0 (T2 ) =
1
2E0 (T1 ). Also gilt E0 (T1 ) = 1−2(1−p)
, was im symmetrischen Fall gleich ∞ ist.
3
2.5
Gleichgewichtsverteilungen
Im Allgemeinen hängt die Verteilung einer Markovkette zu einem gegebenen Zeitpunkt auf sehr
komplizierte Weise ab von der Startverteilung (und natürlich von dem Zeitpunkt). Oft gibt es
aber für eine gegebene Übergangsmatrix spezielle Verteilungen, so dass die mit dieser Verteilung
gestartete Kette zu jedem Zeitpunkt dieselbe Verteilung besitzt, nämlich diese Startverteilung.
Man sagt, die Kette sei dann im Gleichgewicht bzw. sie sei stationär.
Wie bisher sei I eine höchstens abzählbare Menge und P eine stochastische Matrix auf I.
Wir wollen jede Abbildung
P ν : I → [0, ∞) ein Maß nennen und erinnern uns, dass ein Maß ν eine
Verteilung P
heißt, falls i∈I ν(i) = 1 gilt. Außerdem erinnern wir uns, dass νP das Matrixprodukt
(νP )(j) = i∈I ν(i)pi,j bezeichnet.
Definition 2.5.1 (invariantes Maß, Gleichgewichtsverteilung). Ein Maß ν heißt invariant
für P , falls νP = ν gilt, d. h. falls ν ein (nichtnegativer) Links-Eigenvektor von P zum Eigenwert
1 ist. Falls ν eine Verteilung und invariant ist, nennt man ν auch eine Gleichgewichtsverteilung
für P .
Bemerkung 2.5.2. (a) Wenn I endlich ist, kann jedes invariante Maß zu einer Gleichgewichtsverteilung normiert werden.
(b) Die Frage, ob P ein invariantes Maß besitzt, ist a priori nicht leicht zu beantworten. Man
muss im Prinzip das Gleichungssystem νP = ν lösen und prüfen, ob es eine nichtnegative
Lösung ν gibt.
(c) Offensichtlich ist ein für P invariantes Maß auch für jede Potenz von P invariant. Falls
P irreduzibel ist und ν 6= 0 ein invariantes Maß ist, so ist ν(i) > 0 für jedes i ∈ I. Denn
wegen ν 6= 0 existiert ein i0 ∈ I mit ν(i0 ) > 0, und dann folgt für jedes i ∈ I (mit einem
(n)
n ∈ N, so dass p(n)
i0 ,i > 0): ν(i) ≥ ν(i0 )pi0 ,i > 0.
(d) Wenn ν eine Gleichgewichtsverteilung ist, dann gilt für jedes n ∈ N0 und jedes j ∈ I:
Pν (Xn = j) =
X
ν(i)p(n)
i,j = ν(j),
i∈I
d. h. die mit Verteilung ν gestartete Kette hat zu jedem Zeitpunkt die selbe Verteilung ν.
3
1
Dies folgt etwa aus dem Starken Gesetz der Großen Zahlen, zusammen mit dem Hinweis auf E0 (S1 ) < 0, d. h.
es gilt insbesondere limn→∞ Sn = −∞ mit P0 -Wahrscheinlichkeit Eins.
24
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Sehr oft kann das invariante Maß nicht sinnvoll explizit angegeben werden, und es gibt
wenige Beispiele, in denen das invariante Maß eine der bekannten Verteilungen ist. F ür die
symmetrische Irrfahrt auf Z (siehe Beispiel 2.2.3) ist die Gleichverteilung auf Z invariant, aber
offensichtlich kann man sie nicht zu einer Gleichgewichtsverteilung normieren. F ür die Irrfahrt
auf {0, . . . , N } (siehe Beispiel 2.2.5) mit absorbierenden Rändern 0 und N sind die beiden
Verteilungen invariant, die auf {0} bzw. auf {N } konzentriert sind. Für weitere Beispiele siehe
Lemma 2.5.8 und Beispiele 2.5.9 und 2.7.4.
Für den Rest dieses Abschnittes setzen wir voraus, dass P irreduzibel ist, also dass I aus
einer einzigen Äquivalenzklasse besteht. Zunächst zeigen wir, dass im Falle der Rekurrenz immer
mindestens ein invariantes Maß existiert, und zwar, für beliebiges k ∈ I, das Maß γk , gegeben
als
Tk
X
1l{Xn =i} .
γk (i) = Ek
n=1
In Worten: γk (i) ist die erwartete Zahl der Besuche in i für eine in k gestartete Markovkette,
die betrachtet wird bis zur ersten Rückkehr zum Startpunkt k.
Satz 2.5.3. Sei P irreduzibel und rekurrent, und sei k ∈ I. Dann gelten:
(a) γk ist ein invariantes Maß.
(b) Für jedes i ∈ I gilt 0 < γk (i) < ∞.
(c) γk ist das einzige invariante Maß mit Wert 1 in k.
Beweis. (a) Wir schreiben zunächst γk (i) wie folgt:
X
X
γk (i) = Ek
1l{Xn =i,n≤Tk } =
Pk (Xn = i, n ≤ Tk )
n∈N
=
XX
n∈N
Pk (Xn = i, Xn−1 = j, n ≤ Tk ).
n∈N j∈I
Man beachte, dass das Ereignis {n ≤ T k } = {Tk ≤ n − 1}c in Fn−1 liegt. Also können wir die
Markov-Eigenschaft zum Zeitpunkt n − 1 anwenden:
Pk (Xn = i, Xn−1 = j, n ≤ Tk ) = Pk (Xn−1 = j, n ≤ Tk )Pj (X1 = i)
= Pk (Xn−1 = j, n − 1 ≤ Tk − 1)pj,i .
Dies setzen wir oben ein und erhalten nach einer Indexverschiebung
γk (i) =
pj,i
X
pj,i Ek
j∈I
=
X
X
j∈I
Pk (Xn = j, n ≤ Tk − 1) =
j∈I
n∈N0
Tk
X
n=1
X
X
γk (j)pj,i .
1l{Xn =j} =
pj,i Ek
k −1
TX
n=0
1l{Xn =j}
j∈I
(b) Auf Grund von (a) ist γk auch invariant für P n für jedes n ∈ N, also folgt insbesondere
1 = γk (k) ≥ γk (j)p(n)
j,k für jedes j ∈ I. Wegen der Irreduzibilität gibt es für jedes j ein n mit
(n)
(n)
pj,k > 0, und somit folgt γk (j) < ∞ für jedes j. Andererseits folgt auch γ k (j) ≥ γk (k)p(n)
k,j = pk,j ,
was positiv ist für geeignetes n.
25
2.5. GLEICHGEWICHTSVERTEILUNGEN
P
(c) Es sei λ ein invariantes Maß mit λ(k) = 1. Dann haben wir λ(j) = i∈I\{k} λ(i)pi,j +pk,j
für jedes j. Nun ersetzen wir auf der rechten Seite λ(i) ebenfalls mit Hilfe der Invarianz und
erhalten
X X
λ(j) =
i∈I\{k} i1 ∈I\{k}
X
=
λ(i1 )pi1 ,i + pk,i pi,j + pk,j
λ(i1 )pi1 ,i pi,j +
i,i1 ∈I\{k}
X
=
X
pk,i pi,j + pk,j
i∈I\{k}
λ(i1 )pi1 ,i pi,j + Pk (Tk ≥ 2, X2 = j) + Pk (Tk ≥ 1, X1 = j).
i,i1 ∈I\{k}
In dieser Weise fahren wir iterativ fort und erhalten für jedes n ∈ N
λ(j) =
X
λ(in )
i0 ,i1 ,...,in ∈I\{k}
≥
n+1
X
n
Y
r=1
n+1
X
pir ,ir−1 pi0 ,j +
Pk (Tk ≥ r, Xr = j)
r=1
Pk (Tk ≥ r, Xr = j)
r=1
= Ek
k ,n+1}
min{T
X
r=1
1l{Xr =j} .
Nun lassen wir n → ∞ und erhalten auf der rechten Seite γ k (j) als Grenzwert. Also haben wir
gezeigt, dass λ(j) ≥ γk (j) für alle j ∈ I. Daher ist λ−γk ebenfalls ein invariantes Maß. Da dieses
Maß allerdings eine Nullstelle besitzt (nämlich in k), ist es nach Bemerkung 2.5.2(b) identisch
gleich Null. Dies beendet den Beweis.
Zusammen mit Satz 2.3.14 wissen wir nun, dass jede endliche irreduzible stochastische
Matrix immer eine Gleichgewichtsverteilung besitzt.
Der folgende Satz 2.5.5 klärt die Frage nach der Existenz von Gleichgewichtsverteilungen
und ist einer der wichtigsten Sätze über Markovketten. Die Antwort ist eng verknüpft mit der
erwarteten Rückkehrzeit zu einem Startpunkt i ∈ I:
µi = Ei (Ti ) =
X
n∈N
nPi (Ti = n) =
X
(n)
nfi,i
∈ [0, ∞].
n∈N
Falls µi < ∞ (d. h. falls die Irrfahrt nach endlicher erwarteter Zeit zu ihrem Startpunkt i zur ück
kehrt), dann ist natürlich Pi (Ti < ∞) = 1, die Irrfahrt also rekurrent. Mit Hilfe von µ i können
wir also rekurrente Zustände feiner unterteilen:
Definition 2.5.4 (positive und Nullrekurrenz). Ein Zustand i ∈ I heißt positiv rekurrent,
falls µi < ∞, und nullrekurrent, falls i rekurrent, aber nicht positiv rekurrent ist.
Der folgende Satz zeigt insbesondere, dass die Existenz von Gleichgewichtsverteilungen äquivalent zur positiven Rekurrenz ist:
26
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Satz 2.5.5. Sei P irreduzibel, dann sind die folgenden drei Aussagen äquivalent.
(i) Es existiert eine Gleichgewichtsverteilung.
(ii) Es gibt einen positiv rekurrenten Zustand in I.
(iii) Alle Zustände in I sind positiv rekurrent.
Sind diese Bedingungen erfüllt, so ist die Gleichgewichtsverteilung π eindeutig bestimmt und
durch π(i) = µ1i gegeben.
Beweis. Die Richtung (iii) =⇒ (ii) ist trivial. Wir zeigen nun (ii) =⇒ (i). Sei k ∈ I mit µ k < ∞,
dann ist wegen Irreduzibilität die Kette rekurrent. Nach Satz 2.5.3 ist γ k ein invariantes Maß.
Man sieht, dass
X
j∈I
γk (j) =
X
j∈I
Ek
Tk
X
n=1
1l{Xn =j} = Ek
Tk X
X
n=1 j∈I
1l{Xn =j} = Ek (Tk ) = µk < ∞.
(2.5.1)
Also kann man γk zu einer Gleichgewichtsverteilung normieren, d. h. (i) folgt.
Nun beweisen wir (i) =⇒ (iii). Sei π eine Gleichgewichtsverteilung, und sei k ∈ I. Dann ist
γ = π/π(k) ein invariantes Maß mit γ(k) = 1. Nach Satz 2.5.3 gilt γ = γ k . Wie in (2.5.1) sieht
man, dass
X
X
1
1 X
π(j) =
γ(j) =
< ∞.
γk (j) =
µk =
π(k)
π(k)
j∈I
j∈I
j∈I
Also ist (iii) gezeigt.
Die Zusatzaussage ergibt sich aus den obigen Beweisen.
Bemerkung 2.5.6 (Klassifikation). Also ergibt sich eine Trichotomie für irreduzible Markovketten, d. h. eine irreduzible Markovkette gehört immer zu genau einem der folgenden drei
Fälle:
• Die Kette ist transient, für alle i, j ∈ I gilt Pi (Tj < ∞) < 1, und es gibt kein invariantes
Maß.
• Die Kette ist nullrekurrent, für alle i, j ∈ I gilt Pi (Tj < ∞) < 1 und Ei (Tj ) = ∞, und es
gibt zwar ein invariantes Maß aber keine invariante Verteilung.
• Die Kette ist positiv rekurrent, für alle i, j ∈ I gilt Ei (Tj ) < ∞, und es gibt eine invariante
Verteilung.
Auf Grund von Satz 2.3.14 kann bei endlichem Zustandsraum I nur der positiv rekurrente Fall
auftreten.
3
Beispiel 2.5.7. Die eindimensionale Irrfahrt (siehe Beispiel 2.2.3) ist nullrekurrent. Denn sie
besitzt ja das konstante Maß als ein invariantes Maß, und dies lässt sich nicht normieren.
3
In den meisten Fällen, selbst bei endlichem I, kann man die Gleichgewichtsverteilung nicht
sinnvoll explizit angeben, die Formel wäre zu kompliziert. Ein schönes Gegenbeispiel ist die
µ-Irrfahrt auf einer Gruppe, siehe Beispiel 2.2.2:
2.6. KONVERGENZ GEGEN DIE GLEICHGEWICHTSVERTEILUNG
27
Lemma 2.5.8. Es seien G eine endliche Gruppe und µ eine Verteilung auf G. Dann ist die
Gleichverteilung auf G eine Gleichgewichtsverteilung der µ-Irrfahrt. Falls die Irrfahrt irreduzibel
ist, so ist sie auch die einzige Gleichgewichtsverteilung.
Beweis. Für jedes g ∈ G ist die Abbildung h 7→ g −1 h bijektiv auf G, und es gilt
X
X
X
pg,h =
µ(g −1 h) =
µ(g 0 ) = 1.
g∈G
g∈G
g 0 ∈G
Beispiel 2.5.9 (Bernoulli-Laplace-Diffusionsmodell). Noch ein Beispiel, in dem die invariante Verteilung explizit angegeben werden kann, ist das
aus Beispiel 2.2.8.
Diffusionsmodell
w
Hier ist die hypergeometrische Verteilung ν(i) = si w−i
/ s+w
invariant
auf
{0, 1, . . . , w}. 3
w
2.6
Konvergenz gegen die Gleichgewichtsverteilung
Das Hauptergebnis dieses Abschnittes (und eine der wichtigsten Eigenschaften von Markovketten) ist die Tatsache, dass jede irreduzible aperiodische und positiv rekurrente Markovkette bei
divergierender Laufzeit gegen ihre Gleichgewichtsverteilung konvergiert. Hierbei nennen wir eine Markovkette bzw. ihre Übergangsmatrix P aperiodisch, wenn für jedes i ∈ I die sogenannte
Periode von i,
di = ggT{n ∈ N : p(n)
i,i > 0},
gleich Eins ist. Wir wollen uns im Folgenden auf aperiodische Markovketten beschränken, d. h.
wir werden voraussetzen, dass di = 1 für jedes i ∈ I gilt. Unser Hauptergebnis ist:
Satz 2.6.1. Es sei P irreduzibel, aperiodisch und positiv rekurrent mit Gleichgewichtsverteilung
π. Dann gilt für alle i, j ∈ I:
lim p(n)
i,j = π(j).
n→∞
Als Übungsaufgabe zeigt man leicht, dass auch für jede Startverteilung ν und jedes j ∈ I
gilt: limn→∞ Pν (Xn = j) = π(j). Falls die Markovkette nicht aperiodisch ist, also wenn sie etwa
die Periode d > 1 hat2 , dann zeigt man leicht, dass die Matrix P d auf gewissen Teilmengen
aperiodisch ist, und kann Satz 2.6.1 auf geeignete Teilmatrizen von P d anwenden.
Als Vorbereitung des Beweises von Satz 2.6.1 charakterisieren wir die Aperiodizität:
Lemma 2.6.2. P ist genau dann irreduzibel und aperiodisch, wenn für jede i, j ∈ I ein n0 ∈ N
existiert, so dass p(n)
i,j > 0 für alle n ≥ n0 gilt.
Beweis. Dieser Beweis ist länglich und benutzt ausschließlich zahlentheoretische Argumente
und wird daher weggelassen. Siehe etwa [Se81].
Beweis von Satz 2.6.1. Wie immer sei (X n )n∈N0 eine Markovkette mit Übergangsmatrix P und
Start in i unter Pi . Wir wollen also zeigen, dass Pi (Xn = j) für n → ∞ gegen π(j) konvergiert.
2
Man kann leicht zeigen, dass die Periode eine Klasseneigenschaft ist, d. h. dass die Abbildung i 7→ di konstant
auf den Klassen ist.
28
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
Wir benutzen ein sogenanntes Kopplungsargument, das die Untersuchung der betrachteten
Markovkette (Xn )n∈N0 koppelt mit einer weiteren, unabhängigen Markovkette (Yn )n∈N0 mit der
selben Übergangsmatrix, wobei allerdings (Y n )n∈N0 mit der Gleichgewichtsverteilung π gestartet
wird. Daraus folgt, dass die Verteilung von Y n zu jedem festen Zeitpunkt n exakt gleich π ist,
siehe Bemerkung 2.5.2(d). Unsere Hauptaufgabe besteht nun darin zu beweisen, dass die erste
Kette irgendwann einmal die zweite trifft, d. h. dass sich beide Ketten jemals im selben Zustand
befinden. Mit anderen Worten, wir werden zeigen, dass die Treffzeit
T = inf{n ∈ N0 : Xn = Yn }
mit Sicherheit endlich ist. Dann definieren wir die gekoppelte Kette (Z n )n∈N0 durch
Zn =
(
Xn
Yn
für n ≤ T,
für n > T,
und zeigen, dass (Zn )n∈N0 ebenfalls eine Markovkette mit Übergangsmatrix P ist. Danach ist
der Beweis schnell beendet.
Wir kommen zu den Details. Als Erstes sieht man, dass die Paar-Markovkette (X n , Yn )n∈N0
die Übergangsmatrix Pb auf I × I mit pb(i,j),(k,l) = pi,k pj,l für alle i, j, k, l ∈ I besitzt. Für
(n) (n)
alle n ∈ N gilt auch pb(n)
(i,j),(k,l) = pi,k pj,l , wovon man sich leicht überzeugt. Die Aperiodizität
von Pb zeigt man leicht als Übungsaufgabe mit Hilfe von Lemma 2.6.2 und (2.1.7). Da P die
Gleichgewichtsverteilung π besitzt, hat Pb die Gleichgewichtsverteilung π
b, die gegeben ist durch
b
π
b(i, j) = π(i)π(j) für i, j ∈ I. Also ist P insbesondere positiv rekurrent (siehe Satz 2.5.5).
Ab jetzt sei X0 = i fest. Die Markovkette (Xn , Yn )n∈N0 auf I × I besitzt die Startverteilung
νb(k, l) = δi (k)π(l), wobei δi (k) = δi,k das Kroneckersymbol ist.
Nun argumentieren wir, dass die Treffzeit T mit Wahrscheinlichkeit Eins endlich ist. F ür
einen beliebigen Zustand b ∈ I sei T(b,b) der erste Zeitpunkt, an dem die Kette (X n , Yn )n∈N0 den
Punkt (b, b) trifft. Offensichtlich ist T ≤ T (b,b) . Wegen der Rekurrenz von Pb ist T(b,b) endlich,
also auch T .
Nun beweisen wir, dass die oben definierte Folge (Z n )n∈N0 eine Markovkette mit Übergangsmatrix P ist. Dazu reicht es nach Lemma 2.1.5(a) zu zeigen, dass für alle n ∈ N und alle
i0 , . . . , in ∈ I gilt:
n
Y
pir−1 ,ir .
(2.6.1)
Pνb(Z[0,n] = i[0,n] ) = δi (i0 )
r=1
Dies zeigen wir durch Aufspaltung nach allen Werten, die T annehmen kann:
Pνb(Z[0,n] = i[0,n] ) =
=
n
X
r=0
n
X
Pνb(Z[0,n] = i[0,n] , T = r) + Pνb(Z[0,n] = i[0,n] , T > n)
Pνb(X[0,r] = i[0,r] , Y[r+1,n] = i[r+1,n] , Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir )
r=0
+ Pνb(X[0,n] = i[0,n] , Y0 6= i0 , . . . , Yn 6= in ).
Nun nutzt man die Unabhängigkeit der Ketten (Xn )n∈N0 und (Yn )n∈N0 sowie die Markov-
29
2.7. REVERSIBLE MARKOVKETTEN
Eigenschaft der Kette (Yn )n∈N0 zum Zeitpunkt r bzw. n aus, um zu erhalten:
Pνb(X[0,r] = i[0,r] , Y[r+1,n] = i[r+1,n] , Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir )
= Pi (X[0,r] = i[0,r] )Pπ (Y[r+1,n] = i[r+1,n] | Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir )
× Pπ (Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir )
n
Y
= δi (i0 )
pij−1 ,ij Pπ (Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir )
j=1
und
Pνb(X[0,n] = i[0,n] , Y0 6= i0 , . . . , Yn 6= in ) = δi (i0 )
n
Y
j=1
pij−1 ,ij Pπ (Y0 6= i0 , . . . , Yn 6= in ).
Nun kombiniere man all diese Gleichungen und beachte, dass
n
X
Pπ (Y0 6= i0 , . . . , Yr−1 6= ir−1 , Yr = ir ) + Pπ (Y0 6= i0 , . . . , Yn 6= in ) = 1,
r=0
um bei (2.6.1) anzukommen. Also ist (Z n )n∈N0 eine Markovkette mit Übergangsmatrix P .
Nun ist der Beweis von Satz 2.6.1 leicht zu beenden. Wir schreiben p (n)
i,j mit Hilfe von
(Zn )n∈N0 als
p(n)
i,j = Pνb (Zn = j) = Pνb (Zn = j, T ≤ n) + Pνb (Zn = j, T > n)
und analog π(j) als
π(j) = Pπ (Yn = j) = Pνb(Zn = j, T ≤ n) + Pνb(Yn = j, T > n).
Somit folgt
(n)
p − π(j) ≤ 2Pνb(T > n),
i,j
und dies konvergiert für n → ∞ gegen Null, da ja Pνb(T < ∞) = 1.
2.7
Reversible Markovketten
Einen wichtigen Spezialfall von Gleichgewichtsverteilungen stellen Verteilungen dar, die die sogenannte detailed balance condition erfüllen:
Definition 2.7.1 (reversibel). Ein Maß ν auf I heißt reversibel bezüglich der stochastischen
Matrix P , falls für alle i, j ∈ I gilt: ν(i)pi,j = ν(j)pj,i . In diesem Fall nennen wir auch P
reversibel.
Bemerkung 2.7.2. (a) Es ist offensichtlich, dass jedes reversible Maß invariant ist. Im positiv
rekurrenten Fall ist also die Gleichgewichtsverteilung der einzige Kandidat f ür eine reversible Verteilung. Allerdings sind bei weitem nicht alle Gleichgewichtsverteilungen reversibel.
Die Reversibilität ist eine sehr spezielle Eigenschaft.
30
KAPITEL 2. MARKOVKETTEN IN DISKRETER ZEIT
(b) Der Begriff der Reversibilität kommt von der folgenden Eigenschaft her: Wenn π eine
reversible Verteilung ist, so ist die Verteilung der Markovkette unter P π invariant unter
Zeitumkehr, d. h. für alle n ∈ N und alle i0 , i1 , . . . , in ∈ I gilt
Pπ (X0 = i0 , . . . , Xn = in ) = Pπ (X0 = in , . . . , Xn = i0 ).
Diese Eigenschaft rechnet man leicht als Übungsaufgabe nach.
3
Es folgen zwei Beispiele, in denen die reversible Gleichgewichtsverteilung existiert und explizit angegeben werden kann.
Beispiel 2.7.3. Sei G eine endliche Gruppe und µ eine Verteilung auf G mit µ(g) = µ(g −1 ) für
jedes g ∈ G. Dann ist die Gleichverteilung auf G reversibel für die µ-Irrfahrt auf G (siehe Beispiele 2.2.2 und 2.5.8). Dies sieht man leicht, indem man nachrechnet, dass die Übergangsmatrix
P symmetrisch ist.
3
Beispiel 2.7.4 (Ehrenfests Urnenmodell). Wir betrachten das Ehrenfest-Modell vonBeispiel 2.2.7. Als Übungsaufgabe rechnet man nach, dass die Binomialverteilung π(k) = Nk 2−N
reversibel ist.
Eine andere Betrachtungsweise macht es möglich, die reversible Verteilung durch Deduktion
zu finden. Wir erweitern das Modell, indem wir den Aufenthaltsort jeder einzelnen Kugel registrieren: ‘0’ für die linke Urne, ‘1’ für die rechte. Dann ist der Vektor der N Aufenthaltsorte der
N Kugeln ein Element des neuen Zustandsraumes {0, 1} N . Wir können diesen Zustandsraum
als eine Gruppe auffassen, wobei die Verknüpfung die Addition modulo 2 ist. Die Markovkette
der N Labels gehorcht der Regel, dass zu den Zeitpunkten 1, 2, . . . ein zufällig gewähltes der N
Indizes geflippt wird. Dies ist eine µ-Irrfahrt im Sinne von Beispiel 2.2.2 mit µ(x) = N1 , falls
x = (x1 , . . . , xN ) genau eine von Null verschiedene Komponente hat. Nach Beispiel 2.7.3 ist die
Gleichverteilung reversibel für diese Irrfahrt. Projiziert man diese Verteilung wieder zurück auf
die Anzahl der Kugeln in der linken Urne, erhält man gerade die Binomialverteilung.
Da die Kehrwerte der Verteilung π(k) gerade die erwarteten Rückkehrzeiten zu k sind, erhält
man die interessante Folgerung, dass das System im Mittel viel später in seinen Anfangszustand
zurückkehrt, wenn es in einem extremen Zustand startet (d. h. alle Kugeln in einer Urne), als
wenn es mit etwa ausgeglichenen Kugelbeständen beginnt.
3
Beispiel 2.7.5 (MCMC). In vielen Anwendungen des Konvergenzsatzes 2.6.1 dreht man den
Spieß folgendermaßen um: Auf einer endlichen Menge I hat man eine gewisse Verteilung π
gegeben und möchte eine Stichprobe mit dieser Verteilung ziehen, d. h. man möchte eine Zufallsvariable mit der Verteilung π generieren. Diese Aufgabe ist zwar endlich, aber in den meisten
Fällen höchst nichttrivial, weil I oft gigantisch groß ist. Ein beliebter Ansatz ist die sogenannte
Markov Chain Monte Carlo Methode: Man wählt eine Markovkette, deren invariante Verteilung
π ist, und man lässt diese Kette mit einem beliebigen Startwert ‘genügend lange’ laufen, bis man
auf Grund von Satz 2.6.1 meint, dass die Kette ‘nahe genug’ an π heran gekommen ist. Dabei
wählt man meist eine Übergangsmatrix mit vielen Nullen, so dass π sogar reversibel ist, etwa
die Matrix P = (pi,j )i,j∈I mit
n
o
(
π(j)qj,i
qi,j min 1, π(i)qi,j
, falls i 6= j,
pi,j =
P
1 − k∈I\{i} pi,k ,
falls i = j,
2.7. REVERSIBLE MARKOVKETTEN
31
wobei Q = (qi,j )i,j∈I eine stochastische ‘Referenzmatrix’ auf I ist (mit vielen Nullen). Dieser Ansatz wird der Metropolis-Algorithmus genannt. Man beachte, dass nur die Quotienten π(j)/π(i)
bekannt sein müssen, die bei geeigneter Wahl von Q meist nicht extrem klein oder extrem groß
sind und deren Berechnung dann auch nicht aufwendig ist.
Der Vorteil einer solchen MCMC-Methode ist, dass sie einfach zu definieren und zu implementieren ist. Der Nachteil ist, dass man oft keine guten Kriterien hat, wann man die Iterationen abbrechen sollte. In jedem Fall werden Abschätzungen für die Konvergenzgeschwindigkeit
benötigt, und es ist oft nicht leicht, effektive Abschätzungen zu erhalten.
Viele Beispiele für zu simulierende Verteilungen kommen aus der statistischen Physik, wo auf
Gitterkonfigurationsräumen der Form I = {0, 1}Λn , wobei Λn = Zd ∩ [−n, n]d eine große Box ist,
1
e−βHn (i) gegeben sind, wobei Zn,β die Normierung ist,
gewisse Verteilungen der Form π(i) = Zn,β
β > 0 ein Stärkenparameter und Hn : I → R eine Hamiltonsche Abbildung. Dies ist ein Maß, das
Konfigurationen i mit kleinem Wert von H n (i) bevorzugt, und dieser
P Effekt ist desto stärker, je
größer β ist. Ein Beispiel ist die Anzahl der 0-1- Übergänge Hn (i) = x,y∈Λn : |x−y|=1 |ix −iy |, das
ein Stück Eisen modelliert (Ladung in Nachbarpunkten soll möglichst oft gleich gerichtet sein),
oder die Anzahl der Nachbarpaare, in denen ein Molekül sitzt, Hn = #{(x, y) ∈ Λ2n : |x − y| =
1, ix = iy = 1}.
3
Kapitel 3
Markovketten in stetiger Zeit
Markovketten in stetiger Zeit sind Prozesse (X(t)) t∈[0,∞) mit höchstens abzählbarem Zustandsraum I, die im Gegensatz zu Markovketten mit diskreter Zeit, die wir im vorigen Kapitel studiert haben, mit t ∈ [0, ∞) statt n ∈ N0 indiziert sind und die sich ebenfalls der Markoveigenschaft erfreuen, d. h. für jedes n ∈ N und jede 0 ≤ t1 ≤ t2 ≤ · · · ≤ tn ≤ tn+1 sowie jede
i1 , i2 , . . . , in , in+1 ∈ I gilt
P X(tn+1 ) = in+1 X(t1 ) = i1 , . . . , X(tn ) = in = P X(tn+1 ) = in+1 X(tn ) = in .
(3.0.1)
Wir werden im Folgenden kurz MKSZ schreiben für Markovketten in stetiger Zeit und MKDZ
für Markovketten in diskreter Zeit wie im vorigen Kapitel. Wenn also (X(t)) t∈[0,∞) eine MKSZ
ist, so ist für jedes t0 > 0 die Kette (X(nt0 ))n∈N0 eine MKDZ mit Übergangsmatrix (P(X(t0 )) =
j | X(0) = i))i,j∈I . Daher haben MKSZ und MKDZ viele Dinge mit einander gemein, aber
wegen der Überabzählbarkeit der Indexmenge [0, ∞) gibt es zumindest immer dort bedeutsame
Unterschiede, wo potentiell überabzählbar viele Zeitpunkte involviert sind. Außerdem benötigt
man a priori sehr viele stochastische Matrizen, um eine MKSZ zu beschreiben, und es ist klar,
dass man nach Methoden suchen muss, eine MKSZ auf viel praktikablere Weise zu beschreiben.
Dies führt dazu, dass die Theorie der MKSZ recht unterschiedlich von der der MKDZ ist.
3.1
Intuitive Konstruktion
In diesem Abschnitt skizzieren wir die Konstruktion einer MKSZ in einem wichtigen Spezialfall
auf natürliche Weise, um eine intuitive Vorstellung von MKSZ zu erlangen. Wir werden hier
recht oberflächlich bleiben; präzise Definitionen, Annahmen, Aussagen und Beweise folgen im
Abschnitt 3.3.
Zunächst sieht man, dass eine MKSZ (X(t)) t∈[0,∞) zu gewissen Sprungzeiten 0 < T1 < T2 <
. . . Sprünge vom aktuellen Zustand zu einem anderen Zustand ausführt, wobei wir “Sprünge”
zum aktuellen Zustand ignorieren. Es sei also T 0 = 0 und Tn = inf{t > Tn−1 : X(t) 6= X(Tn−1 )}
die n-te Sprungzeit. Der Einfachheit halber setzen wir hier voraus, dass T n > Tn−1 für alle
n ∈ N mit Wahrscheinlichkeit Eins gilt. Außerdem setzen wir voraus, dass die Pfade t 7→ X(t)
mit Wahrscheinlichkeit Eins rechtsstetig sind und überall linksseitige Grenzwerte besitzen. Dies
garantiert, dass X(Tn ) = X(Tn +) 6= X(Tn −) ist, wobei wir X(Tn +) = limt↓0 X(Tn + t) und
X(Tn −) = limt↑0 X(Tn + t) setzen.
33
34
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Wir bezeichnen mit τn = Tn − Tn−1 die Wartezeit von (n − 1)-ten bis zum n-ten Sprung.
Dann folgt aus einer etwas sorglosen Anwendung der Markoveigenschaft in (3.0.1), dass gilt:
P(τ1 > s + t | τ1 > t, X(0) = i) = P X(r) = i ∀r ∈ [0, t + s] X(r) = i ∀r ∈ [0, t]
= P X(r) = i ∀r ∈ [t, t + s] X(t) = i
(3.1.1)
= P(τ1 > s | X(0) = i),
i ∈ I, s, t > 0.
Also sollten die Wartezeiten zwischen den Sprüngen gedächtnislos sein. Als eine beliebte Übungsaufgabe zeigt man, dass dann diese Wartezeiten exponentialverteilt sein müssen. Außerdem sollte
die Wahrscheinlichkeit, dann in einen bestimmten anderen Zustand zu springen, unabhängig von
allem Vorherigen sein.
Dies legt die folgende Konstruktion einer MKSZ X = (X(t)) t∈[0,∞) nahe. Wir nehmen
an, dass es für jedes i ∈ I einen Vorrat an zum Parameter c i > 0 exponentiell verteilten
Zufallsgrößen ξi(n) , n ∈ N, gibt. Die Variable ξi(n) soll die Wartezeit sein, die die Kette beim n-ten
Besuch in i verweilt, bevor sie wieder von i weg springt. Die Kette verbringt also bei jedem
Besuch durchschnittlich 1/ci Zeiteinheiten in i. Die Gesamtheit aller dieser Wartezeiten sei
unabhängig. Ferner gebe es eine von all diesen Wartezeiten unabhängige Markovkette (Yn )n∈N0
in diskreter Zeit. Wir setzen voraus, dass Y n 6= Yn−1 für jedes n ∈ N. Wir starten mit X0 =
Y0 . Nach Ablauf der Wartezeit ξY(1)0 springt die Kette X in den Zustand Y1 . Nun beginnt die
Wartezeit ξY(1)1 zu laufen, und nach ihrem Ablauf springt X in den Zustand Y 2 . Wenn Y2 = Y0 ,
so beginnt die Wartezeit ξY(2)0 zu laufen, sonst die Wartezeit ξY(1)2 . Nach ihrem Ablauf springt X
in den Zustand Y3 und so weiter. Somit ist der Übergangsmechanismus der MKSZ X offenbar
vollständig beschrieben. Zusammen mit einer Startverteilung ν auf I ist damit ein stochastischer
Prozess definiert. Die MKDZ (Yn )n∈N0 heißt die in (X(t))t∈[0,∞) eingebettete Kette. Es gilt dann
nach Konstruktion Yn = X(Tn ) für jedes n ∈ N0 .
Die Tatsache, dass diese Konstrution wirklich eine MKSZ definiert, also dass insbesondere
die Mwrkoveigenschaft in (3.0.1) erfüllt ist, kann man durch eine nicht wirklich schwierige, aber
sehr umständliche und lästige Rechnung verifizieren, siehe etwa [Ge02].
Man definiert
qi,j =
(
ci pi,j
−ci
falls i 6= j,
falls i = j,
(3.1.2)
und bezeichnet Q = (qi,j )i,j∈I als die Q-Matrix der MKSZ. Offenbar kann man aus Q die c i und
jene Zeilen von P , für die ci 6= 0 ist, zurückgewinnen; die anderen Zeilen von P sind ohnehin
bedeutungslos. Wir erwähnen (siehe Satz 3.3.7), dass
qi,j = lim
t↓0
Pi (X(t) = j)
,
t
i, j ∈ I, i 6= j,
(3.1.3)
gilt. Die qi,j heißen daher auch Übergangsraten.
Im Allgemeinen kann man den Fall ci = 0 für ein i ∈ I erlauben. In diesem Fall ist i
absorbierend, und von i aus werden keinerlei Sprünge mehr ausgeführt. Dagegen ignorieren wir
zunächst den möglichen Fall ci = ∞, in welchem man sofort springt. Es kann allerdings passieren,
dass der Prozess “steckenbleibt” in dem Sinne, dass der Explosionszeitpunkt
ζ=
∞
X
n=1
τn = lim Tn
n→∞
(3.1.4)
35
3.2. BEISPIELE
mit positiver Wahrscheinlichkeit endlich ist. Hier stellt sich die Frage, ob man den Prozess auch
noch nach dem Zeitpunkt ζ definieren kann oder will; die bisherige Konstruktion reicht nur bis
ζ. Hier ist ein Kriterium für die Endlichkeit des Explosionszeitpunktes:
P
Lemma 3.1.1. Es gilt genau dann Pi (ζ < ∞) = 1 für alle i ∈ I, wenn Pi ( n∈N 1/cYn < ∞) = 1
für alle i ∈ I gilt, wobei (Yn )n∈N0 eine MKDZ mit Übergangsmatrix P und Start in i ist.
Beweis. Es sei Pbi die Verteilung der MKDZ Y = (Yn )n∈N0 bei Start in i, dann ergibt der Satz
von der Totalen Wahrscheinlichkeit:
X 1
Z
X 1
Pi
<∞ =
< ∞ Y = y Pbi (dy).
Pi
c Yn
c Yn
I N0
n∈N
l∈N
Die Aussage des Lemmas lautet also:
Pi (ζ < ∞)
für alle i ∈ I
⇐⇒
X 1
<∞
c yn
n∈N
Man beachte, dass auf dem Ereignis {Y = y} gilt:
Ei [ζ] =
∞
X
n=1
Ei [τn ] =
für Pbi -fast alle y ∈ I N0 .
∞
X
1
,
c
n=1 yn
also ist ‘⇐=’ klar. Um die umgekehrte Richtung zu zeigen, betrachte man
Ei [e−ζ ] =
∞
Y
n=1
Ei [e−τn ] =
∞
Y
n=1
nX
c yn
1 o
= exp
.
log 1 −
1 + c yn
1 + c yn
∞
n=1
Eine elementare Übungsaufgabe zeigt, dass die rechte Seite gleich Null ist, wenn die Reihe der
1/cyn divergiert. Dies zeigt die umgekehrte Richtung und beendet den Beweis des Lemmas.
3.2
Beispiele
Beispiel 3.2.1 (Geburts- und Todesprozesse). Geburts- und Todesprozesse nennt man
solche MKSZ, deren Zustandsraum I = N 0 ist und für die die Q-Matrix die Form


λi , falls j = i + 1,
(3.2.1)
qi,j = µi , falls j = i − 1, i ≥ 1,


0
sonst, wenn i 6= j,
besitzt. Dies ist ein Prozess auf N0 , der mit Rate λi um 1 größer wird und mit Rate µi um 1
kleiner, wenn er gerade in i ist. Die λ i werden als Geburtsraten, die µi als Sterberaten bezeichnet.
Sind alle µi = 0 (bzw. alle λi = 0), dann heisst die MKSZ (reiner) Geburtsprozess (bzw. (reiner)
Todesprozess).
Geburts- und Todesprozesse sind Nächstnachbarschaftsirrfahrten auf N 0 in stetiger Zeit und
werden zum Beispiel als (sehr einfache) Modelle zur Beschreibung der zeitlichen Evolution der
Größe einer Population verwendet.
3
36
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Beispiel 3.2.2 (M/M/c-Warteschlange). Wir betrachten eine Warteschlange mit exponentiell verteilten Zwischenankunftszeiten der Kunden (dafür steht das erste ‘M ’; es erinnert an
‘Markov’), exponentiell verteilten Bedienzeiten (dafür steht das zweite ‘M ’) und c ∈ N Bedienern (dafür steht das ‘c’). Wir setzen voraus, dass die Gesamtheit aller Zwischenankunftszeiten
und Bedienzeiten unabhängig sind und dass die Zwischenankunftszeiten und die Bedienzeiten
jeweils die gleiche Verteilung haben. Die Schlange funktioniert nach dem Prinzip FIFO, also ‘first
in – first out’. Wenn andere Verteilungen für die Zwischenankunftszeiten bzw. die Bedienzeiten
gewählt werden als eine exponentielle, spezifiziert man dies im ersten bzw. zweiten Argument.
Allerdings verliert man dabei im Allgemeinen die Markoveigenschaft.
Wir betrachten die Anzahl X(t) der Kunden in der Warteschlange zum Zeitpunkt t ∈ [0, ∞).
Da wir die Exponentialverteilung zugrunde legen, ist (X(t)) t∈[0,∞) eine MKSZ mit Zustandsraum
N0 . Seien λ > 0 bzw. µ > 0 die Parameter der Exponentialverteilungen der Zwischenankunftsbzw. Bedienungszeiten (für jeden der c Bediener). Es ist nicht mit postitiver Wahrscheinlichkeit
möglich, dass zu einem Zeitpunkt zwei Kunden gleichzeitig eintreffen oder abgefertigt werden.
Also kann die MKSZ (X(t))t∈[0,∞) Sprünge immer nur zu benachbarten Zuständen ausführen,
ist also ein Geburts- und Todesprozess. Die Geburts- und Sterberaten sind gegeben durch
(
iµ falls 0 ≤ i ≤ c,
(3.2.2)
λi = λ für alle i ∈ N0 ,
µi =
cµ falls i ≥ c.
Man beachte, dass die Sterberate proportional zur Zahl der Kunden ist, die gerade bedient
werden.
3
Beispiel 3.2.3 (Poissonprozess). Ein wichtiger Spezialfall von Beispiel 3.2.1 ist der Poissonprozess, der als reiner Geburtsprozess mit λ i = λ für alle i ∈ N0 definiert ist, wobei λ > 0 ein
Parameter ist. Dieser Prozess wächst also genau um 1 nach unabhängigen, zum Parameter λ
exponentialverteilten Wartezeiten. Man kann mit Hilfe eines Poissonprozesses (N t )t∈[0,∞) und
einer MKDZ (Y (n))n∈N0 leicht eine MKSZ (X(t))t∈[0,∞) konstruieren, indem man X(t) = Y (Nt )
setzt. Dann benutzt man den Poissonprozess als eine zufällige Uhr. Dann ist (Y (n))n∈N0 die in
(X(t))t∈[0,∞) eingebettete MKDZ. Wir haben übrigens wiederum vorausgesetzt, dass Y n 6= Yn−1
für jedes n ∈ N gilt.
3
Bemerkung 3.2.4 (Alternative Konstruktion). Wenn Sprünge jeweils nur zu endlich vielen
anderen Zustanden möglich sind, kann eine alternative Konstruktion der MKSZ wie folgt gegeben
werden. Für jedes Paar (i, j) von verschiedenen Zuständen benötigen wir einen Poissonprozess
(Ni,j (t))t∈[0,∞) mit Parameter λi,j ∈ (0, ∞). Die Familie der Poissonprozesse wird als unabhängig
vorausgesetzt. Zu einem Zeitpunkt, in dem die MKSZ in den Zustand i springt, beginnen alle
zufälligen Uhren Ni,j mit j ∈ I \ {i} zu ticken. Sobald die erste dieser Uhren klingelt, springt die
Markovkette in den zugehörigen Zustand. Hier wiederholt sich die Sache mit diesem Zustand an
Stelle von i.
Die Idee bei dieser Konstruktion ist, dass wir wieder einen Poissonprozess erhalten, wenn
wir die Gesamtheit der Poissonprozesse
P N i,j mit j ∈ I \ {i} zu einem zusammenfassen, und der
Parameter dieses Prozesses ist λ(i) = j6=i λi,j . (Dies zeigt man als eine beliebte Übungsaufgabe.)
Insbesondere ist das erste Klingeln dieser Uhren exponentialverteilt mit diesem Parameter, wie
man leicht sieht, und ferner ist die Wahrscheinlichkeit, dass es die j-te Uhr ist, gerade gleich
λj /λ(i) .
Ein Vorteil dieser Konstruktionsvariante ist, dass die Übergangsmatrix P nicht explizit
spezifiziert werden muss, sondern dass sie sich durch einen relativen Vergleich der Raten ergibt.
3
37
3.2. BEISPIELE
Beispiel 3.2.5 (Galton-Watson-Prozess). Wir betrachten einen Verzweigungsprozess in stetiger Zeit, also das kontinuierliche Gegenstück zu dem Prozess in Beispiel 2.2.10. Jeweils nach
unabhängigen, zum Parameter Eins exponentialverteilten Wartezeiten stirbt ein Partikel und
wird durch eine zufällige Anzahl von Partikeln
ersetzt. Die Wahrscheinlichkeit, dass es genau j
P
Nachkommen hat, sei pj ∈ [0, 1], wobei j∈N0 pj = 1 sei. Die Wahl der Anzahl der Nachkommen
ist individuell pro Partikel und unabhängig. Es sei X(t) die Anzahl der Partikel zum Zeitpunkt
t ∈ [0, ∞). Wir setzen voraus, dass p1 = 0 ist, um zu vermeiden, dass die Ersetzung eines Partikels durch genau eines als ein Sprung der MKSZ angesehen wird. Dann ist (X(t)) t∈[0,∞) eine
MKSZ mit Q-Matrix
qi,j


wenn i = j,
−i,
= ipj−i+1 , wenn j > i + 1 oder j = i − 1,


0
sonst.
Insbesondere ist 0 ein absorbierender Zustand der MKSZ.
Wir diskutieren kurz die Endlichkeit des Explosionszeitpunkts
ζ. Wir setzen dabei voraus,
P
dass die erwartete Nachkommenschaft, m =
jp
,
endlich
ist.
Die eingebettete MKDZ
j
j∈N0
kann rekursiv beschrieben werden durch
Yn = Yn−1 + (Wn − 1)1l{Yn−1 >0} ,
n ∈ N,
wobei (Wn )n∈N eine u. i. v. Folge von Zufallsgrößen mit Verteilung (pj )j∈N0 ist. Dann ist
0 ≤ Y n ≤ Y0 +
n
X
k=1
(Yk − Yk−1 ) ≤ Y0 +
n
X
(Wk − 1)1l{Yk−1 >0} ≤ Y0 + 1l{Yn−1 >0}
k=1
n
X
(Wk − 1).
k=1
Nach dem Gesetz der Großen Zahlen haben wir also lim sup n→∞ Yn /n ≤ max{0, m − 1}. Daher
ist für jedes i ∈ I
Pi
X 1 Y −1
X 1
X 1
n
= ∞ = 1.
= ∞ = Pi
= ∞ = Pi
c Yn
Yn
n n
n∈N
n∈N
n∈N
Nach Lemma 3.1.1 ist der Explosionszeitpunkt ζ endlich, P i -fast sicher für jedes i ∈ I.
3
Beispiel 3.2.6 (Stochastische Vielteilchensysteme). Wenn man ein stochastisches System
vieler Teilchen im Raum modellieren möchte, dann bietet sich der Zustandsraum I = Λ S an,
wobei Λ ⊂ Zd eine große Box ist (etwa Λ = [−N, N ]d ∩ Zd ) und S eine endliche Menge von
Eigenschaften, die ein Teilchen haben kann. Wir betrachten dann eine Konfiguration von genau
einem Teilchen in jedem Punkt der Box Λ, das jeweils eine Eigenschaft s ∈ S besitzt, etwa einen
Spin, eine Farbe, eine Meinung, ein Geschlecht oder andere Merkmale, je nach Anwendung.
Jedes der Teilchen wechselt individuell seine Eigenschaft zufällig zu gewissen zufälligen Zeiten.
Um die Markoveigenschaft des gesamten Teilchensystems zu erhalten, nehmen wir nat ürlich an,
dass die Wartezeiten exponentiell verteilt sind. Der Eigenschaftswechsel kann abhängig sein von
den Eigenschaften der anderen Teilchen, und ein interessanter Fall besteht darin, dass dieser
Wechsel nur von den Eigenschaften der Nachbarn abhängt.
Eine andere Möglichkeit ist, eine beliebig große Anzahl von Teilchen in der Box Λ anzunehmen und nur zu registrieren, wie viele Teilchen mit einer gegebenen Eigenschaft in einem
38
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
gegebenen Gitterpunkt sitzen. (Hierfür ist ein größerer Zustandsraum als ΛS notwendig.) Zusätzlich kann man eine zufällige individuelle Migration jedes einzelnen Teilchens zulassen. Dies wäre
ein räumlich dynamischer Verzweigungsprozess.
Die Konstruktion eines solchen Vielteilchensystems kann im Prinzip ohne große Probleme
wie oben oder wie in Bemerkung 3.2.4 durchgeführt werden. Allerdings ist man hauptsächlich
interessiert an räumlich unendlichen Systemen mit eventuell unendlich vielen Teilchen. Hier
muss man zusätzliche Bedingungen an die Übergangsraten stellen, und die Konstruktion wird
technisch aufwendig.
3
Beispiel 3.2.7 (M/E2 /1-Warteschlange). Eine M/Ek /1-Warteschlange besitzt einen Schalter, exponentiell verteilte Zwischenankunftszeiten der Kunden, und Bedienzeiten, die die sogenannte Erlang-Verteilung Ek besitzen, also die Verteilung einer Summe von k unabhängigen
exponentialverteilten Zufallsgrößen mit dem selben Parameter, sagen wir µ ∈ (0, ∞). Ansonsten
gelten die in Beispiel 3.2.2 beschriebenen Voraussetzungen.
Die Zahl der Kunden in einer M/E2 /1-Warteschlange ist keine MKSZ, da die E 2 -Verteilung
nicht gedächtnislos ist. Wegen der besonderen Eigenschaft der Erlang-Verteilung lässt sich aber
eine MKSZ mit größerem Zustandsraum so definieren, dass die Zahl der Kunden in einer
M/E2 /1-Warteschlange eine Funktion jener MKSZ ist.
Der “Trick” besteht darin, dass man die E 2 -verteilte Bedienungszeit künstlich in zwei Phasen
zerlegt, die jeweils exponentiell mit Parameter 2µ und unabhängig sind. Merkt man sich nun
zusätzlich zur Zahl der Kunden noch, in welcher Phase der Bedienung das System sich befindet,
so hat man eine MKSZ vorliegen, da die Zeitdauern der einzelnen Phasen gedächtnislos sind.
Der Zustandsraum dieser MKSZ ist
E = {0} ∪ N × {1, 2} ,
(3.2.3)
wobei “0” bedeutet, dass kein Kunde im System ist, und (n, i), dass n ∈ N Kunden im System
sind und der Kunde, der gerade bedient wird, sich in der Bedienungsphase i ∈ {1, 2} befindet.
Übergänge von Phase 1 zur Phase 2 finden immer mit Rate 2µ statt. Mit derselben Rate 2µ
endet die Bedienungszeit eines Kunden, wenn er sich in Phase 2 befindet, worauf sich die Zahl der
Kunden um Eins verringert und der nächste Kunde in Phase 1 bedient wird. Die Ankunftsrate
ist immer λ.
3
Beispiel 3.2.8 (M/G/1-Warteschlange). Sei X(t) die Anzahl der Kunden im System zur
Zeit t ≥ 0 bei einer M/G/1-Warteschlange, siehe auch Beispiel 3.2.2. Hierbei steht ‘M’ daf ür,
dass die Zwischenankunftszeiten der Kunden exponentiell verteilt sind, aber das ‘G’ steht daf ür,
dass die Verteilung der Bedienzeiten nicht näher spezifiziert wird (‘general’). Der stochastische
Prozess (X(t))t≥0 besitzt also in der Regel nicht die Markoveigenschaft. Wenn aber 0 < S 1 <
S2 < . . . die (zufälligen) Zeitpunkte sind, an denen die Bedienungszeit eines Kunden endet, dann
definiert Yn := X(Sn +) (wobei S0 = 0) eine MKDZ (Yn )n∈N0 auf I = N0 , da die Zwischenankunftszeiten der Kunden gedächtnislos sind. Mit anderen Worten, (Y n )n ist eine in (X(t))t≥0
eingebettete Markovkette.
Wir werden nun die Übergangswahrscheinlichkeiten pi,j dieser MKDZ berechnen und sie
auf Rekurrenz untersuchen. Sei G die Verteilungsfunktion der Bedienungszeit. Wir nehmen an,
dass G(0) = 0 ist (d. h. die Bedienzeiten nichtnegativ sind mit Wahrscheinlichkeit Eins) und
der Erwartungswert ν der Bedienungszeit endlich ist. Den Parameter der exponentialverteilten
Zwischenankunftszeiten nennen wir λ ∈ (0, ∞). Sei Y 0 die Zahl der Kunden, die am Ende einer
Bedienungszeit noch im System sind. Den nächsten Kunden, der bedient wird, bezeichnen wir
39
3.2. BEISPIELE
mit der Nummer 1 usw. Sei zunächst i ≥ 1 und K die Zahl der Kunden, die während der
Bedienungszeit B des ersten Kunden eintreffen. Dann gilt
pi,j = P(Y1 = j | Y0 = i)
= P(K = j − i + 1 | Y0 = i)
(R ∞
0 Pi (K = j − i + 1 | B = x) dG(x),
=
0
falls j − i + 1 ≥ 0,
sonst.
(3.2.4)
Wir berechnen nun den Integranden: Im Fall j − i + 1 ≥ 1 gilt
Pi (K = j − i + 1 | B = x) = Pi (K ≥ j − i + 1 | B = x) − Pi (K ≥ j − i + 2 | B = x).
(3.2.5)
Die Wahrscheinlichkeit, dass innerhalb der Zeit x mindestens k Kunden eintreffen, ist gleich
der Wahrscheinlichkeit, dass die Summe von k unabhängigen Exp(λ)-verteilten Zufallsvariablen
einen Wert kleiner oder gleich x annimmt. Diese ist gegeben durch
Z x k k−1
λ y
P(K ≥ k | B = x) =
e−λy dy,
k ∈ N.
(3.2.6)
0 (k − 1)!
Setzt man dies mit k = j − i + 1 bzw. k = j − i + 2 in (3.2.5) ein, so ergibt sich
Z x j−i+2 j−i+1
Z x j−i+1 j−i
λ
y
λ
y
−λy
e
dy −
e−λy dy.
P (K = j − i + 1|B = x) =
(j − i)!
(j − i + 1)!
0
0
(3.2.7)
Indem man das erste Integral partiell integriert, sieht man, dass die rechte Seite von (3.2.7)
gleich (λx)j−i+1 e−λx /(j − i + 1)! ist. Dies gilt auch im Fall j − i + 1 = 0. Die Zahl der im
Zeitraum x ankommenden Kunden ist daher Poisson-verteilt mit Parameter λx. Somit gilt f ür
i ∈ N und j − i + 1 ≥ 0:
Z ∞
(λx)j−i+1 −λx
e
dG(x).
(3.2.8)
pi,j =
(j − i + 1)!
0
Weiter gilt (wie man leicht einsieht) p 0,j = P(K = j) = p1,j . Mit der Abkürzung
Z ∞
(λx)r −λx
cr = P(K = r) =
e
dG(x),
r ∈ N0 ,
r!
0
folgt

P = (pij )i,j∈N0




=



c0
c0
0
0
0
..
.
c1
c1
c0
0
0
..
.
c2
c2
c1
c0
0
..
.
c3
c3
c2
c1
c0
..
.
c4
c4
c3
c2
c1
..
.
...
...
...
...
...
..
.
(3.2.9)









(3.2.10)
Offenbar sind alle cr positiv. Daher ist die Markovkette irreduzibel und aperiodisch. Nach
Satz 2.5.5 existiert genau eine invariante Verteilung.
Zur Abkürzung definieren wir
ci =
∞
X
j=i+1
cj = P(K ≥ i + 1),
i ∈ N0 .
(3.2.11)
40
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Dann gilt
EK =
∞
X
i=0
und
ici =
∞ Z
X
i
i=0
∞
0
∞
X
i=0
(λx)i −λx
e
dG(x) =
i!
ci =
∞
X
Z
∞
λx dG(x) = λν =: ρ.
(3.2.12)
0
P(K ≥ i + 1) = EK = ρ.
(3.2.13)
i=0
Die Zahl ρ heißt Verkehrsdichte der Warteschlange. Große Werte von ρ entstehen durch große
λ, d. h. durch kurze mittlere Kundenabstände 1/λ oder durch langsame Bedienung d. h. große
ν. Es ist daher zu erwarten, dass große ρ zu langen Warteschlangen führen. Wir werden gleich
sehen, dass der Wert ρ = 1 kritisch ist in dem Sinne, dass für kleinere Werte die Markovkette
positiv rekurrent ist und für größere nicht. Dies ist nicht verwunderlich, denn ρ = 1 bedeutet
gerade, dass die erwartete Bedienungszeit ν gleich der erwarteten Zwischenankunftszeit λ −1 ist.
Um dies alles zu zeigen, lösen wir das lineare Gleichungssystem π = πP . Schreibt man die
einzelnen Gleichungen untereinander und addiert die ersten k für alle k ∈ N, dann erhält man
das äquivalente Gleichungssystem
π1 c0 = π 0 c0
π2 c0 = π 0 c1 + π 1 c1
Wenn nun
P∞
i=0
(3.2.14)
π3 c0 = π 0 c2 + π 1 c2 + π 2 c 1
..
..
.
.
πi = 1 ist, dann kann man alle Gleichungen addieren und erhält
(1 − π0 )c0 = π0 ρ +
∞
X
i=1
πi
∞
X
cj = π0 ρ + (1 − π0 )(ρ − c0 ).
(3.2.15)
j=1
Auflösen nach π0 ergibt π0 = c0 − ρ + c0 = 1 − ρ. Durch sukzessives Einsetzen in (3.2.14) erhält
man rekursiv alle πi für i ∈ N. Offenbar muss ρ < 1 sein, damit eine invariante Verteilung
existiert, denn sonst wäre π0 ≤ 0. Also ist die Markovkette im Fall ρ ≥ 1 nicht positiv rekurrent.
Sei umgekehrt 0 < ρ < 1. Setzt man π0 = 1 − ρ und berechnet die πi aus (3.2.14) rekursiv, dann
sind
äquivalent zu π = πP ist, bleibt nur zu zeigen, dass
P∞ offenbar alle πi positiv. Da (3.2.14)
Pk
π
=
1
ist.
Setzt
man
s
=
π
k
i=0 i
i=1 i und addiert die ersten k Gleichungen von (3.2.14),
dann erhält man
k−1
k−1
k−i
X
X
X
sk c0 = (1 − ρ)
cj +
cj
πi
j=0
i=1
j=1
(3.2.16)
≤ (1 − ρ)ρ + sk−1 (ρ − c0 )
= (1 − ρ)ρ + sk−1 (c0 − (1 − ρ)).
Hieraus folgt
1−ρ
(ρ − sk−1 ),
(3.2.17)
c0
P∞
P∞
woraus sk−1 ≤ ρ für alle k und somit die Endlichkeit von i=0 πi folgt. Falls i=0 πi 6= 1 ist,
normiert man die πi so,Pdass die Summe 1 ist, und sieht wie vorher, dass das normierte π 0 gleich
1 − ρ ist. D. h. es gilt ∞
i=0 πi = 1 (man musste also gar nicht normieren!). Dies zeigt, dass die
Markovkette im Fall ρ < 1 positiv rekurrent ist.
0 < πk = sk − sk−1 ≤
Für weitere Diskussionen hierzu verweisen wir auf [HS82, S. 251] und [KT81, S. 502 ff]. 3
3.3. DEFINITIONEN UND ERSTE ERGEBNISSE
3.3
41
Definitionen und erste Ergebnisse
Nun zurück zur Theorie. Gegeben sei als Zustandsraum eine abzählbare (nichtleere) Menge I. In
diesem Abschnitt führen wir das Konzept einer MKSZ ein und viele damit verbundene Objekte
wie Familien von Übergangsmatrizen und die schon erwähnte Q-Matrix.
Zunächst führen wir das Analogon der Übergangsmatrix P einer MKDZ einführen. Während
im zeitlich diskreten Fall durch eine Verteilung ν und eine stochastische Matrix P die Verteilung
der MKDZ mit Startverteilung ν und Übergangsmatrix P festgelegt ist, ist nicht klar, ob dies
im stetigen Fall mit ν und der Matrix P (1) := (P i (X(1) = j))i,j∈I auch so ist, denn aus P (1)
kann man zwar P (n) für n ∈ N durch P (n) = P (1)n berechnen, aber wie berechnet man z. B.
P (1/2) aus P (1)? Um diese Probleme zu umgehen, definieren wir gleich eine ganze geeignete
Familie (P (t))t≥0 von Übergangsmatrizen. Um flexibler zu sein, müssen die Zeilensummen nicht
unbedingt gleich Eins sein.
Definition 3.3.1 ((Sub-)markovsche Halbgruppe). Sei I eine abzählbare, nichtleere Menge.
Eine Familie (P (t))t>0 von Matrizen (Pi,j (t))i,j∈I heißt submarkovsche Halbgruppe auf I, wenn
für alle i, j ∈ I und alle t, s > 0 gilt:
(i) Pi,j (t) ≥ 0,
(ii)
P
k∈I
Pi,k (t) ≤ 1,
(iii) Pi,j (t + s) =
P
k∈I
Pi,k (t)Pk,j (s) (Chapman-Kolmogorov-Gleichung)
Die Familie (P (t))t>0 heißt markovsch, wenn zusätzlich in (ii) das Gleichheitszeichen für alle
i ∈ I gilt, und sie heißt standard, wenn zusätzlich zu (i) - (iii) gilt:
(iv) limt↓0 Pij (t) = δij (=: Pij (0)) für alle i, j ∈ I.
Eine markovsche Halbgruppe besteht also aus stochastischen Matrizen. Wir werden später
sehen, dass die Bedingung (iv) schon gilt, wenn sie nur für alle i = j gefordert wird.
Nun bringne wir die Definition einer MKSZ. Wir wollen die Möglichkeit einer Explosion in
endlicher Zeit (siehe Abschnitt 3.1) nicht a priori ausschließen. Im Falle einer Explosion gibt es
vielfältige Möglichkeiten, den Prozess als MKSZ weiterlaufen zu lassen, z. B. durch unmittelbares
Springen in einen bestimmten Zustand mit “Neustart” der Kette. Oft will man aber auch den
Fall betrachten, dass der Prozess im Zustand der Explosion verharrt. Dies erreicht man dadurch,
dass man einen zusätzlichen Zustand ∂ (Grab, Sarg) zu I hinzufügt und vereinbart, dass sich
der Prozess nach der Explosion für immer in ∂ befindet. Dies war der Grund, dass wir in der
Definition einer submarkovschen Halbgruppe zugelassen haben, dass die Zeilensummen kleiner
als Eins sind.
42
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Definition 3.3.2 (Markovkette in stetiger Zeit). Sei (P (t)) t>0 eine submarkovsche Halbgruppe auf I. Weiter seien ∂ ∈
/ I und ν eine Wahrscheinlichkeitsverteilung auf I ∪ {∂}.
Dann heißt ein I ∪ {∂}-wertiger stochastischer Prozess (X(t)) t≥0 eine Markovkette in stetiger Zeit (MKSZ) mit Startverteilung ν und Halbgruppe (P (t)) t>0 , wenn für alle n ∈ N, und
alle 0 ≤ t1 < t2 < · · · < tn < t und alle i1 , . . . , in , i ∈ I gelten:
(i) P X(t) = i | X(t1 ) = i1 , . . . , X(tn ) = in = Pin ,i (t − tn ), wenn die linke Seite definiert ist,
(ii) P X(0) = i = νi für alle i ∈ I ∪ {∂},
(iii) P X(t) = ∂ | X(t1 ) = i1 , . . . , X(tn−1 ) = in−1 , X(tn ) = ∂ = 1.
Bemerkung 3.3.3. Eine submarkovsche Halbgruppe auf I läßt sich zu einer markovschen auf
I ∪ {∂} fortsetzen durch die Definition
(
1,
falls i = ∂ und t > 0,
(3.3.1)
Pi,∂ (t) =
P
1 − j∈I Pi,j (t), falls i ∈ I und t > 0.
In diesem Fall gilt die Bedingung (i) aus Definition 3.3.2 automatisch auch für i1 , . . . , in , i ∈ I ∪
{∂} (Übungsaufgabe). Die Fortsetzung ist die einzig mögliche genau dann, wenn die Halbgruppe
nicht markovsch auf I ist (Übungsaufgabe). Es ist klar, dass (P (t)) t>0 genau dann standard auf
I ist, wenn die Fortsetzung auf I ∪ {∂} standard ist.
3
Satz 3.3.4. Sei ν eine Verteilung auf I ∪ {∂}, und sei (P (t)) t>0 submarkovsch. Dann existiert
eine MKSZ X = (X(t))t≥0 zu ν und (P (t))t>0 im Sinne von Definition 3.3.1. Für diese MKSZ
gilt für alle n ∈ N0 , alle 0 = t0 < t1 < · · · < tn und alle i0 , . . . , in ∈ I:
P X(t0 ) = i0 , X(t1 ) = i1 , . . . , X(tn ) = in = νi0 Pi0 ,i1 (t1 − t0 ) · · · Pin−1 ,in (tn − tn−1 ).
(3.3.2)
Insbesondere ist die Verteilung von X eindeutig durch ν und (P (t)) t>0 bestimmt.
Beweis. Dies folgt mit Hilfe des Satzes 1.3.3 von Kolmogorov. Wir verzichten auf eine genauere
Begründung.
Bemerkung 3.3.5. Wie im Fall einer MKDZ kann man (3.3.2) auch als Definition einer MKSZ
zu ν und (P (t))t>0 wählen.
3
Die bisherigen Aussagen lassen vermuten, dass sich MKSZ im wesentlichen wie MKDZ
behandeln lassen. Dies ist insofern richtig, als zum Beispiel (X(ns)) n∈N0 für festes s > 0 eine
MKDZ mit Startverteilung ν und Übergangsmatrix P (s) ist, wenn (X(t)) t≥0 eine MKSZ zu
ν und (P (t))t>0 ist. Deutliche Unterschiede gibt es immer dort, wo man überabzählbar viele
Zeitindizes gleichzeitig betrachtet, z. B. bei der Betrachtung der Zufallsvariable sup s∈[0,1] X(s),
etwa wenn I = N ist.
Ein weiterer Unterschied besteht offenbar darin, dass wir das einfache Objekt P im diskreten Fall durch ein kompliziertes – nämlich (P (t))t>0 – ersetzen müssen. Während man P sofort
43
3.3. DEFINITIONEN UND ERSTE ERGEBNISSE
ansieht, ob es eine Übergangsmatrix ist, ist dies für (sub-)markovsche Halbgruppen viel schwieriger. In Abschnitt 3.1 sahen wir bereits, dass die Beschreibung von MKSZ durch die Q-Matrix
viel günstiger ist, siehe (3.1.3). Q beschreibt das Verhalten von P ij (t) für infinitesimal kleine
t > 0. Da man die komplette Halbgruppe aus der Kenntnis von (P i,j (t))0<t≤t0 für alle i, j ∈ I
und festes t0 > 0 rekonstruieren kann, ist es plausibel, dass dies auch aus der Kenntnis von
limt↓0 t−1 Pi,j (t) = qi,j möglich ist. Inwieweit dies stimmt, werden wir später sehen. Zunächst
beweisen wir die Existenz der Grenzwerte q i,j . Dazu – und im folgenden fast immer – setzen wir
voraus, dass (P (t))t>0 standard ist. Dies gilt nicht automatisch, aber in Anwendungsbeispielen
praktisch immer. Für den Nichtstandardfall konsultiere man [Ch67].
Die Voraussetzung “standard” besagt, dass die Kette nach einer kurzen Zeit mit großer
Wahrscheinlichkeit im Startzustand ist. Man beachte jedoch, dass auch für kleine t > 0 die Zahl
Pi,j (t) nicht gleich der Wahrscheinlichkeit ist, bis zum Zeitpunkt t nicht gesprungen zu sein. Wir
zeigen zunächst, dass im Standardfall für jede i, j ∈ I die Abbildung t 7→ Pi,j (t) gleichmäßig
stetig ist. Ohne die Voraussetzung “standard” braucht t 7→ P i,j (t) nicht einmal messbar zu sein
(siehe [Ch67]).
Lemma 3.3.6. Sei (P (t))t≥0 standard. Dann gilt für jedes i ∈ I
X
Pi,j (t + h) − Pi,j (t) = 0.
lim sup
h↓0 t≥0
(3.3.3)
j∈I
Insbesondere ist für i, j ∈ I die Abbildung t 7→ Pi,j (t) gleichmäßig stetig auf [0, ∞).
Beweis. Sei h > 0. Wir schätzen ab:
X
XX
Pi,k (h)Pk,j (t) − δi,k Pk,j (t)
|Pi,j (t + h) − Pi,j (t)| =
j∈I
j∈I k∈I
≤
XX
|Pi,k (h) − δi,k |Pk,j (t) =
j∈I k∈I
≤
X
X
k∈I
|Pi,k (h) − δi,k | = 1 − Pi,i (h) +
k∈I
|Pi,k (h) − δi,k |
X
X
Pk,j (t)
j∈I
Pi,k (h) ≤ 2(1 − Pi,i (h)).
k∈I\{i}
(3.3.4)
Nun folgt die Aussage, da der Term am Ende der Ungleichungskette nicht von t abhängt und
für h ↓ 0 gegen Null konvergiert.
Nun bringen wir endlich den Beweis der Existenz der Grenzwerte in (3.1.3).
Satz 3.3.7. Sei (P (t))t≥0 standard. Dann existiert für alle i, j ∈ I der Grenzwert
qi,j = lim
h↓0
Pi,j (h) − δi,j
.
h
(3.3.5)
Im Fall i 6= j gilt 0 ≤ qi,j < ∞, im Fall i = j gilt 0 ≥ qi,i ≥ −∞. Ferner gilt für alle i ∈ I:
X
qi,j ≤ −qi,i =: qi .
(3.3.6)
j∈I : j6=i
Beweis. (Siehe z. B. [KT81] oder [GS75]).
44
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
1. Teil: i = j. Definiere
qi0 := sup
h>0
Wir werden zeigen, dass
so gewählt, dass
qi0
1 − Pi,i (h)
∈ [0, ∞].
h
= −qi,i = limh↓0 h−1 (1 − Pi,i (h)) gilt. Seien c < qi0 und 0 < t0 < ∞
1 − Pi,i (t0 )
> c,
t0
und seien 0 < τ < t0 und n ∈ N so gewählt, dass
h t
t0 0
,
.
τ∈
n+1 n
Dann gilt
1
1
(1 − Pi,i (t0 )) ≤
1 − (Pi,i (τ ))n Pi,i (t0 − nτ )
t0
t0
n(1 − Pi,i (τ )) 1 − Pi,i (t0 − nτ )
1 − (Pi,i (τ ))n 1 − Pi,i (t0 − nτ )
+
≤
+
,
≤
t0
t0
nτ
t0
c<
wobei wir beim zweiten Ungleichheitszeichen die Chapman-Kolmogorov-Gleichung, beim dritten
die allgemeine Ungleichung 1 − ab ≤ 2 − a − b, falls a, b ∈ [0, 1] mit a = (P i,i (τ ))n und b =
Pii (t0 − nτ ) und beim vierten die Beziehung 1 − a n = (1 − a)(1 + a + a2 + · · · + an−1 ) ≤ n(1 − a)
für a = Pi,i (τ ) verwendet haben.
Bei festem t0 lassen wir nun τ gegen Null und damit n → ∞ gehen, und somit konvergiert
der letzte Summand wegen der “standard” Eigenschaft gegen Null. Es folgt
c < lim inf
τ ↓0
1 − Pi,i (τ )
≤ qi0 .
τ
Da c < qi0 beliebig war, haben wir sogar
qi0 = lim
τ ↓0
1 − Pi,i (τ )
,
τ
wie behauptet.
2. Teil: i 6= j. Sei X = (X(t))t≥0 eine MKSZ mit submarkovscher standard Halbgruppe (P (t)) t≥0
und Start in i. Definiere für i, j ∈ I, n ∈ N und h > 0
(n)
j Pi,i (h)
= P Xnh = i, Xrh 6= j für alle r = 1, . . . , n − 1
(n)
fij (h) = P(Xnh = j, Xrh 6= j für alle r = 1, . . . , n − 1 .
Sei ε ∈ (0, 1/3) vorgegeben. Da (P (t)) t≥0 standard ist, existiert ein t0 = t0 (ε) > 0, so dass für
alle t ∈ [0, t0 ] gilt: 1 − Pi,i (t) < ε, 1 − Pj,j (t) < ε und Pi,j (t) < ε. Seien n ∈ N und h > 0 gegeben
mit nh ≤ t0 , und sei u ∈ [nh, t0 ]. Dann haben wir
ε > Pi,j (u) ≥
n
X
r=1
(r)
fi,j (h)Pj,j (u
− rh) ≥ (1 − ε)
n
X
r=1
(r)
fi,j (h),
also gilt
n
X
r=1
(r)
fi,j (h) ≤
ε
.
1−ε
(3.3.7)
45
3.3. DEFINITIONEN UND ERSTE ERGEBNISSE
Außerdem haben wir
(r)
j Pi,i (h)
Pi,i (rh) =
+
r−1
X
(m)
fi,j (h)Pj,i ((r − m)h),
r = 1, . . . , n.
(3.3.8)
m=1
Also folgt mit (3.3.7):
(r)
j Pi,i (h)
≥ Pi,i (rh) −
r−1
X
(m)
fi,j (h) ≥ 1 − ε −
m=1
ε
1 − 3ε
≥
.
1−ε
1−ε
(3.3.9)
Daher haben wir
Pi,j (u) ≥
n−1
X
(r)
j Pi,i (h)Pi,j (h)Pj,j (u
− (r + 1)h) ≥ n(1 − 3ε)Pi,j (h),
(3.3.10)
r=0
(0)
wobei wir j Pi,i (h) = 1 setzten und bei der letzten Ungleichung (3.3.9) verwendeten.
Für festes u ∈ (0, t0 ] wähle nun h > 0 und n ∈ N mit n ≥ 2, so dass u ∈ [nh, (n + 1)h].
Dann folgt n ≥ (u − h)/h und aus (3.3.10):
Pi,j (h)
Pi,j (u)
≥ (1 − 3ε)
.
u−h
h
(3.3.11)
Wir lassen für festes u > 0 beidseitig h ↓ 0 gehen und erhalten
∞>
Pi,j (h)
1 Pi,j (u)
≥ lim sup
.
1 − 3ε u
h
h↓0
(3.3.12)
Nun geht u ↓ 0:
Pi,j (h)
Pi,j (u)
1
lim inf
≥ lim sup
.
1 − 3ε u↓0
u
h
h↓0
(3.3.13)
Mit ε ↓ 0 folgt, dass qi,j = limh↓0 Pi,j (h)/h existiert und endlich ist.
3. Teil: Schluss. Sei M ⊂ I endlich. Dann gilt
X Pi,j (h)
1 − Pi,i (h)
≥
≥
h
h
j∈I\{i}
X
j∈M \{i}
Pi,j (h)
.
h
Die linke Seite geht
P für h ↓ 0 gegen qi = −qi,i , die rechte gegen
war, folgt −qi,i ≥ j∈I\{i} qi,j .
P
j∈M \{i} qi,j .
(3.3.14)
Da M beliebig
P
Bemerkung 3.3.8. Der Fall −qi,i > j∈I\{i} qi,j kann wirklich auftreten (siehe [Ch67, S. 275
f]). Die in Abschnitt 3.1 präsentierte Konstruktion funktioniert in diesem Fall nicht, da man in
einem solchen Fall mit positiver Wahrscheinlichkeit unendlich viele Sprünge in endlicher Zeit
vollführt.
Auch der Fall −qi,i = ∞ ist möglich ([Ch67, S. 278ff]). Dies widerspricht nicht der Standardeigenschaft von (P (t))t≥0 , obwohl – wie wir gleich sehen werden – in diesem Fall der Zustand
i sofort verlassen wird. Bei praktischen Anwendungen sind solche eher pathologischen Fälle
allerdings von geringer Bedeutung.
3
46
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Wir wollen nun im Standardfall für i ∈ I die Verteilung des Zeitpunkts des ersten Sprunges,
τ = inf{s > 0 : X(s) 6= X(0)}
(3.3.15)
bei Start in i bestimmen. Mit Pi bezeichnen wir die Wahrscheinlichkeit bei Start in i. Wir hatten
uns anschaulich
bereits überlegt, dass bei Start in i die Zeit τ exponentiell zum Parameter
P
qi = j∈I\{i} qi,j verteilt sein müsste. Dies ist allerdings ohne weitere Voraussetzungen nicht
richtig. Man braucht eine Bedingung an die Trajektorien, die sichert, dass diese nicht zu wild
aussehen. Die Tatsache, dass (P (t)) t≥0 standard ist, garantiert dies nicht. Statt dessen benötigen
wir den Begriff der Separabilität. Wir erinnern daran, dass unsere MKSZ X = (X(t)) t∈[0,∞) auf
einem Wahrscheinlichkeitsraum (Ω, F, P) definiert ist, und wir schreiben ω 7→ X(t, ω) f ür die
Zufallsgröße X(t).
Definition 3.3.9 (Separable MKSZ). Eine MKSZ X = (X(t)) t∈[0,∞) heißt separabel, wenn
für jede abzählbare dichte Menge M ⊂ [0, ∞) ein N ∈ F existiert mit P(N ) = 0, so dass für alle
ω∈
/ N , t ≥ 0 und ε > 0 die Zahl X(t, ω) im Abschluss der Menge {X(s, ω) : s ∈ [t−ε, t+ε]∩M }
liegt. Dabei heißt eine Menge A ⊂ I ∪ {∂} abgeschlossen, wenn A endlich ist oder ∂ enthält.
Proposition 3.3.10. Sei (P (t))t≥0 standard und X eine zugehörige separable MKSZ. Dann gilt
für die in (3.3.15) definierte Zeit τ
Pi (τ ≥ t) = e−qi t
für alle t ≥ 0,
(3.3.16)
wobei wir die Konvention ∞ · 0 = 0 benutzen.
Beweis. Für t = 0 ist die Behauptung klar. Sei t > 0 und zunächst qi < ∞. Dann gilt
Pi (τ ≥ t) = Pi X(s) = i für alle s ∈ [0, t)
= Pi X(k2−n t) = i für alle n ∈ N und alle k = 0, . . . , 2n − 1
(3.3.17)
= lim Pi X(k2−n t) = i für alle k = 0, . . . , 2n − 1
n→∞
2n −1
2n
= lim Pi,i (t2−n )
= lim 1 − qi t2−n + o(t2−n )
= e−qi t ,
n→∞
n→∞
wobei wir beim zweiten Gleichheitszeichen die Separabilität, beim dritten die Stetigkeit von P i
und beim vierten die Markoveigenschaft benutzt haben. Der Fall q i = ∞ ergibt sich leicht mit
Hilfe eines Grenzübergangs.
Wir würden nun gerne zeigen, dass bei Start in i die Zufallsgrößen τ und X(τ ) unabhängig
sind und Pi (X(τ ) = j) = qi,j /qi gilt, sofern qi > 0. Unter der Voraussetzung “standard” ist dies
selbst für separable MKSZ nicht unbedingt richtig. Bevor wir zeigen, in welchem Sinne und unter
welchen Voraussetzungen die Aussage richtig ist, definieren wir, was eine konservative Q-Matrix
ist.
Definition 3.3.11. Eine Abbildung Q : I × I → R heißt eine konservative Q-Matrix, wenn
gelten
(i) qij ≥ 0 für alle i, j ∈ I mit i 6= j,
P
(ii) qi := −qii = j∈I\{i} qij < ∞ für alle i ∈ I.
47
3.3. DEFINITIONEN UND ERSTE ERGEBNISSE
Bemerkung 3.3.12. Nicht jede Matrix Q = (q i,j )i,j∈I , die sich aus einer Standardhalbgruppe
(P (t))t≥0 wie in Satz 3.3.7 ergibt, ist konservativ. Andererseits ist Konservativität eine notwendige Voraussetzung dafür, dass das beschriebene Simulationsverfahren funktioniert. Wir werden
später sehen, dass es zu jeder konservativen Q-Matrix mindestens eine Standardhalbgruppe
(P (t))t≥0 gibt mit der Eigenschaft, dass die q i,j gleich den Grenzwerten in Satz 3.3.7 sind. 3
Satz 3.3.13. Sei (P (t))t≥0 standard und (X(t))t≥0 eine zugehörige separable MKSZ mit Start
in i ∈ I. Seien j ∈ I \ {i}, qi ∈ (0, ∞), qj < ∞ und τ wie in (3.3.15). Dann gilt für alle u ≥ 0:
qij
Pi τ ≥ u, und es existiert s > 0 : X(t) = j für alle t ∈ (τ, τ + s] = e−qi u .
(3.3.18)
qi
Ist Q konservativ, so existiert lim h↓0 X(τ + h, ω) = J(ω) fast sicher, ist unabhängig von τ und
erfüllt Pi (J = j) = qij /qi für jedes j ∈ I \ {i}.
Beweis. Wir betrachten die Ereignisse
Bγ = τ ≥ u, X(t) = j für alle t ∈ (τ, τ + γ) ,
γ > 0,
B = τi ≥ u, es existiert s > 0 : X(t) = j für alle t ∈ (τ, τ + s] .
(3.3.19)
(3.3.20)
Dann gilt Bγ ↑ B für γ ↓ 0. Wir werden zeigen, dass
Pi (Bγ ) = e−qi u
qij −qj γ
e
qi
(3.3.21)
gilt, woraus dann aufgrund der Stetigkeit von P i folgt, dass Pi (B) = e−qi u qij /qi gilt.
Fixiere u ≥ 0. Sei für n ∈ N, m ∈ N und γ := 2−m
Bn,γ : = es existiert s ≥ u, so dass X(k2−n ) = i für alle k2−n < s,
und X(k2−n ) = j für alle s ≤ k2−n < s + γ .
(3.3.22)
Dann existiert eine Menge Bγ0 mit Bn,γ ↓ Bγ0 für n → ∞, und wegen der Separabilität von X
q
gilt Pi (Bγ0 ) = Pi (Bγ ). Also genügt es zu zeigen, dass lim n→∞ Pi (Bn,γ ) = e−qi u qi,ji e−qj γ gilt. Für
n ≥ m folgt:
Pi (Bn,γ ) =
∞
X
k=bu2n c
Pi,i (2−n )
k
= Pi,j (2−n )Pj,j (2−n )
Pi,j (2−n ) Pj,j (2−n )
2n−m −1
Pi,i (2−n )
2n−m −1
1
bu2n c
1 − Pi,i (2−n )
(3.3.23)
,
wobei bxc die größte ganze Zahl echt kleiner als x sei. Wegen P i,i (2−n ) < 1 für alle hinreichend großen n konvergiert die Reihe. Die vier Faktoren sind für n → ∞ in obiger Reihenfolge
asymptotisch äquivalent zu
qi,j 2−n ,
e−qj γ ,
e−qi u ,
1
.
qi 2−n
Also ist die erste Behauptung, (3.3.21), bewiesen.
Ist Q konservativ, dann folgt die Existenz des Grenzwerts J(ω) und die Formel für die Verteilung, indem man in (3.3.18) u = 0 setzt und über alle j ∈ I \ {i} summiert. Die Unabhängigkeit
ist klar, da
qi,j
Pi (J = j | τ ≥ u) =
qi
48
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
nicht von u abhängt.
Mit Satz 3.3.13 ist die Konstruktion aus Abschnitt 3.1 leider immer noch nicht vollständig
gerechtfertigt, auch nicht im konservativen Fall. Dazu müsste man wissen, dass z. B. auch der
zweite Sprung gegeben den zweiten Zustand unabhängig von der Zeit ist, die man im ersten
und zweiten Zustand verbracht hat. Diese Tatsache ist richtig und lässt sich zum Beispiel durch
eine Erweiterung von Satz 3.3.13 zeigen, indem man die gemeinsame Verteilung der ersten k
Sprünge und der Sprungzeiten berechnet, was recht mühsam ist. Daher verzichten wir hier auf
eine Durchführung dieser Argumente.
Bemerkung 3.3.14 (Starke Markoveigenschaft). Alternativ lässt sich die Unabhängigkeit
des zweiten Sprunges von der Wartezeit und dem zweiten Zustand auch aus der starken Markoveigenschaft herleiten, die wir aber weder formulieren noch beweisen wollen. F ür eine exakte
Definition siehe z. B. [Ch67]; sie ist ähnlich dem diskreten Fall. Wir betonen, dass die starke
Markoveigenschaft ohne Separabilität im Allgemeinen nicht gilt und selbst im separablen Fall
nicht gelten muss; z. B. dann nicht, wenn man als Stoppzeit τ = inf{s ≥ 0 : X(s) = ∂} wählt
und ein Rücksprung nach I möglich ist. Die Rücksprungverteilung kann nämlich explizit von
dem Verhalten von X kurz zuvor abhängen, ohne dass dies die Markoveigenschaft zerstört. Die
starke Markoveigenschaft kann daran scheitern, dass die “Kompaktifizierung” I ∪ {∂} von I zu
grob ist. Die Theorie der Ray-Knight-Kompaktifizierung zeigt, wie man, abhängig von der Standardhalbgruppe (P (t))t≥0 , die Menge I so kompaktifiziert, dass eine MKSZ mit Werten in der
Kompaktifizierung existiert mit den geforderten endlich-dimensionalen Verteilungen, so dass sie
rechtsstetige Pfade hat und die starke Markoveigenschaft erfüllt. Der interessierte Leser sei auf
[Wi79] verwiesen.
3
3.4
Vorwärts- und Rückwärtsgleichungen
Als nächstes stellen wir uns die Frage, ob und gegebenenfalls wie man aus einer konservativen
Q-Matrix die Standardhalbgruppe (P (t)) t≥0 berechnen kann.
Satz 3.4.1 (Rückwärtsgleichung). Sei (P (t))t≥0 standard mit konservativer Q-Matrix Q.
Dann ist t 7→ Pi,j (t) auf [0, ∞) stetig differenzierbar für alle i, j ∈ I, und es gelten
P 0 (t) = QP (t),
t ≥ 0,
und
P (0) = I,
(3.4.1)
wobei Id die Identität auf I ist (d. h. Idi,j = δi,j ) und die Ableitung komponentenweise zu
verstehen ist.
Beweis. Für h > 0 und s ≥ 0 gilt:
i
Pi,j (h + s) − Pi,j (s)
1 hX
=
Pi,k (h)Pk,j (s) − Pi,j (s)
h
h
k∈I
i
X
1h
=
Pi,i (h) − 1 Pi,j (s) +
Pi,k (h)Pk,j (s) .
h
(3.4.2)
k∈I\{i}
Falls die eventuell unendliche Summe mit dem Grenzwert h ↓ 0 vertauscht werden darf, so
49
3.4. VORWÄRTS- UND RÜCKWÄRTSGLEICHUNGEN
erhalten wir aus (3.4.2) leicht:
lim
h↓0
X
X
Pi,j (h + s) − Pi,j (s)
= qi,i Pi,j (s) +
qi,k Pk,j (s) =
qi,k Pk,j (s).
h
(3.4.3)
k∈I
k∈I\{i}
Wir
P rechtfertigen nun die Vertauschung. Seien ε > 0 und J ⊂ I mit i ∈ J und |J| < ∞, so dass
k∈I\J qi,k < ε/2 (hier benutzen wir, dass Q konservativ ist). Dann gilt
X P (h)
X P (h) X
i,k
i,k
qi,k
− qi,k Pk,j (s) ≤ +
h
h
k∈I\J
k∈I\J
k∈I\J
1 − P (h)
X Pi,k (h) ε
i,i
−
<
+
h
h
2
k∈J\{i}
X
X
ε
ε
h↓0
qi,k + < ε,
−→ −qi,i −
qi,k + =
2
2
(3.4.4)
k∈I\J
k∈J\{i}
wobei wir beim letzten Gleichheitszeichen die Konservativität von Q benutzten. Damit ist die
Konvergenz in (3.4.3) gerechtfertigt, und es folgt
P 0 (s) = QP (s),
(3.4.5)
wobei allerdings der Strich zunächst nur als rechtsseitige Ableitung zu verstehen ist, da h > 0
war.
Aus dem Lemma 3.3.6 wissen wir, dass P i,j (·) gleichmäßig stetig
P ist. Wegen der Konservativität von Q und Beschränktheit der Pi,j (·) durch 1 konvergiert k∈I qi,k Pk,j (s) gleichmäßig für
0 (·)
alle s ∈ [0, ∞). Da gleichmäßige Grenzwerte stetiger Funktionen stetig sind, folgt, dass P i,j
stetig ist. Nun gilt aber allgemein, dass eine stetige Funktion mit existierender und stetiger
rechtsseitiger Ableitung sogar stetig differenzierbar ist (da dies nicht ganz so trivial zu beweisen ist, wie man meinen könnte, zeigen wir dies im folgenden Lemma 3.4.2). Da P (0) = Id im
Standardfall immer gilt, folgt die Behauptung.
Lemma 3.4.2. Sei f : [0, t0 ] → R stetig und auf [0, t0 ) rechtsseitig differenzierbar mit stetiger
Ableitung f + . Dann ist f auf (0, t0 ) stetig differenzierbar mit Ableitung f + .
Rt
Beweis (nach M. Schäl). Setze F (t) := f (0) + 0 f + (s) ds für t ∈ [0, t0 ]. Da nach dem
Hauptsatz der Differential- und Integralrechnung F stetig differenzierbar mit Ableitung f + ist,
genügt es zu zeigen, dass F = f ist.
Sei ϕ(t) := F (t)−f (t) für t ∈ [0, t0 ]. Dann ist ϕ stetig, ϕ(0) = 0 und ϕ+ (t) = 0 für t ∈ [0, t0 ).
Zu zeigen ist ϕ = 0. Wäre dem nicht so, dann gälte maxt∈[0,t0 ] ϕ(t) > 0 oder mint∈[0,t0 ] ϕ(t) < 0.
Es genügt, den ersten Fall zu betrachten. Wegen der Stetigkeit von ϕ existiert ein t ∗ ∈ (0, t0 ]
mit ϕ(t∗ ) = maxt∈[0,t0 ] ϕ(t). Sei γ(s) := ϕ(s) − ts∗ ϕ(t∗ ) für s ∈ [0, t∗ ]. Dann gelten
γ + (s) = −
ϕ(t∗ )
<0
t∗
für s ∈ [0, t∗ )
und
ϕ(0) = 0 = ϕ(t∗ ).
(3.4.6)
Sei s∗ ∈ [0, t∗ ) so gewählt, dass γ(s∗ ) = mins∈[0,t∗ ] γ(s). Dann folgt
γ + (s∗ ) = lim
h↓0
γ(s∗ + h) − γ(s∗ )
≥0
h
(3.4.7)
50
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
im Widerspruch zu (3.4.6).
Es gibt nicht viele Beispiele, in denen die Halbgruppe explizit bekannt ist, aber hier ist eines,
das wir als Übungsaufgabe formulieren:
Beispiel 3.4.3 (Yule-Prozess). Wir betrachten eine Bakterienkultur unter der Annahme,
dass sich die Bakterien unabhängig voneinander teilen, und zwar mit Rate λ > 0, und dass keine
Bakterien sterben. Die Anzahl der Bakterien zum Zeitpunkt t sei bezeichnet mit X(t) ∈ N, dann
ist (X(t))t∈[0,∞) eine MKSZ auf N, der sogenannte Yule-Prozess, ein reiner Geburtsprozess. Man
kann die Q-Matrix leicht explizit berechnen. Dann wird die Rückwärtsgleichung erfüllt durch
(
j−1
−λt )e−iλt , falls i ≤ j,
j−i (1 − e
Pi,j (t) =
0
sonst.
3
Satz 3.4.4 (Vorwärtsgleichung). Sei (P (t))t≥0 standard mit konservativer Q-Matrix Q.
Weiter sei
c := sup qi < ∞.
(3.4.8)
i∈I
Dann gelten
P 0 (t) = P (t)Q,
t ≥ 0,
und
P (0) = I.
(3.4.9)
Beweis. Sei h > 0. Es gilt
P (h) − δ 1 − P (h)
k,j
k,k
k,j ≤ qk ;
≤
h
h
(3.4.10)
letzteres wurde im 1. Teil des Beweises von Satz 3.3.7 gezeigt. Somit gilt
Pk,j (h) − δk,j h↓0 X
Pi,j (t + h) − Pi,j (t) X
=
Pi,k (t)
−→
Pi,k (t)qkj ,
h
h
k∈I
(3.4.11)
k∈I
denn wegen der Voraussetzung 3.4.8 gilt für endliches J ⊂ I mit j ∈ J und
P (h) − δ
X ε
k,j
k,j
− qk,j ≤ c = ε.
Pi,k (t)
h
c
P
k∈I\J
Pi,k (t) < ε/c:
(3.4.12)
k∈I\J
Nach Satz 3.4.1 wissen wir, dass Pij (·) stetig differenzierbar ist, also folgt die Behauptung.
Beispiel 3.4.5 (Poissonprozess). Sei Q die (konservative) Q-Matrix des Poissonprozesses aus
Beispiel 3.2.3. Bislang wissen wir noch nicht, ob die zum Poissonprozess gehörige Halbgruppe
wirklich standard ist, dennoch versuchen wir, die Rückwärts- und Vorwärtsgleichung zu Q zu
lösen. Die Rückwärtsgleichung lautet ausgeschrieben:
X
0
Pi,j
(t) =
qi,k Pk,j (t) = λPi+1,j (t) − λPi,j (t), t > 0, i, j ∈ N0 ,
(3.4.13)
k∈I
Pi,j (0) = δi,j ,
i, j ∈ N0 .
(3.4.14)
51
3.4. VORWÄRTS- UND RÜCKWÄRTSGLEICHUNGEN
Wir werden später sehen, dass dieses System eine eindeutige Lösung hat, aber man sieht bereits
jetzt, dass sich hier die Rückwärtsgleichung nicht besonders zur Berechnung von P (t) eignet,
denn zur Berechnung von P0,j (t) muss man bereits P1,j (t) kennen usw. Die Vorwärtsgleichung
lautet ausgeschrieben:
(
X
λPi,j−1 (t) − λPi,j (t), falls j ≥ 1,
0
(3.4.15)
Pi,j
(t) =
Pi,k (t)qk,j =
−λPi,0 (t),
falls j = 0,
k∈I
Pi,j (0) = δi,j ,
i, j ∈ N0 .
(3.4.16)
Hieraus kann man für festes i ∈ N0 das System rekursiv für j = 0, 1, 2, . . . lösen. Für j = 0
erhält man:
(
0,
falls i ≥ 1,
(3.4.17)
Pi,0 (t) =
−λt
e , falls i = 0.
Dies setzt man in die Gleichung für j = 1 ein. Mit dieser Methode zeigt man leicht, dass
(
0,
falls i > j,
Pi,j (t) =
(3.4.18)
(λt)j−i
−λt
e
(j−i)! , falls i ≤ j,
gilt. Die Anzahl der Sprünge des Poissonprozesses in einem Zeitintervall der Länge t ist also
Poisson-verteilt mit Parameter λt. Man kann nun explizit nachrechnen, dass diese (einzige)
Lösung der Vorwärtsgleichung wirklich eine markovsche Standardhalbgruppe ist. Dies wird sich
allerdings gleich als unnötig herausstellen (siehe Satz 3.4.8).
3
Beispiel 3.4.6 (Galton-Watson-Prozess). Wir benutzen die Rückwärtsgleichung, um die
erwartete Populationsgröße eines Galton-Watson-Prozesses zu berechnen, siehe
P Beispiel 3.2.5.
Wir setzen wiederum voraus, dass die erwartete Nachkommenschaft, m =
j∈N0 jpj , endlich
ist.
Zunächst sehen wir, dass für jedes i ∈ N0 gilt: Ei [X(t)] = iE1 [X(t)]. Dies ersieht man
aus der Konstruktion des Prozesses oder rechnet es mühsam mit Hilfe der Q-Matrix nach. Die
Rückwärtsgleichung ergibt daher
∞
∞
j=2
j=2
X
X
d
jpj = (m − 1)E1 [X(t)].
pj Ej [X(t)] = −E1 [X(t)] + E1 [X(t)]
E1 [X(t)] = −E1 [X(t)] +
dt
Wegen der Startbedingung E1 [X(0)] = 1 haben wir also E1 [X(t)] = e(m−1)t für jedes t ∈ [0, ∞).
Der Prozess konvergiert also im Mittel exponentiell gegen ∞, bleibt konstant oder konvergiert
exponentiell gegen Null, je nachdem ob m > 1, m = 1 oder m < 1. Man nennt den Prozess
superkritisch, falls m > 1 und subkritisch sonst.
3
Bislang wissen wir nicht, ob zu einer konservativen Q-Matrix immer eine Standardhalbgruppe gehört und unter welchen Umständen diese eindeutig ist. Die Existenz wird im folgenden Satz
sichergestellt. Dabei können wir die Konservativität von Q etwas abschwächen.
Definition 3.4.7. Q : I × I → R heißt schwach konservativ, wenn gelten:
(i) qij ≥ 0 für alle i, j ∈ I mit i 6= j,
(ii) qii > −∞ für alle i ∈ I,
52
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
(iii)
P
j∈I qij
≤ 0 für alle i ∈ I.
Wieder definieren wir qi := −qii für alle i ∈ I.
Unser Ziel besteht darin, zu einer gegebenen schwach konservativen Matrix Q eine Standardhalbgruppe (P (t))t≥0 zu finden, die die Vorwärts- und Rückwärtsgleichung löst, für die also
0
insbesondere (nach der Rückwärtsgleichung für t = 0) P (0) = Q ist, d.h. Q ist die Q-Matrix
von (P (t))t≥0 . Wir wissen dann insbesondere, dass, wenn Q schwach konservativ ist und die
Vorwärtsgleichung, bzw. die Rückwärtsgleichung, eine eindeutige Lösung hat, diese automatisch
eine Standardhalbgruppe sein muss (vgl. Bemerkung am Ende von Beispiel 3.4.5).
Satz 3.4.8. Sei Q eine schwach konservative Matrix. Dann existiert eine Standardhalbgruppe
(P (t))t≥0 , die die Vorwärtsgleichung und die Rückwärtsgleichung löst und für die gilt
P ij (t) ≤ Zij (t),
t ≥ 0, i, j ∈ I,
(3.4.19)
für jede Standardhalbgruppe (Z(t)) t≥0 mit Q-Matrix Q. Diese Standardhalbgruppe (P (t)) t≥0 heißt
Minimallösung.
Beweisskizze. Wir zeigen nur die Konstruktion der Standardhalbgruppe (P (t)) t≥0 (die uns
beim Beweis von Satz 3.5.4 nützlich sein wird), ohne aber zu beweisen, dass sie wirklich die
geforderten Eigenschaften hat. Für den vollständigen Beweis siehe [Ch67, S. 251 ff].
Definiere für i, j ∈ I, t ≥ 0
0
Pi,j
(t) := δi,j e−qi t
(3.4.20)
X Z
(3.4.21)
und für n ∈ N0 induktiv
n+1
Pi,j
(t)
:=
t
k∈I\{j} 0
n
Pi,k
(s)qk,j e−qj (t−s) ds.
n (·) stetig differenzierbar ist und
Induktiv zeigt man, dass Pi,j
N
Hi,j
(t) :=
N
X
n
Pi,j
(t) ≤ 1
(3.4.22)
n=0
ist. Schließlich definiert man für t ≥ 0
N
P i,j (t) := lim Hi,j
(t)
N ↑∞
(3.4.23)
(der Grenzwert existiert und ist ≤ 1). Es bleibt zu zeigen, dass (P (t)) t≥0 standard ist und
die Vorwärtsgleichung und die Rückwärtsgleichung löst, sowie die Minimalitätseigenschaft. Der
Beweis der Gültigkeit der Vorwärtsgleichung ist mit der obigen Rekursion relativ leicht, für den
n auch der
Nachweis der Rückwärtsgleichung zeigt man zunächst, dass die oben definierten Pi,j
Rekursion
X Z t
n+1
n
Pi,j (t) =
e−qi (t−s) qi,k Pk,j
(s) ds
(3.4.24)
k∈I\{i} 0
n (t) ist die Wahrgenügen. Die letzte Gleichung läßt sich anschaulich wie folgt interpretieren: P i,j
scheinlichkeit, bei Start in i mit genau n Sprüngen zur Zeit t in j zu landen. P i,j (t) ist dann die
Wahrscheinlichkeit, bei Start in i mit endlich vielen Sprüngen zur Zeit t in j zu landen.
53
3.4. VORWÄRTS- UND RÜCKWÄRTSGLEICHUNGEN
Bemerkung 3.4.9 (Interpretation der Minimall ösung). Die Minimallösung (P (t))t≥0 ist
die Halbgruppe derjenigen MKSZ X zu Q, die nach der ersten Explosion – d. h. dem ersten
Zeitpunkt zu dem X entweder in den Zustand ∂ springt, oder dem Infimum der Zeitpunkte, an
e zu einer
denen X unendlich viele Zustände besucht hat – für immer in ∂ bleibt. Jede MKSZ X
anderen Standardlösung Z verhält sich bis zur Explosion genauso wie X, springt dann aber von
3
∂ aus auf irgendeine Weise zurück nach I, weswegen P i,j (t) ≤ Zi,j (t) gilt.
Korollar 3.4.10. Sei Q schwach konservativ. Wenn die Minimallösung (P (t))t≥0 markovsch
ist, dann ist sie die einzige Standardhalbgruppe mit Q-Matrix Q.
Beweis. Sei (Z(t))t≥0 auch eine Standardhalbgruppe zu Q, dann folgt aus Satz 3.4.8, dass
Zi,j (t) ≥ P i,j (t) für alle i, j ∈ I und t ≥ 0, also
1≥
X
Zi,j (t) ≥
j∈I
X
P i,j (t) = 1,
i ∈ I, t ≥ 0,
(3.4.25)
j∈I
also folgt Zi,j (t) = P i,j (t) für alle i, j ∈ I und t ≥ 0.
Proposition 3.4.11. Sei Q konservativ und c = sup i∈I qi < ∞. Dann ist die Minimallösung
(P (t))t≥0 markovsch.
d P
Beweis. Unser Ziel besteht darin, zu zeigen, dass dt
j∈I P i,j (t) = 0 für alle t ≥ 0 gilt, woraus
P
wegen j∈I P i,j (0) = 1 folgt, dass (P (t))t≥0 markovsch ist.
Sei J ⊂ I endlich. Da (P (t))t≥0 die Vorwärtsgleichung erfüllt, gilt
X 0
X
X X
d X
P i,j (t) =
P i,j (t) =
P i,k (t)qk,j −
P i,j (t)qj .
dt
j∈J
j∈J
(3.4.26)
j∈J
j∈J k∈I\{j}
P
P
P
0
Nun ist
j∈J
k∈I\{j} P i,k (·)qk,j stetig, denn |J| < ∞, und
k∈I\{j} P i,k (t)qk,j = P i,j (t) +
P i,j (t)qj ist stetig in t nach Satz 3.4.1.
Weiter konvergiert mit J ↑ I
X X
P i,k (·)qk,j
monoton
−→
X X
P i,k (·)qk,j =
j∈I k∈I\{j}
j∈J k∈I\{j}
da Q konservativ ist, und
X
P i,j (t)qj
monoton
−→
P
j∈I
P i,k (·)qk ,
X
P i,j (t)qj .
(3.4.28)
P i,j (t)qj stetig ist:
X
X
h↓0
P i,j (t + h) − P i,j (t) −→
P i,j (t + h) − P i,j (t) qj ≤ c
0
j∈I
(3.4.27)
k∈I
j∈I
j∈J
Wir zeigen, dass t 7→
X
(3.4.29)
j∈I
gleichmäßig für alle t ∈ [0, ∞) nach Lemma 3.3.6. Der Satz von Dini besagt, dass, wenn eine
Folge stetiger Funktionen auf einem kompakten Intervall monoton gegen eine stetige Funktion
54
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
punktweise konvergiert, die Konvergenz sogar gleichmäßig ist. Somit konvergiert die rechte Seite
von (3.4.26) gleichmäßig auf kompakten Intervallen gegen
X
X
P i,k (t)qk −
P i,j (t)qj = 0.
(3.4.30)
j∈I
k∈I
Da jede Folge stetig differenzierbarer Funktionen f n : [0, t0 ] → R mit fn (0) → a ∈ R, deren
Ableitungen gleichmäßig konvergieren, gleichmäßig auf [0, t0 ] gegen eine stetig differenzierbare
Funktion f konvergiert, deren Ableitung gleich dem Grenzwert der Ableitungen der f n ist, folgt
d X
P i,j (t) = 0.
dt
(3.4.31)
j∈I
Bemerkung 3.4.12. Aus den bisherigen Resultaten folgt: Ist Q schwach konservativ,
und hat
P
die Vorwärtsgleichung eine eindeutige Lösung (P (t))t≥0 und erfüllt diese j∈I Pij (t) = 1 für
alle i ∈ I, dann ist (P (t))t≥0 standard und die einzige Standardhalbgruppe mit Q-Matrix Q. 3
3.5
Langzeitverhalten und invariante Maße
Wir studieren nun die Existenz von Grenzwerten von P ij (t) für t → ∞. Interessanterweise ist
dies weniger kompliziert als im zeitlich diskreten Fall, da das Problem der Periodizität bei MKSZ
nicht auftaucht.
Satz 3.5.1. Sei (P (t))t≥0 standard. Dann existiert für alle i, j ∈ I
πij := lim Pij (t),
t→∞
und es gilt
X
πij ≤ 1.
(3.5.1)
(3.5.2)
j∈I
Beweis. Wegen Bemerkung 3.3.3 können wir annehmen, dass (P (t))t≥0 standard und markovsch
ist. Für j ∈ I existiert daher ein h0 > 0, so dass Pj,j (h) > 0 für alle 0 ≤ h ≤ h0 . Mit der
Chapman-Kolmogorov-Gleichung folgt somit für t > 0, indem man t = nh mit n ∈ N und
h ≤ h0 setzt:
Pj,j (t) ≥ (Pj,j (h))n > 0.
(3.5.3)
Für beliebiges h > 0 betrachte nun die MKDZ (X(nh)) n∈N0 mit Übergangsmatrix P (h). Diese
ist wegen Pj,j (h) > 0 für alle j ∈ I aperiodisch, also existiert nach Satz 2.6.1 der Grenzwert
πi,j (h) := lim Pi,j (nh).
n→∞
(3.5.4)
Sei ε > 0 vorgegeben und i, j ∈ I. Da Pi,j (·) nach Lemma 3.3.6 gleichmäßig stetig ist,
existiert ein h, so dass |Pi,j (t + s) − Pi,j (t)| < ε/4 für alle t ≥ 0 und alle s ≤ h. Wähle nun
n0 = n0 (h), so dass
ε
|Pi,j (nh) − πi,j (h)| < ,
n ≥ n0 .
(3.5.5)
4
55
3.5. LANGZEITVERHALTEN UND INVARIANTE MASSE
Dann gilt für t, t0 ≥ n0 h mit kh ≤ t ≤ (k + 1)h und mh ≤ t0 ≤ (m + 1)h
|Pi,j (t) − Pi,j (t0 )| ≤ |Pi,j (t) − Pi,j (kh)| + |Pi,j (kh) − πi,j (h)|
+ |πi,j (h) − Pi,j (mh)| + |Pi,j (mh) − Pi,j (t0 )| < 4
ε
= ε.
4
(3.5.6)
Also existiert limt→∞ Pi,j (t), und es ist πi,j := limt→∞ Pi,j (t) = limt→∞ Pi,j (nh) = πi,j (h).
Insbesondere hängt πi,j (h) gar nicht von h ab.
Sei nun J ⊂ I endlich. Dann gilt
X
X
X
πi,j =
lim Pi,j (t) = lim
Pi,j (t) ≤ 1,
j∈J
also folgt
P
j∈I
j∈J
t→∞
t→∞
(3.5.7)
j∈J
πi,j ≤ 1.
Wie im diskreten Fall wollen wir die Beziehung zwischen den Grenzwerten π i,j und invarianten Maßen näher studieren.
Definition 3.5.2 (Invariantes Maß). Sei (P (t)) t≥0 submarkovsch und X eine zugehörige
MKSZ. Eine Abbildung π : I → [0, ∞] heißt ein invariantes
Maß für (P (t))t>0 (oder für X),
P
wenn πP (t) = π für jedes t ≥ 0 gilt. Gilt zusätzlich
i∈I πi = 1, dann heißt π invariantes
Wahrscheinlichkeitsmaß oder invariante Verteilung von (P (t)) t>0 .
Proposition 3.5.3. Sei (P (t))t≥0 standard und πi,j wie in Satz 3.5.1 definiert. Dann ist (π i,j )j∈I
für jedes i ∈ I ein invariantes Maß.
Beweis. Wir setzen wie in Bemerkung 3.3.3 (P (t)) t≥0 zu einer Markovhalbgruppe auf I ∪ {∂}
fort. Dann gilt für s, t ≥ 0 und k ∈ I ∪ {∂}
X
Pi,j (s)Pj,k (t) = Pi,k (t + s).
(3.5.8)
j∈I∪{∂}
Läßt man s → ∞ gehen, so folgt mit der üblichen Abschneidetechnik (d. h. nach Betrachtung
zunächst endlicher Summationsbereiche)
X
πi,j Pj,k (t) ≤ πi,k .
(3.5.9)
j∈I∪{∂}
P
P
Summiert man über alle k ∈ I ∪{∂}, so folgt j∈I∪{∂} πi,j ≤ k∈I∪{∂} πi,k , also – da die Summe
endlich ist – die Gleichheit in (3.5.9) für alle k ∈ I ∪ {∂}. Für k ∈ I ist P∂k (t) = 0 für alle t ≥ 0,
also ist (πi,j )j∈I ein invariantes Maß.
Satz 3.5.4. Sei Q konservativ und die Minimallösung (P (t))t≥0 markovsch. Dann ist π : I → R
ein invariantes Wahrscheinlichkeitsmaß von (P (t)) t≥0 genau dann, wenn es erfüllt:
X
(i) πQ = 0,
(ii) πi ≥ 0, i ∈ I,
(iii)
πi = 1.
(3.5.10)
i∈I
Beweis. (nach [Mi63]):
56
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
1. Schritt: Sei π ein invariantes Wahrscheinlichkeitsmaß, dann gilt
X
πj (1 − Pj,j (t)) =
πi Pi,j (t).
(3.5.11)
Dividiert man beidseitig durch t > 0 und läßt t ↓ 0 gehen, so folgt
X
∞ > π j qj ≥
πi qi,j ≥ 0
(3.5.12)
i∈I\{j}
i∈I\{j}
(um das mittlere “≥” zu erhalten, summiere man zunächst über endliche Mengen).
Sei J ⊂ I endlich. Dann folgt mit der Vorwärtsgleichung (die ja von der Minimallösung
erfüllt wird)
X
X
X d
X
d X
πi Pi,j (t) +
πi
πi Pi,j (t) =
πi Pi,j (t) = −qj
Pi,k (t)qk,j .
(3.5.13)
dt
dt
i∈J
i∈J
i∈J
i∈J
k∈I\{j}
Wie im Beweis von Satz 3.4.11 folgt die Stetigkeit der letzten Summe. Die beiden
PTerme auf der
rechten Seite von (3.5.13) konvergieren mit J ↑ I jeweils monoton gegen −q j i∈I πi Pi,j (t) =
−qj πj bzw.
X
X
X
X
X
Pi,k (t)qk,j =
qk,j
πi Pi,k (t) =
qk,j πk ,
πi
i∈I
k∈I\{j}
i∈I
k∈I\{j}
k∈I\{j}
da π invariant ist.
Der Grenzwert ist jeweils konstant und endlich nach (3.5.12), insbesondere also stetig. Wie
im Beweis von Satz 3.4.11 folgt mit dem Satz von Dini und dem Satz über die Vertauschbarkeit
von Grenzwert und Ableitung
X
X
d X
d
πi Pi,j (t) = −qj πj +
qk,j πk =
πk qk,j .
(3.5.14)
0 = πj =
dt
dt
i∈I
k∈I\{j}
k∈I
Also gilt (i). Die Aussagen (ii) und (iii) sind ohnehin klar.
n (t) und H N (t) für n, N ∈ N , und i, j ∈ I und
2. Schritt: π erfülle (i), (ii) und (iii). Definiere P i,j
0
i,j
t ≥ 0 wie im Beweis von Satz 3.4.8. Wir zeigen per Induktion nach N ∈ N 0 , dass gilt:
X
N
πi Hi,j
(t) ≤ πj
für alle j ∈ I, t ≥ 0.
(3.5.15)
i∈I
Für N = 0 gilt
X
0
πi Hi,j
(t) =
i∈I
X
πi δi,j e−qj t = πj e−qj t ≤ πj .
(3.5.16)
i∈I
Gelte also (3.5.15) für ein N ∈ N0 . Dann folgt
X
X Z tX
N +1
−qj t
N
πi Hi,j (t) = πj e
+
πi Hi,k
(s)qk,j e−qj (t−s) ds
k∈I\{j} 0 i∈I
i∈I
≤ πj e
−qj t
+
X Z
t
πk qk,j e−qj (t−s) ds
k∈I\{j} 0
= πj e−qj t + πj qj
Z
0
t
e−qj (t−s) ds = πj ,
(3.5.17)
57
3.5. LANGZEITVERHALTEN UND INVARIANTE MASSE
wobei in “≤” die Induktionsvoraussetzung einging und beim vorletzten Gleichheitszeichen die
Eigenschaft (i).
N (t), folgt aus (3.5.15)
Da Pi,j (t) = P i,j (t) = limN ↑∞ Hi,j
X
πi Pi,j (t) ≤ πj
für alle j ∈ I, t ≥ 0.
(3.5.18)
i∈I
Summiert man über alle j ∈ I, so sieht man, dass in (3.5.18) in Wirklichkeit Gleichheit gilt,
d. h. π ist ein invariantes Wahrscheinlichkeitsmaß.
Bemerkung 3.5.5. Satz 3.5.4 zeigt, dass man unter den angegebenen Voraussetzungen alle
invarianten Wahrscheinlichkeitsmaße durch Lösen von πQ = 0 mit den Nebenbedingungen (ii)
und (iii) in (3.5.10) erhält. Dies ist für die Berechnung von π sehr bedeutsam, da die Matrizen
P (t) für t ≥ 0 im Gegensatz zu Q meist nicht explizit gegeben sind. Man beachte aber die
Voraussetzungen von Satz 3.5.4. Miller gibt in [Mi63] ein Beispiel, bei dem für ein konservatives
Q (i) - (iii) eine eindeutige Lösung hat, ohne dass π ein invariantes Wahrscheinlichkeitsmaß ist.
Die Minimallösung ist in seinem Beispiel nicht markovsch.
3
Definition 3.5.6 (Irreduzibilität). Eine Standardhalbgruppe (P (t)) t≥0 mit schwach konservativer Q-Matrix Q (oder Q selbst) heißt irreduzibel,
Qn−1 wenn für alle i, j ∈ I mit i 6= j ein n ∈ N0
und i = i0 , i1 , . . . , in = j aus I existieren mit m=0
qim ,im+1 > 0.
Korollar 3.5.7. Sei Q konservativ und irreduzibel und die Minimallösung markovsch. Wenn
(3.5.10) in Satz 3.5.4 eine Lösung π hat, dann ist diese eindeutig, und es gilt lim t→∞ Pij (t) = πj
für alle i, j ∈ I.
Beweis. Nach Satz 3.5.4 ist die Lösung π invariant unter (P (t))t≥0 , also ist π auch ein invariantes
Wahrscheinlichkeitsmaß der MKDZ (X(n)) n∈N0 mit Übergangsmatrix P (1). Diese MKDZ ist
irreduzibel: Im Beweis von Satz 3.5.1 sahen wir, dass P i,i (t) > 0 für alle t ≥ 0. Für i 6= j
seien i0 , . . . , in wie bei der Definition 3.5.6 gegeben. Es genügt zu zeigen, dass i
i1 für die
0 (t) = q
MKDZ (X(n))n∈N0 gilt, wobei wir an Definition 2.3.1 erinnern. Wegen P i,i
i,i
1 t + o(t)
1
und qi,i1 > 0 existiert ein h0 > 0, so dass Pi,i1 (t) > 0 für alle t ∈ (0, h0 ] gilt. Weiter gilt für
t > h0 , dass Pi,i1 (t) ≥ Pi,i (t − h0 )Pi,i1 (h0 ) > 0, womit insbesondere die Irreduzibilität von P (1)
gezeigt ist. Wegen Pi,i (1) > 0 ist die Aperiodizität klar. Also folgt nach Satz 2.6.1 für j ∈ I,
dass πj = limn→∞ Pi,j (n), und wegen Satz 3.5.1 gilt sogar π j = limt→∞ Pi,j (t). Dies zeigt auch
die Eindeutigkeit der Lösung π von (i) - (iii) in Satz 3.5.4.
Korollar 3.5.8. Sei Q konservativ und die Minimallösung markovsch. Wenn (3.5.10) keine
Lösung hat, dann folgt
lim Pij (t) = 0
für alle i, j ∈ I.
(3.5.19)
t→∞
Beweis. Nach Satz 3.5.1 existiert π i,k = limt→∞ Pi,k (t) und es gilt
es existieren i, j ∈ I mit lim t→∞ Pi,j (t) = πi,j > 0, dann definiere
π i,k := P
πi,k
.
r∈I πi,r
P
k∈I
πi,k ≤ 1. Angenommen,
(3.5.20)
58
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Nach Satz 3.5.3 ist (π i,k )k∈I ein invariantes Wahrscheinlichkeitsmaß und erfüllt (3.5.10) im
Widerspruch zur Voraussetzung. Also gilt π i,j = 0 für alle i, j ∈ I.
Beispiel 3.5.9 (Geburts- und Todesprozesse). Für Geburts- und Todesprozesse (siehe
Beispiel 3.2.1) lassen sich die invarianten Wahrscheinlichkeitsverteilungen, wenn sie existieren,
explizit berechnen. Wir nehmen an, dass die Geburts- und Sterberaten alle strikt positiv sind.
Definiert man b0 = 1 und
λ0 . . . λj−1
bj =
,
j ∈ N,
(3.5.21)
µ1 . . . µ j
so kann man zeigen, dass genau im Fall
i
∞ X
1 X bj = ∞
λi bi
(3.5.22)
j=0
i=0
der Prozess nicht explodiert (d. h. die Minimallösung markovsch ist). Wir setzen dies im Folgenden voraus. Solche expliziten notwendige und hinreichende Nichtexplosionskriterien sind übrigens für allgemeine MKSZ nicht bekannt.
Der Geburts- und Todesprozess ist wegen der Voraussetzung der Positivität der λi und µi
offenbar irreduzibel. Anstatt das Gleichungssystem in Satz 3.5.4 direkt zu lösen, führt auch die
folgende Überlegung zu einer Lösung:
Wenn ein invariantes Wahrscheinlichkeitsmass π existiert, dann muss (da der Prozess im
Gleichgewicht ist), für jedes i ∈ N0 genausoviel “Masse” pro Zeit von i nach i + 1 fließen wie
umgekehrt, d. h. es muss gelten:
πi λi = πi+1 µi+1
für alle i ∈ N0 .
(3.5.23)
Man zeigt leicht, dass (3.5.23) äquivalent zu (i) in Satz 3.5.4 ist. Die Aussage in (3.5.23) erhält
man, indem man die ersten i + 1 Gleichungen von πQ = 0 addiert. Aus (3.5.23) folgt f ür k ∈ N
λk−1
λk−2 λk−1
= πk−2
= · · · = π 0 bk .
(3.5.24)
µk
µk−1 µk
P
P∞
P∞
Wenn ∞
k=0 πk = 1 ist, so muss 1 = π0
k=0 bk gelten. Wäre
P∞ k=0 bk = ∞, so müßte π0 = 0
sein und nach (3.5.24) πk = 0 für alle k ∈ N gelten, was k=0 πk = 1 widerspricht.
P
P∞Ist also
∞
k=0 bk = ∞, dann existiert kein invariantes Wahrscheinlichkeitsmaß. Ist dagegen
k=0 bk <
∞, so definiert
1
bj ,
j ∈ N0 ,
(3.5.25)
πj = P∞
k=0 bk
P
eine Lösung von (3.5.23) und damit ein invariantes Wahrscheinlichkeitsmaß. Also ist ∞
k=0 bk <
∞ eine notwendige und hinreichende Bedingung für die Existenz eines invarianten Wahrscheinlichkeitsmaßes eines irreduziblen Geburts- und Todesprozesses. Aus Korollar 3.5.7 folgt dann
sogar πj = limt→∞ Pij (t) für alle i, j ∈ N0 .
3
πk = πk−1
Beispiel 3.5.10 (M/M/c-Warteschlange). Wir betrachten die M/M/c-Warteschlange aus
Beispiel 3.2.2. Wie wir dort gesehen haben, ist die Anzahl der Kunden insbesondere ein Geburtsund Todesprozess, also können wir Beispiel 3.5.9 anwenden. Mit den dort definierten b j gilt:
∞
X
j=0
∞
c−1
X
X
λj
λj
+
.
bj =
j!µj
c!cj−c µj
j=0
j=c
(3.5.26)
59
3.5. LANGZEITVERHALTEN UND INVARIANTE MASSE
Die erste Summe ist immer endlich, die zweite ist endlich genau dann, wenn λ < cµ ist. Also
existiert eine invariante Verteilung genau dann, wenn die Verkehrsdichte ρ = λ/(cµ) kleiner als
Eins ist. In diesem Fall haben wir
∞
X
j=0
woraus sich πj = bj
P∞
k=0 bk
−1
c−1
X
λj
cc ρc
+
,
bj =
j!µj
c!(1 − ρ)
(3.5.27)
j=0
explizit berechnen lässt:
πj = π 0
λ j
µ
×
(
1
j! ,
1
,
c!cj−c
falls j ≤ c,
falls j ≥ c.
(3.5.28)
Im Spezialfall c = 1 erhält man πj = (1 − ρ)ρj für alle j ∈ N0 , also eine geometrische Verteilung.
3
Beispiel 3.5.11 (Warteschlangennetze). In den letzten 20 Jahren sind Warteschlangennetze vor allem mit Anwendung auf Rechnersysteme, aber auch auf Produktionsabläufe untersucht
worden. Man modelliert solche Netze dadurch, dass man jeden der Bediener als Eckpunkt eines
endlichen Graphen auffasst. Man verbindet i mit j durch einen gerichteten Pfeil und beschriftet
ihn mit πi,j , wenn πi,j > 0 die Wahrscheinlichkeit ist, dass ein Kunde, nachdem er bei i bedient
wurde, sich bei j anstellt. Zusätzlich kann man eine Ecke des Graphen einführen, die die “Außenwelt” darstellt. Ein Kunde, der das ganze System verläßt, geht also in jene Ecke. Außerdem
legt man fest, mit welcher Verteilung Kunden von außen in den einzelnen Ecken eintreffen, und
beschriftet die Ecken mit der zugehörigen Bedienungszeitverteilung. Nimmt man an, dass alle Bedienungszeiten, Sprünge und Zwischenankunftszeiten unabhängig sind, und legt man eine
geeignete Startbedingung fest, so ist damit die Dynamik des Prozesses festgelegt. Interessant
sind die gemeinsame Verteilung der Warteschlangenlängen in allen Ecken (außer der “Außenwelt”), insbesondere für divergierende Zeit, aber auch die Verweildauerverteilung eines Kunden
im System. Wenn alle Bedienungs- und Zwischenankunftsverteilungen endliche Mischungen von
Ek -Verteilungen sind, so kann man mit der in Beispiel 3.2.7 vorgestellten Methode den Vektor
der Zahl der Kunden in jeder Ecke zu einer MKSZ “aufblähen”. Dies wird auch häufig gemacht,
um damit invariante Wahrscheinlichkeitsmaße (numerisch) für obigen Vektor zu berechnen.
Ein Spezialfall, für den die Grenzverteilungen eine besonders einfache Gestalt haben, sind
Jackson-Netzwerke (vgl. [HS82, S. 456 ff]). Wir machen die folgenden Annahmen:
1. Es gibt N ∈ N Knoten - durchnumeriert von 1 bis N .
2. Im Knoten i befinden sich ci Bediener. Die Bedienungszeiten seien Exp(µ i )-verteilt.
3. Kunden, die von außen (und nicht von einem anderen Knoten) bei Knoten i eintreffen,
haben unabhängige Exp(λi )-verteilte Zwischenankunftszeiten.
4. Gegeben ist eine substochastische N × N -Matrix P = (p i,j )i,j=1,...,N , wobei pi,j die Wahrscheinlichkeit sei, dass ein Kunde nach der Bedienung
P im Knoten i sich (sofort!) am Knoten
j anstellt. Dann interpretieren wir p i,0 := 1 − N
j=1 pi,j als die Wahrscheinlichkeit, dass
der Kunde nach Bedienung am Knoten i das System verläßt.
5. Es gelte überall FIFO (“first in first out”).
60
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
Notwendig und hinreichend für die Existenz einer Gleichgewichtsverteilung ist offenbar, dass
alle N Knoten so schnell arbeiten, dass langfristig genausoviel herein- wie herausfließt. Wir leiten
zunächst heuristisch eine Verkehrsgleichung her, die wir dann mathematisch exakt analysieren,
womit wir im folgenden Satz ein notwendiges und hinreichendes Kriterium für die Existenz einer
invarianten Verteilung sowie eine Formel dafür erhalten.
Wenn αi ≥ 0 die Rate ist, mit der Kunden im stationären Zustand den Knoten i verlassen,
dann gilt anschaulich:
N
X
αj pj,i ,
i = 1, . . . , N,
(3.5.29)
αi = λ i +
j=1
denn was abfließt (αi ) muss auch reinfließen (rechte Seite). Wir nehmen nun zusätzlich an, dass
gilt
n→∞
P n −→ 0
komponentenweise,
(3.5.30)
was besagt, dass Kunden von jedem Knoten aus irgendwann das System verlassen – sicher keine
allzu starke und eine leicht überprüfbare Voraussetzung an P .
Lemma 3.5.12. Unter obigen Annahmen hat (3.5.29) genau eine Lösung α, und zwar
αT = λT (I − P )−1 = λT
∞
X
P k.
(3.5.31)
k=0
Beweis. (3.5.29) kann man in der Form α T = λT + αT P , also αT (I − P ) = λT schreiben. Nun
gilt
I − P n = (I − P )(I + P + P 2 + · · · + P n−1 ).
(3.5.32)
Wegen unserer Voraussetzung (3.5.30) ist I − P n für hinreichend große n invertierbar und daher
det(I − P n ) 6= 0. Also ist nach (3.5.32) auch det(I − P ) 6= 0, d. h., I − P ist invertierbar, woraus
das erste Gleichheitszeichen der Behauptung
folgt. Weiter folgt aus (3.5.32) nach Grenz übergang
P∞
−1
k
n → ∞ die Gleichung (I − P ) = k=0 P .
Wir machen nun noch die weitere Annahme
αi =
N
X
j=1
λj
∞
X
Pk
k=0
ji
>0
für alle i,
(3.5.33)
was zum Beispiel aus der stärkeren Forderung λj > 0 für alle j folgt. Nun wählen wir – naheliegenderweise – als Zustandsraum des Netzwerks I = N N
0 , wobei X(t) = (n1 , . . . , nN ) bedeuten
soll, dass sich zur Zeit t genau ni ∈ N0 Kunden am Knoten i befinden für alle i = 1, . . . , N .
Offenbar ist (X(t))t≥0 eine MKSZ, deren Q-Matrix wir im Beweis des folgenden Satzes explizit
angeben werden.
Satz 3.5.13 (Jackson). Unter den obigen Annahmen hat die MKSZ (X(t)) t≥0 genau dann ein
invariantes Wahrscheinlichkeitsmaß π, wenn für alle i = 1, . . . , N gilt: αi < ci µi .
In diesem Fall ist π eindeutig, und es gilt
πn1 ,...,nN = Ψ1 (n1 ) · · · · · ΨN (nN ),
(3.5.34)
61
3.5. LANGZEITVERHALTEN UND INVARIANTE MASSE
wobei Ψi (·) das invariante Wahrscheinlichkeitsmaß einer M/M/c i -Schlange mit Ankunftsrate αi
und Bedienungsrate µi ist, also

α n  1 ,
falls n ≤ ci ,
n!
i
Ψi (n) = Ψi (0)
× 1 1
(3.5.35)
 ci ! n−ci , falls n ≥ ci .
λi
ci
Bemerkung 3.5.14. Man beachte, dass trotz der Abhängigkeiten, die zwischen den Knoten
bestehen, die Anzahl der Kunden an den einzelnen Knoten im stationären Zustand zu einem
festen Zeitpunkt unabhängige Zufallsgrößen sind.
3
Beweis von Satz 3.5.13. Offenbar hat die Q-Matrix folgende Gestalt (mit e i bezeichen wir
N
das Element aus NN
0 mit einer Eins an der i-ten Stelle und Nullen sonst). Für alle n ∈ E = N0
gilt
qn,n+ei = λi ,
qn,n−ei = (ni ∧ ci )µi pi0 ,
(3.5.36)
qn,n−ei +ej = (ni ∧ ci )µi pij ,
alle anderen qij mit i 6= j sind Null. Weiter ist Q irreduzibel.
Wir setzen nun voraus, dass αi < ci µi für alle i (den Beweis im umgekehrten Fall ersparen
wir uns). Definiere π durch (3.5.34). Nach Satz 3.5.4 ist zu zeigen, dass πQ = 0; die Eindeutigkeit
von π folgt dann aus Satz 3.5.7. Wir zeigen sogar, dass für jedes n = (n1 , . . . , nN ) gilt
N
X
πn+ej qn+ej ,n = πn
πn−ej qn−ej ,n = πn
j=1
N
X
qn,n+ej ,
(3.5.37)
qn,n−ej ,
(3.5.38)
qn,n−ei +ej ,
(3.5.39)
j=1
j=1
N
X
N
X
N
X
j=1
πn−ei +ej qn−ei +ej ,n = πn
N
X
i=1
i6=j
i=1
i6=j
woraus sofort πQ = 0 folgt.
Tatsächlich zeigen wir nur (3.5.37), da (3.5.38) und (3.5.39) analog bewiesen werden. Die
linke Seite von (3.5.37) ist
N Y
N
X
j=1
i=1
i6=j
=
Ψi (ni ) Ψj (nj + 1)((nj + 1) ∧ cj )µj pj0
N
Y
Ψi (ni )
j=1
i=1
=
N
Y
Ψi (ni )
=
i=1
N
X
Ψj (nj )
αj pj0 =
Ψi (ni )
N
X
j=1
N
Y
i=1
j=1
i=1
N
Y
N
X
Ψj (nj + 1)
λj ,
(nj + 1) ∧ cj µj pj0
Ψi (ni )
N
X
j=1
αj 1 −
N
X
k=1
pjk
(3.5.40)
62
KAPITEL 3. MARKOVKETTEN IN STETIGER ZEIT
was gleich der rechten Seite von (3.5.37) ist, wobei wir beim letzten Gleichheitszeichen die
Verkehrsgleichung (3.5.29) und beim vorletzten die explizite Formel für Ψj (nj + 1)/Ψj (nj ) benutzten.
3
Bibliographie
[Ba91] H. Bauer, Maß- und Integrationstheorie, 2. Auflage, Walter de Gruyter, Berlin–New
York, 1991.
[Ba02] H. Bauer, Wahrscheinlichkeitstheorie, 5. Auflage, Walter de Gruyter, Berlin–New York,
2002.
[Bi86] P. Billingsley, Probability and Measure, Wiley, New York 1986.
[Ch78] K. L. Chung, Elementare Wahrscheinlichkeitstheorie und stochastische Prozesse,
Springer, Berlin, 1978.
[Br68] L. Breiman, Probability, Addison-Wesley, Reading, 1968.
[Ch67] K. L. Chung, Markov Chains with Stationary Transition Probabilities, Springer, Berlin
1967.
[Co80] D.L. Cohn, Measure Theory, Birkhäuser, Basel 1980.
[Fe68] W. Feller, An Introduction to Probability Theory and its Applications, Vol. I, 3rd ed.,
Wiley, New York, 1968.
[Ge02] H.-O. Georgii, Stochastik. Einführung in die Wahrscheinlichkeitstheorie und Statistik,
Walter de Gruyter, 2002.
[GS75] I. I. Gikhman und A. V. Skorohod, The Theory of Stochastic Processes II, Springer,
Berlin, 1975.
[H02] O. Häggström, Finite Markov Chains and Algorithmic Applications, Cambridge University Press, 2002.
[HS82] D. Heyman und M. Sobel, Stochastic Models in Operations Research, Vol. I, McGraw
Hill, New York, 1982.
[KT75] S. Karlin und H. M. Taylor, A First Course in Stochastic Processes, Academic
Press, New York, 1975.
[KT81] S. Karlin und H. M. Taylor, A Second Course in Stochastic Processes, Academic
Press, New York, 1975.
[Kr02] U. Krengel, Einführung in die Wahrscheinlichkeitstheorie und Statistik, 6. Auflage,
Vieweg, 2002.
[Mi63] R. Miller, Stationary equations
Trans. Amer. Math. Soc. 109, 35-44, 1963.
in
continuous
time
[No97] J. Norris, Markov Chains, Cambridge University Press, 1997.
63
Markov
chains,
64
LITERATUR
[Pi90] B. Pittel, On a Daley-Kendall model of random rumours, Journal of Applied Probability
27, 1990.
[Sch98] K. Schürger, Wahrscheinlichkeitstheorie, Oldenbourg, München, 1998.
[Se81] E. Seneta, Non-Negative Matrices and Markov Chains, Springer, New York, 1981.
[Wi79] D. Williams, Diffusions, Markov Processes and Martingales, Wiley, 1979.
Gut lesbare Einführungen in die Theorie der Markovketten sind [Ch67], [Se81], [H02] und
[No97], wobei [Ch67] hauptsächlich die Theorie der stationären Markovketten in stetiger Zeit
sehr umfassend behandelt, [Se81] stochastische Matrizen hauptsächlich als Spezialfall nichtnegativer Matrizen auffasst und deren Frobenius-Eigenwerttheorie zum Hauptthema hat, und [H02]
und [No97] sich auf eine elementare Einführung von Markovketten in diskreter Zeit konzentrieren mit vielen Beispielen (insbesondere algorithmischen Anwendungen in [H02]), aber nicht ganz
so viel Material. Die Lehrbücher [Ch78], [Ge02] und [Kr02] sind hauptsächlich der Elementaren
Wahrscheinlichkeitstheorie gewidmet und dienen zum Nacharbeiten von wichtigen Beispielen
und Anwendungen der bekannten diskreten und absolutstetigen Verteilungen. Die Lehrb ücher
[Fe68], [Bi86], [Ba02], [Sch98] dienen dem Nachschlagen benötigter Hilfsmittel der Wahrscheinlichkeitstheorie, und [Co80] und [Ba91] informieren über die benötigte Maßtheorie.
Документ
Категория
Без категории
Просмотров
14
Размер файла
445 Кб
Теги
prozess, 001, pdf, 4297, stochastische
1/--страниц
Пожаловаться на содержимое документа