Stochastik für Ingenieure

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 X_n heißt Markov-Kette :⇔
- P(X_n+1 = x_n+1 | X_n = x_n, X_n-1 = x_n-1, ..., X₁ = x₁) = P(X_n+1 = x_n+1 | X_n = x_n)
homogene Markov-Kette (HMK)
- Übergangs-Wahrscheinlichkeit P(X_n+1 = x_n+1 | X_n = x_n) 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:

Übergangs-Graph:

graphische Darstellung einer homogenen Markov-Kette
- Werte von X_n (Zustände) als Knoten
- Übergänge zu anderen Zuständen als Pfeile mit Angabe von P_ij
Beispiel Roulette

Beispiel Autovermietung:

Wahrscheinlichkeit späterer Zustände:

Frage: Wie groß ist die Wahrscheinlichkeit P(X₅ = 50), beim Roulette-Beispiel nach 5 Schritten gewonnen zu haben?
allgemein gesucht
- P_ijⁿ = P(X_n+k = j | X_n = 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 P⁵ berechnen und ablesen
- P_2,5⁵ = 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
- P_i,jⁿ > 0 für ein n ≥ 0
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
- P_i,i+1 = p, P_i,i-1 = 1-p
- besonders interessant ist der symmetrische Fall p=1/2
zweidimensional
- Zustandraum ist ℤ², 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 ℤ³ 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(X_n+1 = i) = P(X_n = 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:

Markov-Ketten