Markov-Ketten
- Stochastischer Prozess:
- anschaulich: zeitabhängige
Zufallsgröße
- etwas genauer: Familie von Zufallsvariablen X(t), t
"Zeit"
- t ∈ ℝ+ stetiger
stochastischer Prozess
- t ∈ ℕ diskreter stochastischer
Prozess
- Wertebereich von X stetig (oft ℝ) oder diskret (oft
{1,2,...,n} oder ℕ)
- betrachten hier nur wertediskrete Prozesse, meistens
auch zeitdiskret
- Beispiele:
- Roulette-Spieler
- beginnt mit 20 €
- setzt beim Roulette immer 10 € auf Rot
- hört auf, wenn er kein Geld mehr hat oder 50
€
- X(i) = Besitz nach der i-ten Runde (diskret)
- Kreisprozess
- System befindet sich in einem von N
Zuständen
- In jedem Schritt wechselt es zum nächst
größeren, nach Schritt N zurück auf Zustand 1
(diskret)
- Börsennotierung einer Firma zur Zeit t (stetig
oder diskret)
- Länge der Warteschlange an einer Kasse (stetig)
- Markov-Prozess:
- anschaulich: nächster Wert ist nur abhängig
vom letzten, nicht von der ganzen Vergangenheit
- diskreter stochastischer Prozess Xn
heißt Markov-Kette :⇔
- P(Xn+1 = xn+1 | Xn
= xn, Xn-1 = xn-1, ..., X1
= x1) = P(Xn+1 = xn+1 | Xn
= xn)
- homogene Markov-Kette (HMK)
- Übergangs-Wahrscheinlichkeit P(Xn+1
= xn+1 | Xn = xn) hängt
nicht vom Zeitpunkt n ab
- stetiger stochastischer Prozess X(t)
heißt Markov-Prozess :⇔
- für t, s > 0, 0 ≤ u < s gilt
- P(X(t+s)=j | X(s) = i, X(u) = k) = P(X(t+s)=j |
X(s) = i)
- homogen :⇔ P(X(t+s)=j | X(s) = i)
hängt nicht von s ab
- Beispiele
- Roulette: homogene Markov-Kette
- Börsenkurs: vermutlich nicht Markov
- Warteschlange: hängt ab von der Art der
Ankunfts- und Abgangsprozesse
- Übergangs-Matrix P einer HMK:
- Definition
- Wahrscheinlichkeit = 1, irgendwohin zu kommen
- Zustandsvektor v ist Zeilenvektor (!) mit
- damit Zustandvektor u nach einem Schritt
- Übergangs-Graph:
- graphische Darstellung einer homogenen Markov-Kette
- Werte von Xn (Zustände) als
Knoten
- Übergänge zu anderen Zuständen als
Pfeile mit Angabe von Pij
- Beispiel Roulette
- Beispiel Autovermietung:
- Niederlassungen in HH, H, HB, OS
- Autos können an beliebigen Niederlassungen
zurückgegeben werden
- Statistik des Kundenverhaltens liefert
Übergangs-Matrix für Ort eines Autos
- Übergangs-Graph
- Wahrscheinlichkeit späterer Zustände:
- Frage: Wie groß ist die Wahrscheinlichkeit P(X5
= 50), beim Roulette-Beispiel nach 5 Schritten gewonnen zu haben?
- allgemein gesucht
- Pijn = P(Xn+k =
j | Xn = i) (n ≥ 0)
- Chapman–Kolmogorov-Gleichung
- Beweis
- geschrieben als Matrizen
- insbesondere
- im Beispiel
- Zustände (0,1,2,3,4,5) ≙ (0,10,20,30,40,50)
€
- mit Matlab leicht P5 berechnen und
ablesen
- P2,55 = 0.2014
- Eigenschaften von Zuständen:
- Zustand j heißt von i aus
erreichbar, wenn man mit Wahrscheinlichkeit > 0 in n
≥ 0 Schritten von i nach j kommt, also
- Zustände i, j heißen verbunden,
wenn i von j aus erreichbar ist und j von i aus
- Übergangs-Graph zerfällt in
Erreichbarkeitskomponenten
- Beispiel Roulette: {0}, {10, 20, 30, 40}, {50}
- HMK irreduzibel :⇔
es gibt nur eine Komponente
- Zustand i heißt rekurrent,
wenn mit Wahrscheinlichkeit = 1 nach Start bei i in endlich vielen
Schritten i wieder erreicht wird, sonst transient
- Satz
- Mit Wahrscheinlichkeit = 1 wird ein rekurrenter
Zustand unendlich oft angenommen, ein transienter nur endlich
oft.
- Satz
- Zwei verbundene Zustände sind entweder beide
transient oder beide rekurrent.
- Beispiel Zufallspfad:
- eindimensional
- Zustandsraum seien die ganzen Zahlen ℤ
- mit Wahrscheinlichkeit p wechselt man von Zustand
i in i+1, mit 1-p von i nach i-1, also
- Pi,i+1 = p, Pi,i-1 =
1-p
- besonders interessant ist der symmetrische Fall
p=1/2
- zweidimensional
- Zustandraum ist ℤ2, also ein
quadratisches Gitter
- Übergang von einem Punkt (i,j) zu einem der
vier Nachbarpunkte
- betrachten nur den symmetrischen Fall mit
Wahrscheinlichkeit 1/4 in jeder Richtung
- dreidimensional
- analog für ℤ3 mit
Wahrscheinlichkeit 1/6 zu jedem der sechs Nachbarpunkte
- Satz
- Beim unsymmetrischen 1d-Zufallspfad sind alle
Zustände transient, beim symmetrischen alle rekurrent.
- Beim symmetrischen 2d-Zufallspfad sind alle
Zustände rekurrent.
- Beim symmetrischen 3d-Zufallspfad sind alle
Zustände transient.
- Merkregel
- Ein betrunkener Mensch findet immer irgendwann
nach Hause, ein betrunkener Vogel nicht unbedingt!
- Gleichgewichtsverteilung (GGV):
- HMK ist im Gleichgewicht :⇔ P(Xn+1 =
i) = P(Xn = i) (für alle i)
- Beispiel Autovermietung
- Verteilung der Autos auf die Niederlassungen, so
dass sich diese im Mittel nicht ändert
- Gleichgewichtsverteilung π gegeben durch
- praktische Berechnung
- homogenes Gleichungssystem π (P - 1) = 0
lösen
- in der Regel ein Wert frei, auf 1 setzen
- anschließend Ergebnisvektor auf Gesamt-Wahrscheinlichkeit
1 normieren
- Matlab-Trick
- Löse (P' - 1) π' = 0
mit null(P' - eye(n))
- n = Zahl der Zustände
- GGV in den Beispielen:
- Autovermietung mit Matlab
- π = [0.3172, 0.3495, 0.2204, 0.1129]
- Roulette (mit Matlab oder leicht per Hand)
- π = [p, 0, 0, 0, 0, 1-p], p ∈ [0,1]
- Existenz einer GGV:
- Satz
- Sind alle Zustände transient, gibt es keine
GGV.
- Voraussetzung nur für unendliche
Zustandsräume erfüllbar
- Beispiel: unsysmmetrischer Zufallspfad
- Satz
- Irreduzible Markow-Ketten mit endlichem
Zustandsraum haben eine eindeutige GGV.
- Roulette-Beispiel nicht irreduzibel, hat zwei
unabhängige GGV.
- Schnittprinzip:
- Übergangs-Graph sei in zwei Teile K, L zerlegt
- Für GGV gilt: Übergangs-Wahrscheinlichkeit
von K nach L = Übergangs-Wahrscheinlichkeit von
L nach K
- speziell, wenn Zerlegung an einer (Doppel-)Kante
möglich
- Langzeitverhalten:
- Beispiel Autovermietung, Start mit Gleichverteilung
- wiederholte Anwendung von P liefert
- viele, aber nicht alle HMK konvergieren gegen die GGV
- Problem sind Schleifen wie im Kreisprozess-Beispiel
- hinreichend: irreduzibel und keine Schleifen
- Aufgaben: