Inhaltsverzeichnis Was ist ein stochastischer Prozess? Inhalt 1. Wahrscheinlichkeitstheorie (Crashkurs) 1.1. Zufallsvariablen 1.2. Verteilungsfunktion 1.3. Stetige Verteilungsfunktionen 1.4. Diskrete Verteilungsfunktionen 1.5. Erwartungswerte 1.6. Unabhängigkeit 1.7. Bedingte Wahrscheinlichkeit und bedingte Erwartung 1.8. Bedingungsformeln 1.9. Die Faltung 1.10. Das Gesetz der großen Zahlen 1.11. Der Zentrale Grenzwertsatz 2. Irrfahrten 2.1. Die symmetrische einfache Irrfahrt 2.2. Verteilung der symmetrischen einfachen Irrfahrt 2.3. Austrittszeiten aus einem Streifen 1 / 185 3. Markov-Ketten 3.1. Motivation: Irrfahrt mit Leitplanken 3.2. Markov-Ketten 3.3. Übergangswahrscheinlichkeiten 3.4. Klassifikation von Zuständen: Erreichbarkeit 3.5. Klassifikation von Zuständen: Periodizität 3.6. Klassifikation von Zuständen: Rekurrenz 3.7. Stationäre Verteilung und Grenzverhalten 3.8. Mittelwerte im Gleichgewichtszustand 3.9. Rückkehrzeiten 4. Poisson-Prozesse 4.1. Erdbeben und Zählprozesse 4.2. Definition: Poisson-Prozess 4.3. Gedächtnislosigkeit der exponentiellen Verteilung 4.4. Verteilung der Pausenzeiten 4.5. Pausenzeiten und Ereigniszeitpunkte 4.6. Normalapproximation 4.7. Exkurs: Ordnungsstatistik der Gleichverteilung 4.8. Ereigniszeitpunkte bei fester Ereigniszahl 2 / 185 4.9. Vorwärts- und Rückwärtsrekurrenzzeit 4.10. Zusammenführung von Poisson-Prozessen 4.11. Ausdünnung von Poisson-Prozessen 4.12. Inhomogene Poisson-Prozesse 4.13. Zusammengesetzte Poisson-Prozesse, Waldsche Gleichung 5. Brownsche Bewegung 5.1. Noch einmal Irrfahrten 5.2. Eigenschaften der Brownschen Bewegung 5.3. Treffzeit, einseitig 5.4. Maximumprozess 5.5. Treffzeit, beidseitig 5.6. Verhalten der Pfade für wachsendes t 5.7. Weitere Konstruktionen 5.8. Die Brownsche Brücke 6. Die geometrische Brownsche Bewegung 6.1. Definition 6.2. Eigenschaften 6.3. Optionspreise 3 / 185 Was ist ein stochastischer Prozess? Stochastische Prozesse beschreiben die zufällige Entwicklung einer zahlenmäßigen Größe in der Zeit. Diskreter Zeitverlauf: Xn bezeichnet eine zufällige Größe zu den Zeitpunkten n = 1, 2, 3, . . .. Kontinuierlicher Zeitverlauf: X (t) bezeichnet eine zufällige Größe zu Zeitpunkten t ∈ [0, ∞), 4 / 185 Beispiele für Anwendungen stochastischer Prozesse: I Ergebnisse beim Münzwurf, Würfelspiel, I Produktionszahlen, I Arbeitslosenquote, I Nachfrage, I Kapital einer Versicherung, I Länge von Warteschlangen, I Lebensdauer von Produkten, I Aktienkurse. Wir halten uns nicht mit der Frage auf, worauf das stochastische Wesen des Prozesses („die Zufälligkeit”) zurückzuführen ist, sondern betrachten Zufall als das Nicht-Vorhandensein von Information über den exakten Verlauf des Prozesses. 5 / 185 Wir interessieren uns für die stochastischen Eigenschaften der Prozesse, z.B. I Verteilung zu bestimmten Zeitpunkten, I Ein- und Austrittswahrscheinlichkeiten, I Erwartungswerte von mit dem Prozess zusammenhängenden Größen, I Zeitliche Mittel, Grenzverteilungen. 6 / 185 Inhalt I Wahrscheinlichkeitstheorie (Crashkurs) I Irrfahrten Markov-Ketten Poisson-Prozess Brownsche Bewegung I I I 7 / 185 1. Wahrscheinlichkeitstheorie (Crashkurs) Wir benötigen einen Werkzeugkasten von Begriffen und Resultaten aus der Wahrscheinlichkeitstheorie (siehe auch die Vorlesungen Statistik I und Statistik II). 1.1. Zufallsvariablen Eine reelle Zufallsvariable ist eine mathematische Größe, die „zufällige Werte” in R annimmt. Beispiel 1.1 Beim Würfelspiel nimmt die Zufallsvariable „Augenzahl” die Werte 1, 2, 3, 4, 5 und 6 an. Beispiel 1.2 Der Schlusskurs des DAX an der Börse kann als Zufallsvariable angesehen werden. Sie nimmt werte in der Menge R+ = [0, ∞) an . 8 / 185 Wir benötigen aber einen mathematischen Begriff, also definieren wir eine Zufallsvariable als eine Abbildung auf einem Wahrscheinlichkeitsraum. Definition 1.3 Ein Wahrscheinlichkeitsraum (Ω, A, P) besteht aus I einem Grundraum Ω, I einer Menge von Ereignissen A (sog. σ-Algebra. Die Elemente von A sind Teilmengen von Ω), I einem Wahrscheinlichkeitsmaß P, das jedem A ∈ A eine Wahrscheinlichkeit P(A) zuordnet, so dass gilt: I I I P(A) ∈ [0, 1], P(Ω) S∞= 1, P P( i=1 Ai ) = ∞ i=1 P(Ai ) für disjunkte Ereignisse A1 , A2 , . . .. Wir sagen, dass Ereignisse A, für die P(A) = 1 ist, fast sicher sind. 9 / 185 Definition 1.4 Eine reelle Zufallsvariable X ist eine Abbildung X : Ω → R, derart, dass die Menge K (x) = {ω ∈ Ω|X (ω) ≤ x} ein Ereignis ist für jedes x ∈ R. Zwei tröstliche Anmerkungen: I Diese Bedingung ist in der Regel für Abbildungen X : Ω → R erfüllt. Für uns ist daher jede Abbildung X : Ω → R, eine gültige Zufallsvariable. I Wir werden bald sehen, dass wir die Abbildungsnatur von Zufallsvariablen und den zugrundeliegenden Wahrscheinlichkeitsraum Ω bei der Betrachtung stochastischer Prozesse meist vernachlässigen können. 10 / 185 Beispiel 1.5 Die Zufallsvariable X beschreibe den Ausgang des Würfelspiels, d.h. die Augenzahl, die geworfen wurde. Der zugehörige Wahrscheinlichkeitsraum ist Ω = {1, 2, 3, 4, 5, 6}. Ereignisse sind alle Teilmengen von Ω, also zum Beispiel {1, 3, 5} Ereignis ’ungerade Augenzahl’ {4, 5, 6} Ereignis ’Augenzahl >3’ {1} Ereignis ’Augenzahl ist 1’ Die Zufallsvariable X : {1, 2, 3, 4, 5, 6} → R ist gegeben durch X (ω) = ω. Dann ist z.B. K (4.63) = {ω ∈ Ω|X (ω) ≤ 4.63} = {ω ∈ Ω|ω ≤ 4.63} = {1, 2, 3, 4}. 11 / 185 Beispiel 1.6 Es sei X die Summe der Augenzahlen bei zweimaligem Würfeln. Dann ist Ω = {ω = (ω1 , ω2 )|ω1 , ω2 ∈ {1, 2, 3, 4, 5, 6}} und X (ω) = ω1 + ω2 . Beispielsweise ist K (7) = {ω ∈ Ω|X (ω) ≤ 4} = {ω ∈ Ω|ω1 + ω2 ≤ 4} = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (3, 1)}. 12 / 185 1.2. Verteilungsfunktion Definition 1.7 Die Wahrscheinlichkeit des Ereignisses K (x) = {ω ∈ Ω|X (ω) ≤ x} ist eine Funktion von x, die man als Verteilungsfunktion von X bezeichnet: FX (x) = P(K (x)) = P(X ≤ x). Die Verteilungsfunktion FX ist I nicht fallend, I rechtsseitig stetig, d.h. limz↓x FX (z) = FX (x) I und es gilt lim F (x) = 0 x→−∞ X lim FX (x) = 1. x→∞ Zur Beschreibung der Verteilung einer Zufallsvariablen ist es ausreichend, die Verteilungsfunktion anzugeben. 13 / 185 Wir unterscheiden zwei Typen von Verteilungsfunktionen: stetige Verteilungsfunktionen: FX ist stetig und stückweise differenzierbar. diskrete Verteilungsfunktionen: FX ist stückweise konstant und hat Sprünge. 14 / 185 1.3. Stetige Verteilungsfunktionen Eine stetige Verteilungsfunktion hat die Darstellung Rx FX (x) = −∞ fX (u) du Rx = −∞ dFX (u). mit der Dichtefunktion fX (x) = FX0 (x) ≥ 0, die die Verteilung von X vollständig festlegt. Es gilt allgemeiner Z b P(a < X ≤ b) = fX (u) du a Z b = dFX (u). a 15 / 185 Achtung: Die Dichtefunktion fX (x) beschreibt keine Wahrscheinlichkeiten. Es gilt aber die Näherung P(x < X ≤ x + h) ≈ h · fX (x), h > 0, (und h klein). Es gilt für jedes x ∈ R: Z P(X = x) = x fX (u) du = 0, x wenn X eine stetige Zufallsvariable ist. Die Ereignisse 1. a ≤ X ≤ b 2. a < X ≤ b 3. a < X < b 4. a ≤ X < b haben dieselbe Wahrscheinlichkeit. 16 / 185 Beispiel 1.8 Eine Zufallsvariable X besitze die folgende Verteilungsfunktion: Dann ist z.B. P(X ≤ −2) = 0.2, P(X ≤ −1) = 0.5, P(X ≤ 3) = 0.9, P(X ≤ 7) = 1, P(−2 < X ≤ 1) = 0.3, P(1 < X ≤ 3) = 0.4 X ist fast sicher kleiner als 4. 17 / 185 Beispiel 1.9 Die Zufallsvariable X habe die Verteilungsfunktion (exponentielle Verteilung) FX (x) = 1 − e−x . Dann ist fX (x) = e−x . Zum Beispiel ist P(1 < X ≤ 1.1) ≈ 0.1 · e−1 ≈ 0.0368 Exakte Berechnung: P(1 < X ≤ 1.1) = FX (1.1) − FX (1) = e−1 − e−1.1 ≈ 0.0350 18 / 185 1.4. Diskrete Verteilungsfunktionen Eine diskrete Verteilungsfunktion ist stückweise konstant und hat an gewissen Stellen x1 , x2 , . . . Sprünge der Höhe p1 , p2 , . . .. Die zugehörige Zufallsvariable nimmt nur die Werte x1 , x2 , . . . mit positiver Wahrscheinlichkeit an: X ∈ {x1 , x2 , . . .} fast sicher. Es gilt X P(X = xk ) = pk , FX (x) = P(X ≤ x) = pi . i:xi ≤x 19 / 185 Notation zur Vereinfachung: Wir schreiben auch hier Z b g(u) dFX (u) a für die Summe X g(xi ) pi . i:a<xi ≤b Dann gilt, wie schon im stetigen Fall, Z x FX (x) = dFX (u). −∞ und P(a < X ≤ b) = FX (b) − FX (a) = X pi . i:a<xi ≤b 20 / 185 Beispiel 1.10 Die Zufallsvariable X habe die folgende Verteilungsfunktion: Dann gilt z.B. P(X = −3) = 0.5, P(X = 1) = 0.3, P(X = 4) = 0.2 P(X ≤ 0) = 0.5, P(X ≤ 2) = 0.8, P(X > 3) = 0.2 P(−1 < X ≤ 1) = 0.3, P(0 < X ≤ 6) = 0.5, P(X > −1) = 0.5, P(X ≥ −5) = 1. 21 / 185 1.5. Erwartungswerte Mit Hilfe der Verteilungsfunktion lassen sich berechnen: Der Erwartungswert Z ∞ E[X ] = x dFX (x). −∞ Allgemeiner: der Erwartungswert der Zufallsvariablen g(X ), wo g : R → R eine Funktion ist: Z ∞ E[g(X )] = g(x) dFX (x). −∞ Spezialfall: das k -te Moment Z ∞ k E[X ] = x k dFX (x). −∞ Diese Größen sind natürlich nur dann wohldefiniert, wenn die entsprechenden Integrale existieren. 22 / 185 Die Varianz von X ist definiert als der Erwartungswert der quadratischen Abweichung von E[X ]: Var[X ] = E[(X − E[X ])2 ] = E[X 2 ] − E[X ]2 . Es müssen die ersten beiden Momente existieren und es muss E[X ] < ∞ sein. Ist X fast sicher positiv, d.h. P(X > 0) = 1 (oder FX (0) = 0), dann gilt Z ∞ E[X ] = (1 − FX (u)) du. 0 23 / 185 1.6. Unabhängigkeit Zwei Zufallsvariablen heißen unabhängig, wenn P(X ≤ x, Y ≤ y ) = P(X ≤ x) · P(Y ≤ y ), x, y ∈ R gilt. Eine Familie von Zufallsvariablen (Xk )k ∈K ist unabhängig, wenn P(Xk1 ≤ xk1 , . . . , Xkj ≤ xkj ) = P(Xk1 ≤ xk1 ) · · · P(Xkj ≤ xkj ) für alle 1 ≤ j ≤ n und alle xj ∈ R gilt. Gilt dann noch P(Xk1 ≤ xk1 ) = . . . = P(Xkn ≤ xkn ), so sagt man die Zufallsvariablen seien unabhängig und identisch verteilt (kurz: i.i.d., engl. independent and identically distributed). 24 / 185 1.7. Bedingte Wahrscheinlichkeit und bedingte Erwartung Gegeben seien zwei diskrete Zufallsvariablen X und Y . Die bedingte Wahrscheinlichkeit, dass X = x ist, gegeben Y = y ist P(X = x, Y = y ) , P(X = x|Y = y ) = P(Y = y ) vorausgesetzt dass P(Y = y ) 6= 0 ist. Die bedingte Verteilungsfunktion von X gegeben Y = y ist FX (x|Y = y ) = P(X ≤ x|Y = y ). Den bedingten Erwartungswert von X , gegeben Y = y definieren wir natürlich als Z ∞ X E[X |Y = y ] = x dFX (x|Y = y ) = xi P(X = xi |Y = y ). −∞ i:xi ≤x 25 / 185 Wenn X und Y beide stetig sind, dann definieren wir die bedingte Dichtefunktion von X , gegeben Y = y als fX ,Y (x, y ) , fX (x|Y = y ) = fY (y ) wenn fY (y ) 6= 0 ist. Dabei ist fX ,Y (x, y ) die gemeinsame Dichtefunktion definiert durch Z Z y x −∞ −∞ P(X ≤ x, Y ≤ y ) = fX ,Y (u, w) du dw. Die bedingte Verteilungsfunktion von X , gegeben Y = y , ist dann Z x FX (x|Y = y ) = fX (u|Y = y ) du. −∞ Entsprechend ergibt sich der bedingte Erwartungswert von X , gegeben Y = y : Z ∞ Z ∞ E[X |Y = y ] = x dFX (x|Y = y ) = x fX (x|Y = y ) dx. −∞ −∞ 26 / 185 Allgemein ist die bedingte Erwartung von X , gegeben Y = y, Z ∞ E[X |Y = y ] = x dFX (x|Y = y ) = g(y ) −∞ eine Funktion von y . Wir definieren dann die bedingte Erwartung von X gegeben Y als die Zufallsvariable E[X |Y ] = g(Y ). 27 / 185 1.8. Bedingungsformeln Zu den wichtigsten Formeln der angewandten Stochastik gehören: Z ∞ P(A) = P(A|Y = y ) dFY (y ), Z−∞ ∞ E[X |Y = y ] dFY (y ). E[X ] = −∞ 28 / 185 Spezialfälle: Ist Y eine stetige Zufallsvariable mit Dichtefunktion fY , dann gilt entsprechend Z ∞ P(A) = P(A|Y = y ) fY (y ) dy −∞ Z ∞ E[X ] = E[X |Y = y ] fY (y ) dy . −∞ Ist Y eine diskrete Zufallsvariable mit Wahrscheinlichkeiten pi = P(Y = yi ), dann ergibt sich die Formel X P(A) = P(A|Y = yi ) pi yi E[X ] = X E[X |Y = yi ] pi . yi 29 / 185 Beispiel 1.11 X und Y seien zwei unabhängige Zufallsvariablen mit identischer Verteilung (Gleichverteilung auf [0, 1]) ( x ; x ∈ [0, 1] FX (x) = FY (x) = 0 ; sonst Wie groß ist E[max{X , Y }]? E[max{X , Y }] Z ∞Z ∞ = E[max{X , Y }|Y = y , X = x] dFY (y ) dFX (x) −∞ −∞ Z ∞Z ∞ = max{x, y } dFY (y ) dFX (x) −∞ −∞ 1Z 1 Z max{x, y } dy dx Z 1Z x Z 1Z 1 = x dy dx + y dy dx = 0 0 0 0 0 x 30 / 185 Z 1 x Z E[max{X , Y }] = 1 Z y dy dx x dy dx + 0 Z 0 0 1 Z x = 0 Z x x 1 Z dy dx + 0 1 1 1 − 2 2 0 1 1 11 2 = + − = . 3 2 23 3 = 1 Z x 2 dx + 0 Z 1 1 − x 2 dx 2 1 x 2 dx 0 Simulation: 31 / 185 1.9. Die Faltung Seien X und Y zwei unabhängige Zufallsvariablen mit gemeinsamer Verteilungsfunktion FX ,Y und sei S = X + Y . Dann ist FS (x) = P(X + Y ≤ x) Z ∞ = P(X + Y ≤ x|Y = y ) dFY (y ) −∞ Z ∞ = P(X + y ≤ x) dFY (y ) −∞ Z ∞ = P(X ≤ x − y ) dFY (y ) −∞ Z ∞ = FX (x − y ) dFY (y ) −∞ Den Ausdruck auf der rechten Seite bezeichnet man als Faltung von FX und FY und schreibt Z ∞ FX ∗ FY (x) = FX (x − y ) dFY (v ). −∞ 32 / 185 Beispiel 1.12 Seien X und Y unabhängig und identisch verteilt mit exponentieller Verteilung (mit Parameter λ). Dann ist Z ∞ FX ∗ FY (x) = FX (x − y ) dFY (y ) −∞ Z x = (1 − e−λ(x−y ) )λe−λy dy Z0 x Z x −λy = λe dy − e−λ(x−y ) λe−λy dy 0 Z x0 = 1 − e−λx − λ dy e−λx −λx 0 −λx = 1−e − λxe = 1 − (1 + λx)e−λx . Diese Verteilung nennt sich Erlang-Verteilung (Spezialfall einer Gammaverteilung). 33 / 185 1.10. Das Gesetz der großen Zahlen Beispiel 1.13 Ein Würfel werde mehrmals geworfen. Es sei Xk die Augensumme im k -ten Wurf. Dann ist (Xk )k ∈N ein stochastischer Prozess. Es ist natürlich P(Xi = k ) = 1/6 und 6 X 7 1 E[Xk ] = i = . 6 2 i=1 34 / 185 Es sei n 1X mn = xi n k =1 das empirische arithmetische Mittel. Es scheint mn → E[X1 ] für n → ∞ zu gelten. 35 / 185 Wir definieren Sn = X1 + X2 + . . . + Xn = n X Xi . k =1 Satz 1.14 (Starkes Gesetz der großen Zahlen) Sind X1 , X2 , . . . i.i.d. mit Erwartungswert µ dann gilt S n P → µ = 1. n Die Wahrscheinlichkeit, dass im Würfelbeispiel der empirische Mittelwert nicht gegen 7/2 konvergiert, ist also Null. 36 / 185 1.11. Der Zentrale Grenzwertsatz P Sei wieder Sn = nk=1 Xk die Summe von i.i.d. Zufallsvariablen X1 , X )2, . . . mit µ = E[X1 ] < ∞, E[X 2 ] < ∞, σ 2 = Var[X1 ]. Wie wissen bereits P( Sn → µ) = 1. n Konvergiert auch Sn − n · µ? 37 / 185 Beispiel 1.15 Würfelbeispiel: Sn − nµ scheint nicht zu konvergieren. 38 / 185 Es stellt sich heraus, dass Sn − nµ konvergiert, wenn man die Folge entsprechend skaliert: Satz 1.16 (Zentraler Grenzwertsatz) Sind X1 , X2 , . . . i.i.d. mit endlichem Erwartungswert µ und endlicher Varianz σ 2 , dann gilt S − nµ n √ P ≤ x → Φ(x), σ n wobei Φ die Verteilungsfunktion der Standartnormalverteilung ist. Dichte der Standartnormalverteilung 1 2 1 Φ0 (x) = √ e− 2 x . 2π Verteilungsfunktion der Standartnormalverteilung Z x 1 2 1 Φ(x) = √ e− 2 u du. 2π −∞ 39 / 185 Tabelle der Werte der normierten Normalverteilung Φ(x) für x ∈ [−2, 0]. Beispiel: Φ(−0.63) = 0.2643. −2.5 −2.4 −2.3 −2.2 −2.1 −2. −1.9 −1.8 −1.7 −1.6 −1.5 −1.4 −1.3 −1.2 −1.1 −1. −0.9 −0.8 −0.7 −0.6 −0.5 −0.4 −0.3 −0.2 −0.1 0. 0. 0.0062 0.0082 0.0107 0.0139 0.0179 0.0228 0.0287 0.0359 0.0446 0.0548 0.0668 0.0808 0.0968 0.1151 0.1357 0.1587 0.1841 0.2119 0.242 0.2743 0.3085 0.3446 0.3821 0.4207 0.4602 0.5 0.01 0.006 0.008 0.0104 0.0136 0.0174 0.0222 0.0281 0.0351 0.0436 0.0537 0.0655 0.0793 0.0951 0.1131 0.1335 0.1562 0.1814 0.209 0.2389 0.2709 0.305 0.3409 0.3783 0.4168 0.4562 0.496 0.02 0.0059 0.0078 0.0102 0.0132 0.017 0.0217 0.0274 0.0344 0.0427 0.0526 0.0643 0.0778 0.0934 0.1112 0.1314 0.1539 0.1788 0.2061 0.2358 0.2676 0.3015 0.3372 0.3745 0.4129 0.4522 0.492 0.03 0.0057 0.0075 0.0099 0.0129 0.0166 0.0212 0.0268 0.0336 0.0418 0.0516 0.063 0.0764 0.0918 0.1093 0.1292 0.1515 0.1762 0.2033 0.2327 0.2643 0.2981 0.3336 0.3707 0.409 0.4483 0.488 0.04 0.0055 0.0073 0.0096 0.0125 0.0162 0.0207 0.0262 0.0329 0.0409 0.0505 0.0618 0.0749 0.0901 0.1075 0.1271 0.1492 0.1736 0.2005 0.2296 0.2611 0.2946 0.33 0.3669 0.4052 0.4443 0.484 0.05 0.0054 0.0071 0.0094 0.0122 0.0158 0.0202 0.0256 0.0322 0.0401 0.0495 0.0606 0.0735 0.0885 0.1056 0.1251 0.1469 0.1711 0.1977 0.2266 0.2578 0.2912 0.3264 0.3632 0.4013 0.4404 0.4801 0.06 0.0052 0.0069 0.0091 0.0119 0.0154 0.0197 0.025 0.0314 0.0392 0.0485 0.0594 0.0721 0.0869 0.1038 0.123 0.1446 0.1685 0.1949 0.2236 0.2546 0.2877 0.3228 0.3594 0.3974 0.4364 0.4761 0.07 0.0051 0.0068 0.0089 0.0116 0.015 0.0192 0.0244 0.0307 0.0384 0.0475 0.0582 0.0708 0.0853 0.102 0.121 0.1423 0.166 0.1922 0.2206 0.2514 0.2843 0.3192 0.3557 0.3936 0.4325 0.4721 0.08 0.0049 0.0066 0.0087 0.0113 0.0146 0.0188 0.0239 0.0301 0.0375 0.0465 0.0571 0.0694 0.0838 0.1003 0.119 0.1401 0.1635 0.1894 0.2177 0.2483 0.281 0.3156 0.352 0.3897 0.4286 0.4681 0.09 0.0048 0.0064 0.0084 0.011 0.0143 0.0183 0.0233 0.0294 0.0367 0.0455 0.0559 0.0681 0.0823 0.0985 0.117 0.1379 0.1611 0.1867 0.2148 0.2451 0.2776 0.3121 0.3483 0.3859 0.4247 0.4641 40 / 185 Tabelle der Werte der normierten Normalverteilung Φ(x) für x ∈ [−2, 0]. Beispiel: Φ(0.63) = 0.7357. 0. 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1. 1.1 1.2 1.3 1.4 1.5 1.6 1.7 1.8 1.9 2. 2.1 2.2 2.3 2.4 2.5 0. 0.5 0.5398 0.5793 0.6179 0.6554 0.6915 0.7257 0.758 0.7881 0.8159 0.8413 0.8643 0.8849 0.9032 0.9192 0.9332 0.9452 0.9554 0.9641 0.9713 0.9772 0.9821 0.9861 0.9893 0.9918 0.9938 0.01 0.504 0.5438 0.5832 0.6217 0.6591 0.695 0.7291 0.7611 0.791 0.8186 0.8438 0.8665 0.8869 0.9049 0.9207 0.9345 0.9463 0.9564 0.9649 0.9719 0.9778 0.9826 0.9864 0.9896 0.992 0.994 0.02 0.508 0.5478 0.5871 0.6255 0.6628 0.6985 0.7324 0.7642 0.7939 0.8212 0.8461 0.8686 0.8888 0.9066 0.9222 0.9357 0.9474 0.9573 0.9656 0.9726 0.9783 0.983 0.9868 0.9898 0.9922 0.9941 0.03 0.512 0.5517 0.591 0.6293 0.6664 0.7019 0.7357 0.7673 0.7967 0.8238 0.8485 0.8708 0.8907 0.9082 0.9236 0.937 0.9484 0.9582 0.9664 0.9732 0.9788 0.9834 0.9871 0.9901 0.9925 0.9943 0.04 0.516 0.5557 0.5948 0.6331 0.67 0.7054 0.7389 0.7704 0.7995 0.8264 0.8508 0.8729 0.8925 0.9099 0.9251 0.9382 0.9495 0.9591 0.9671 0.9738 0.9793 0.9838 0.9875 0.9904 0.9927 0.9945 0.05 0.5199 0.5596 0.5987 0.6368 0.6736 0.7088 0.7422 0.7734 0.8023 0.8289 0.8531 0.8749 0.8944 0.9115 0.9265 0.9394 0.9505 0.9599 0.9678 0.9744 0.9798 0.9842 0.9878 0.9906 0.9929 0.9946 0.06 0.5239 0.5636 0.6026 0.6406 0.6772 0.7123 0.7454 0.7764 0.8051 0.8315 0.8554 0.877 0.8962 0.9131 0.9279 0.9406 0.9515 0.9608 0.9686 0.975 0.9803 0.9846 0.9881 0.9909 0.9931 0.9948 0.07 0.5279 0.5675 0.6064 0.6443 0.6808 0.7157 0.7486 0.7794 0.8078 0.834 0.8577 0.879 0.898 0.9147 0.9292 0.9418 0.9525 0.9616 0.9693 0.9756 0.9808 0.985 0.9884 0.9911 0.9932 0.9949 0.08 0.5319 0.5714 0.6103 0.648 0.6844 0.719 0.7517 0.7823 0.8106 0.8365 0.8599 0.881 0.8997 0.9162 0.9306 0.9429 0.9535 0.9625 0.9699 0.9761 0.9812 0.9854 0.9887 0.9913 0.9934 0.9951 0.09 0.5359 0.5753 0.6141 0.6517 0.6879 0.7224 0.7549 0.7852 0.8133 0.8389 0.8621 0.883 0.9015 0.9177 0.9319 0.9441 0.9545 0.9633 0.9706 0.9767 0.9817 0.9857 0.989 0.9916 0.9936 0.9952 41 / 185 Beispiel 1.17 Würfelbeispiel: E[X ] = 7 , 2 Var[X ] = 35 . 12 Dann gilt S − 7n n 2 P p ≤ x → Φ(x). 35/12n Oder (für großes n): x − 7n 2 P(Sn ≤ x) ≈ Φ p . 35/12n Beispiel: 340 − 350 P(S100 ≤ 340) ≈ Φ p ≈ Φ(−0, 59) 3500/12 = 0.2776 42 / 185 p Normalverteilung Φ((x − 7/2n)/ 35/12n) (rot) und empirische Verteilungsfunktion von S1 , S2 , S10 , S100 (10 000 Samples, blau). 43 / 185 2. Irrfahrten 2.1. Die symmetrische einfache Irrfahrt In einem Spiel werde eine Münze geworfen. Es sei Xn = 1, wenn im n-ten Spiel Kopf geworfen wurde und Xn = −1, wenn im n-ten Spiel eine Zahl fällt. Dann ist (Xn )n∈N ein stochastischer Prozess. 44 / 185 Die Partialsummen Sn = X1 + X2 + . . . + Xn = n X Xk k =1 bilden einen zweiten stochastischen Prozess (Sn )n∈N0 , die sogenannte symmetrische einfache Irrfahrt. 45 / 185 2.2. Verteilung der symmetrischen einfachen Irrfahrt Wie groß sind die Wahrscheinlichkeiten P(Sn = k ) für k ∈ Z? Schätzung mit Hilfe des zentralen Grenzwertsatzes. Es ist E[X1 ] = 0, E[X12 ] = 1, Var[X1 ] = 1. Also schätzen wir: P(Sn = k ) ≈ P(k − 1 ≤ Sn ≤ k + 1) k + 1 − nµ k − 1 − nµ √ √ ≈ Φ( ) − Φ( ) σ n σ n k +1 k −1 = Φ( √ ) − Φ( √ ). n n Zum Beispiel −1 −3 P(S8 = −2) ≈ Φ( √ ) − Φ( √ ) 8 8 ≈ Φ(−0, 35) − φ(−1, 06) ≈ 0.3632 − 0.1446 = 0.2186. 46 / 185 Sei Uk die Anzahl der Kopf-Würfe bis zum n-ten Wurf und Lk die Anzahl der Zahl-Würfe bis zum n-ten Wurf. Dann ist Sn = Un − Ln . 47 / 185 Es gilt: ⇔ ⇔ Sn = k Ln = Un − k = n − Un n+k Un = . 2 Also gilt ( 0 P(Sn = k ) = P(Un = n+k ) 2 ; n + k ungerade ; n + k gerade. Es bleibt die Verteilung von Un zu berechnen. Beachte: Es gilt Un = i, genau dann, wenn von den n Würfen i mal Kopf fällt. 48 / 185 Beispiel 2.1 Sei n = 5 und i = 3. Dann gibt es folgende Möglichkeiten: 1 2 3 4 5 K K K Z K K K Z K K K Z K K Z Z K K K Z Z Z Z Z K 6 7 8 9 10 K Z K Z Z Z K Z K Z K K Z Z K Z Z K K K K K K K K Das entspricht der Anzahl der 3-elementigen Teilmengen einer Menge mit 5 Elementen: 5 5! 120 = = 10. = 3!(5 − 3)! 12 3 Bei insgesamt 25 Möglichkeiten ergibt sich 5 P(U5 = 3) = 3 25 . 49 / 185 Die allgemeine Formel ist dann n −n P(Un = i) = 2 . i Für |k | ≤ n hatten wir gefunden: ( 0 ; n + k ungerade P(Sn = k ) = n+k P(Un = 2 ) ; n + k gerade. Satz 2.2 Für die symmetrische einfache Irrfahrt gilt für |k | ≤ n und n ∈ N0 : ; n + k ungerade 0 P(Sn = k ) = n n+k 2−n ; n + k gerade 2 50 / 185 Grafik: Berechnete (rot) und simulierte (blau, 1000 Irrfahrten) Wahrscheinlichkeiten P(Sn = k ) für n = 8. 8 −8 Zum Beispiel: P(S8 = −2) = 2 = 0.21875 3 (unsere ZGS-Schätzung: 0.2186). 51 / 185 Grafik: Berechnete (rot) und simulierte (blau, 10000 Irrfahrten) Wahrscheinlichkeiten P(Sn = k ) für n = 30. 52 / 185 2.3. Austrittszeiten aus einem Streifen Sei Tm der erste Index, bei dem entweder Sn = −b oder Sn = b ist, vorausgesetzt dass S0 = m ist. 53 / 185 Es ist E[T0 ] = E[T0 |X1 = 1]P(X1 = 1) + E[T0 |X1 = −1]P(X1 = −1) 1 1 = (1 + E[T1 ]) + (1 + E[T−1 ]) 2 2 = 1 + E[T1 ]. 1 1 1 1 E[T1 ] = 1 + E[T2 ] + E[T0 ] = 1 + E[T2 ] + 1 + E[T1 ] 2 2 2 2 = 3 + E[T2 ] 1 1 1 1 E[T2 ] = 1 + E[T3 ] + E[T1 ] = 1 + E[T3 ] + 3 + E[T2 ] 2 2 2 2 = 5 + E[T3 ] E[T3 ] = 7 + E[T4 ] E[Tk ] = 2k + 1 + E[Tk +1 ]. 54 / 185 Es ist E[Tb ] = 0, also E[Tb−1 ] = 2(b − 1) + 1 + E[Tb ] = 2b − 1 | {z } =0 E[Tb−2 ] = 2(b − 2) + 1 + 2b − 1 = 4b − 4 E[Tb−3 ] = 2(b − 3) + 1 + 4b − 4 = 6b − 9 E[Tb−4 ] = 2(b − 4) + 1 + 6b − 9 = 8b − 16 E[Tb−5 ] = 2(b − 5) + 1 + 8b − 16 = 10b − 25 E[Tb−k ] = 2kb − k 2 . Einsetzen von b − k für k in die Formel ergibt: Satz 2.3 Für die symmetrische einfache Irrfahrt gilt: E[Tk ] = b2 − k 2 = (b − k )(b + k ). 55 / 185 Wir nehmen nun an, dass S0 = 0 ist. Es sei nun T (a, b) der erste Index mit Sn = −a oder Sn = b. 56 / 185 T (a, b) = a + b 2 = a · b. a − b a + b a − b − + 2 2 2 Satz 2.4 Für die symmetrische einfache Irrfahrt gilt: E[T (a, b)] = a · b. 57 / 185 Beispiel 2.5 Wie lange dauert es im Mittel, bis ein Spieler beim Münzwurfspiel entweder ruiniert ist (Sn = −1) oder sein Spielkapital auf 10 Euro angewachsen ist (Sn = 10)? Antwort: E[T (1, 10)] = 10. Wie lange dauert es im Mittel, wenn er bereits 7 Euro eingespielt hat? Antwort: E[T (8, 3)] = 24. 58 / 185 Lassen wir in der Formel E[T (a, b)] = a · b die untere Begrenzung a gegen ∞ streben, so ergibt sich: Satz 2.6 Für die symmetrische einfache Irrfahrt gilt: E[T (∞, b)] = ∞ für jedes b ∈ N. 59 / 185 3. Markov-Ketten 3.1. Motivation: Irrfahrt mit Leitplanken Wir definieren eine doppelt reflektierte Irrfahrt (Irrfahrt mit Leitplanken): P(Xn+1 = Xn + 1) = 12 wenn − 2 < Xn < 2, P(Xn+1 = Xn − 1) = 21 wenn − 2 < Xn < 2, P(Xn+1 = 1) = 1 wenn Xn = 2, P(Xn+1 = −1) = 1 wenn Xn = −2. Dann ist Xn ein stochastischer Prozess mit Zustandsraum E = {−2, −1, 0, 1, 2}. 60 / 185 Die Ereignisse {Xn = j} hängen nur von Xn−1 ab und nicht von X1 , X2 , . . . , Xn−2 . Außerdem sind die Übergangswahrscheinlichkeiten pij = P(Xn = j|Xn−1 = i) von n unabhängig. Wir definieren die sog. Übergangsmatrix: 0 1 0 0 0 1 0 1 0 0 2 1 2 1 P= 0 2 01 2 01 0 0 0 2 2 0 0 0 1 0 Die Matrix ist eine stochastische Matrix, weil die Zeilensumme für jede Zeile = 1 ist. 61 / 185 Wie findet man die Verteilung von X2 ? Es ist z.B. P(X2 = 1|X0 = −1) 2 X = P(X1 = j|X0 = −1)P(X2 = 1|X0 = −1, X1 = j) j=−2 = 2 X P(X1 = j|X0 = −1)P(X2 = 1|X1 = j) j=−2 = 2 X p−1,j pj,1 = 1/4. j=−2 Entsprechend erhält man P P(X2 = i|X0 = j) = 2k =−2 pjk pki = (P 2 )ji . 62 / 185 Also ist die Matrix P = 2 0.5 0. 0.5 0. 0. 0. 0.75 0. 0.25 0. 0.25 0. 0.5 0. 0.25 0. 0.25 0. 0.75 0. 0. 0. 0.5 0. 0.5 die 2-Schritt-Übergangsmatrix von Xn . Allgemeiner: P n ist die n-Schritt-Übergangsmatrix des stochastischen Prozesses Xn , d.h. P(Xn = i|X0 = j) = P(Xk +n = i|Xk = j) = (P n )ij . Beispielsweise ist P 20 = 0.250488 0. 0.5 0. 0.249512 0. 0.500488 0. 0.499512 0. 0.25 0. 0.5 0. 0.25 0. 0.499512 0. 0.500488 0. 0.249512 0. 0.5 0. 0.250488 . 63 / 185 3.2. Markov-Ketten Definition 3.1 Eine (homogene) Markov-Kette mit endlichem Zustandsraum ist ein stochastischer Prozess (Xn )n∈N0 mit Werten in einer beliebigen Menge E = {x1 , x2 , . . . , xn }, für den gilt: A.A.Markov (1856-1922) 1. Markov-Eigenschaft: Die zukünftige Entwicklung des Prozesses hängt nur vom gegenwärtigen Zustand ab, nicht von der Vergangenheit: P(Xn = xi |X0 = xj0 , . . . , Xn−1 = xjn−1 ) = P(Xn = xi |Xn−1 = xjn−1 ), 2. Die Wahrscheinlichkeiten P(Xn = xi |Xn−1 = xj ) sind unabhängig von n ist (Zeit-Homogenität). 64 / 185 Wir schreiben kurz pij = P(Xn = xi |Xn−1 = xj ) für die Übergangswahrscheinlichkeiten. Die Gesamtheit der Wahrscheinlichkeiten pij kann man unter Zuhilfenahme einer n × n Matrix, der Übergangsmatrix, darstellen: p11 p12 . . . p1(n−1) p1n p21 p22 . . . p2(n−1) p2n P = (pij ) = .. .. .. .. .. . . . . . pn1 pn2 . . . pn(n−1) pnn 65 / 185 Beispiel 3.2 (Würfelspiel) Sei Xn die Anzahl der Augenzahlen, die bis zum n-ten Spiel noch nicht gefallen sind. Dann ist Xn eine Markov-Kette mit Zustandsraum E = {0, 1, 2, 3, 4, 5, 6} und Übergangsmatrix P= 1 0 1 6 5 6 1 3 0 0 0 0 0 0 0 0 0 0 0 2 3 1 2 0 0 0 0 0 0 1 2 2 3 0 0 0 0 0 0 1 3 5 6 0 0 0 0 0 0 1 6 1 0 0 0 0 0 0 0 66 / 185 3.3. Übergangswahrscheinlichkeiten 1-Schritt-Übergangswahrscheinlichkeiten: Die Übergangswahrscheinlichkeiten pij = P(Xn+1 = xi |Xn = xj ) kann man als Matrix P = (pij ) schreiben. n-Schritt-Übergangswahrscheinlichkeiten: Wir schreiben (n) pij = P(Xn = xi |X0 = xj ). Satz 3.3 Die n-Schritt-Übergangswahrscheinlichkeiten ergeben sich als Elemente der Matrix P n , also (n) pij = (P n )ij . 67 / 185 n-Schritt-Übergangswahrscheinlichkeiten mit zufälligem Anfang: Es seien πi = P(X0 = xi ) die Anfangswahrscheinlichkeiten und π = (π1 , π2 , . . . , πn ) der Vektor der Anfangswahrscheinlichkeiten. Dann ergibt sich die praktische Formel X P(Xm = xj ) = P(Xm = xj |X0 = k )P(X0 = k ) k = X πk pkjm = (π · P m )j . k m Dabei ist (π · P )j die j-te Koordinate des Vektors π · P m . 68 / 185 Beispiel 3.4 Ein Parkplatz hat 5 Stellplätze. Sei Xn die Anzahl der Autos auf dem Parkplatz nach n Minuten. Es sei (Achtung, Schreibweise nicht ganz korrekt!) Xn + 1 mit Ws. 0.4 Xn+1 = Xn − 1 mit Ws. Xn /10 Xn mit Ws. 0.6 − Xn /10 für Xn < 5 und für Xn = 5 ( Xn − 1 Xn+1 = Xn mit Ws. 0.5 mit Ws. 0.5 Xn ist eine Markov-Kette mit 6 Zuständen {0, 1, 2, 3, 4, 5}. 69 / 185 Die Übergangsmatrix ist gegeben durch 0.6 0.4 0 0 0 0 0.1 0.5 0.4 0 0 0 0 0.2 0.4 0.4 0 0 P = (pij ) = 0 0 0.3 0.3 0.4 0 0 0 0 0.4 0.2 0.4 0 0 0 0 0.5 0.5 Simulation 70 / 185 Für die 2-Schritt-Übergangsmatrix ergibt sich: 0.4 0.44 0.16 0. 0. 0. 0.11 0.37 0.36 0.16 0. 0. 0.02 0.18 0.36 0.28 0.16 0. P2 = 0. 0.06 0.21 0.37 0.2 0.16 0. 0. 0.12 0.2 0.4 0.28 0. 0. 0. 0.2 0.35 0.45 Außerdem ist 0.023 0.023 0.023 100 P = 0.023 0.023 0.023 Interpretation? 0.093 0.093 0.093 0.093 0.093 0.093 0.187 0.187 0.187 0.187 0.187 0.187 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.249 0.199 0.199 0.199 0.199 0.199 0.199 71 / 185 Zum Zeitpunkt null (z.B. Mittags um 12 Uhr) sei die Anfangsverteilung π = (0.0, 0.1, 0.2, 0.2, 0.5, 0.0), d.h. die Markov-Kette befindet sich z.B. im Zustand 3 (d.h. drei PKW befinden sich im Parkhaus) mit Wahrscheinlichkeit 0.2. Dann ist z.B. P(X20 = 3) = (π · P 20 )3 Es ist 0.03 0.109 0.2 0.247 0.233 0.181 0.027 0.103 0.194 0.248 0.24 0.188 0.025 0.097 0.19 0.248 0.245 0.194 20 P = 0.023 0.093 0.186 0.249 0.249 0.199 0.022 0.09 0.184 0.249 0.252 0.203 0.021 0.088 0.182 0.249 0.254 0.205 und daher P(X20 = 3) = 0.187. 72 / 185 3.4. Klassifikation von Zuständen: Erreichbarkeit Ein Zustand xj ist vom Zustand xi aus erreichbar, wenn (n) pij > 0 ist für irgendein n ∈ N ∪ {0}. Wir schreiben dann xi → xj Zwei Zustände x und y kommunizieren, wenn x → y und y → x gilt. Notation: x ↔ y . Die Markov-Kette heißt irreduzibel, wenn x ↔ y gilt für je zwei Zustände x und y in E. 73 / 185 Ein Übergangsdiagramm beschreibt die Zustände und die Übergangswahrscheinlichkeiten in einem Graphen als Knoten mit gewichteten und gerichteten Kanten. 74 / 185 Beispiel 3.5 Eine Maschine befindet sich in einem der drei Zustände (A) „intakt”, (B) „defekt” und (C) „in Reparatur”. Sei Xn ∈ {A, B, C} der Zustand der Maschine nach n Tagen. Die Übergangswahrscheinlichkeiten seien wie folgt gegeben: Es gilt A → A, A → B, A → C, B → B, B → C, B → A, C → C, C → A, C → B. Die Markov-Kette ist irreduzibel. 75 / 185 0.95 0.05 0 0 1 P = 0 0.4 0 0.6 0.851 0.043 0.106 P 100 = 0.851 0.043 0.106 0.851 0.043 0.106 Simulation: 76 / 185 Der Zustandsraum E einer Markov-Kette zerfällt in sogenannte kommunizierende Klassen C1 , C2 , . . . , Ck Jedes x ∈ E ist Element genau einer Klasse und es gilt x ↔ y für alle Elemente y in derselben Klasse. Es gilt k [ E= Ci , i=1 ∅= k \ Ci . i=1 Ist x ∈ Ci , so besteht Ci aus genau der Teilmenge von Zuständen, die mit x kommunizieren. Genau dann, wenn es nur eine solche Klasse gibt, ist die Markov-Kette irreduzibel. 77 / 185 Beispiel 3.6 Eine Markov-Kette habe folgendes Übergangsdiagramm: Die Markov-Kette ist nicht irreduzibel. Es gilt z.B. nicht 3 ↔ 1 oder 5 ↔ 2. Die kommunizierenden Klassen sind C1 = {1, 2} und C2 = {3, 4, 5}. Es ist 0.2 0.95 P= 0 0 0 0.8 0 0 0 0 0.05 0 0 0 0 1 0 0 0.4 0 0.6 0 0.5 0.5 0 78 / 185 Wir haben P 50 = 0.178 0.146 0.209 0.293 0.174 0.173 0.142 0.212 0.297 0.176 0. 0. 0.304 0.435 0.261 0. 0. 0.304 0.435 0.261 0. 0. 0.304 0.435 0.261 0.002 0.002 0.303 0.433 0.26 0.002 0.001 0.303 0.433 0.26 0. 0. 0.304 0.435 0.261 0. 0. 0.304 0.435 0.261 0. 0. 0.304 0.435 0.261 und P 250 = 79 / 185 Übergangsdiagramm Simulation 80 / 185 3.5. Klassifikation von Zuständen: Periodizität Gilt für einen Zustand xi ∈ E (m) pii > 0, dann kann man von xi aus xi in m-Schritten erreichen. Der g.g.T. (größte gemeinsame Teiler) derjenigen m, für die (m) pii > 0 ist, heißt die Periode des Zustandes xi , geschrieben per(xi ). Beispiel 3.7 Ist z.B. für einen Zustand i (1) (2) pii = 0, pii = 0, (4) pii = 0, (7) (5) pii = 0, (8) (3) pii > 0, (6) pii > 0, (9) pii = 0, pii = 0, pii > 0, . . . dann ist die Periode des Zustands xi gleich 3. 81 / 185 Beispiel 3.8 Die Markov-Kette ist nicht irreduzibel. Es gibt drei Klassen E1 = {1}, E2 = {2, 4}, E3 = {3, 5}. Es ist per(1) = 1, per(2) = 2, per(3) = 2, per(4) = 2 und per(5) = 2. 82 / 185 3.6. Klassifikation von Zuständen: Rekurrenz Ein Zustand xi ∈ E heißt rekurrent, wenn die Ws. vom Zustand xi den Zustand xi (irgendwann) wieder zu erreichen gleich eins ist. Anderenfalls heißt der Zustand transient. Ist die erwartete Zeit bis zur Rückkehr endlich, so heißt xi positiv rekurrent, ansonsten nullrekurrent. Rekurrenz und Transienz häufig sind nicht einfach nachzuweisen. Ein Zustand xi ist mit Sicherheit transient wenn es einen Zustand xj 6= xi gibt, für den i → j und nicht j → i gilt. 83 / 185 Satz 3.9 Periodizität, Rekurrenz und Transienz sind Eigenschaften einer gesamten Klasse, d.h. alle oder keine Zustände einer Klasse haben diese Eigenschaften. Beispiel 3.10 84 / 185 Beispiel 3.11 85 / 185 Beispiel 3.12 86 / 185 Beispiel 3.13 Alle Zustände sind rekurrent. 87 / 185 3.7. Stationäre Verteilung und Grenzverhalten Definition 3.14 Eine stationäre Verteilung einer Markov-Kette auf dem Zustandsraum E = {x1 , x2 , . . . , xn } ist eine Anfangsverteilung π = (π1 , π2 , . . . , πn ), für die π·P =π gilt, d.h. die Wahrscheinlichkeiten nach einem Schritt stimmen mit der Anfangsverteilung überein. Es gilt dann natürlich auch π · P n = π, gilt, d.h. die Wahrscheinlichkeiten nach n Schritten stimmen mit der Anfangsverteilung überein. 88 / 185 Die Gleichung πP = π kann man als π(P − In ) = 0 schreiben, wobei In die n × n-Einheitsmatrix ist. Wir können auch schreiben (P − In )T π = 0. Um eine stationäre Anfangsverteilung zu finden, muss man also nur ein homogenes lineares Gleichungssystem lösen und dann diejenige Lösung finden. Uns interessieren natürlich nur Lösungen, für die π1 + . . . + πn = 1 ist. 89 / 185 Beispiel 3.15 Es sei Xn eine Markov-Kette auf E = {1, 2, 3} und 0 12 12 P = 13 13 13 1 0 0 die zugehörige Übergangsmatrix. 90 / 185 Es ist π(P − In ) = 0, g.d.w. (P − In )T π = 0 −1 31 1 1 −2 0 = 0 2 3 1 1 −1 2 3 1 − 13 −1 ⇔ 0 −1 1 = 0 0 12 − 21 1 0 − 43 0 1 −1 =0 ⇔ 0 0 0 Lösung π = c · (− 43 , −1, −1) mit c ∈ R. In unserem Fall muss c · (− 43 − 1 − 1) = 1 gelten: 4 0.4 −3 3 π = − −1 = 0.3 . 10 0.3 −1 91 / 185 Bemerkung: Hat die Matrix P − In stets einen Rang, der kleiner ist als n? Ja, denn P ist eine stochastische Matrix, d.h. die Zeilensummen sind eins. Wenn man also die n Spalten von P − In addiert, ergibt sich der Nullvektor, d.h. die Spaltenvektoren sind linear abhängig. 92 / 185 Beispiel 3.16 Es sei 1 2 1 2 1 3 0 0 2 0 0 3 P= 0 0 1 3 4 4 4 0 0 15 5 93 / 185 Es ist − 12 1 (P − In )T = 02 0 − 23 2 3 0 0 0 − 34 0 0 − 45 − 45 − 54 − 45 − 45 0 − 58 − 12 10 − 16 15 0 0 0 − 34 3 4 4 5 0 0 − 45 Wir lösen das LGS 1 2 0 0 0 − 23 2 3 3 4 3 4 1 2 0 0 0 0 0 0 1 0 0 0 2 3 0 0 0 0 0 1 0 0 0 0 0 1 0 3 4 94 / 185 , −1). Lösung: π = c(− 85 , − 65 , − 16 15 Dann ist 1 c = 8 6 16 = −15/73. − 5 − 5 − 15 − 1 Daher ergibt sich für die stationäre Verteilung: π = ( 24 , 18 , 16 , 15 ) 73 73 73 73 = (0.328767, 0.246575, 0.219178, 0.205479). Interessante Beobachtung: 0.328767 0.246575 0.328767 0.246575 P 100 = 0.328767 0.246575 0.328767 0.246575 0.219178 0.219178 0.219178 0.219178 0.205479 0.205479 . 0.205479 0.205479 95 / 185 Satz 3.17 Eine irreduzible und aperiodische MarkovKette mit endlichem Zustandsraum ist immer (positiv) rekurrent und der Grenzwert P ∞ = lim P n n→∞ ∞ existiert. Die Matrix P hat die Form π1 π2 . . . πn π1 π2 . . . πn P ∞ = .. .. .. .. . . . . π1 π2 . . . πn und π = (π1 , . . . , πn ) ist die einzige stationäre Verteilung der Markov-Kette. 96 / 185 Zusammenfassung: Ist die Markov-Kette Xn irreduzibel und aperiodisch, dann gibt es eine eindeutige stationäre Verteilung π (Lösung der Gleichung π(P − In ) = 0) und es gilt: I Startet die Kette mit der Anfangsverteilung π, so verbleibt sie bei dieser Verteilung, d.h. P(Xn = k ) = πk für jedes n. I Ansonsten gilt unabhängig vom Startwert lim P(Xn = k ) = πk , n→∞ d.h. die Markov-Kette befindet sich mit Wahrscheinlichkeit ≈ πk im Zustand k , wenn der Prozess schon sehr lange läuft (sog. steady state). 97 / 185 3.8. Mittelwerte im Gleichgewichtszustand Für eine gegebene Funktion f : E → R wäre es interessant den Mittelwert von f (Xn ) über einen sehr langen Zeitraum zu bestimmen, also n 1X f (Xk ) n k =0 für sehr großes n. Satz 3.18 (Starkes Gesetz der großen Zahlen) Für eine irreduzible, aperiodische, Markov-Kette mit Zustandsraum mit stationärer Verteilung π gilt fast sicher n n X 1X lim f (Xk ) = f (i)πi , n→∞ n k =0 i=1 für jede beschränkte Funktion auf dem Zustandsraum. 98 / 185 Beispiel 3.19 Eine Maschine befindet sich in einem der drei Zustände (A) „intakt”, (B) „defekt” und (C) „in Reparatur”. Sei Xn ∈ {A, B, C} der Zustand der Maschine nach n Tagen. Die Übergangswahrscheinlichkeiten seien wie folgt gegeben: 99 / 185 In den Verschiedenen Zuständen verursacht die Maschinen entweder Kosten oder es entstehen Einkünfte: A B C Gewinn (in Tsd. Euro) 2 -5 -10 Wie hoch ist der mittlere Gewinn pro Tag, wenn die Markov-Kette im Gleichgewicht ist? Die Markov-Kette ist irreduzibel und aperiodisch. Wir berechnen die Stationäre Verteilung. Es ist 0.95 0.05 0 0 1 P= 0 0.4 0 0.6 Dann ergibt sich −0.05 0 0.4 0 (P − In )T = 0.05 −1 0 1 −0.4 100 / 185 Wir müssen also das zugehörige LGS lösen: -0.05 0 0.4 0.05 -1 0 0 1 -0.4 1 0 -8 0 1 -0.4 0 0 0 Also ist π = c · (−8, −0.4, −1) und daher 1 5 =− . c= −8 − 0.4 − 1 47 Demnach ist die stationäre Verteilung der Markov-Kette gegeben durch π = (π1 , π2 , π3 ) mit π = ( 40 , 2 , 5 ). 47 47 47 101 / 185 Nun sei f : E → R eine Funktion mit Werten f (1) = 2, f (2) = −5, f (3) = −10. Dann ist der Mittelwert von f (X0 ), f (X1 ), . . . gegeben durch n X 40 2 5 f (i)πi = ·2− ·5− · 10 47 47 47 i=1 20 ≈ 0.426. 47 Der mittlere Gewinn pro Tag pro Maschine beträgt also 426 Euro. = 102 / 185 Beispiel 3.20 Eine Warteschlange eines Callcenters habe die Maximale Länge vier. Es sei Xn die Warteschlangenlänge nach n Minuten. Xn sei eine Markov-Kette mit Übergangsmatrix 0.9 0.1 0 0 0 0.2 0.7 0.1 0 0 P= 0 0.2 0.7 0.1 0 0 0 0.2 0.7 0.1 0 0 0 0.2 0.8 103 / 185 Um die Kunden(un)zufriedenheit zu messen, wird eine Straffunktion f : {0, 1, 2, 3, 4} eingeführt, die höher Ausfällt, wenn mehr Kunden warten müssen. Man definiert: f (k ) = k 2 . Wie groß ist die Strafe im Mittel über einen langen Zeitraum? Wir bestimmen zunächst die stationäre Verteilung. Es ist −0.1 0.2 0 0 0 0.1 −0.3 0.2 0 0 T 0.1 −0.3 0.2 0 (P − In ) = 0 0 0 0.1 −0.3 0.2 0 0 0 0.1 −0.2 Wir müssen lösen: (P − In )T = 0. 104 / 185 -0.1 0.1 0 0 0 -0.1 0 0 0 0 0.2 -0.3 0.1 0 0 0.2 -0.1 0 0 0 0 0.2 -0.3 0.1 0 0 0.2 -0.1 0 0 0 0 0.2 -0.3 0.1 0 0 0.2 -0.1 0 0 0 0 0.2 -0.2 0 0 0 0.2 0 ⇒ -0.1 0 0 0 0 1 0 0 0 0 0 -0.1 0 0 0 0 1 0 0 0 0 0 -0.1 0 0 0 0 1 0 0 0 0 0 -0.1 0 0 0 0 1 0 1.6 0.8 0.4 0.2 0 -16 -8 -4 -2 0 Also ist π = c · (−16, −8, −4, −2, −1), d.h. c = 31, 16 8 4 2 1 π= , , , , . 31 31 31 31 31 Dann ergibt sich n X 8 4 2 1 f (i)πi = +4 +9 + 16 ≈ 1.87097. 31 31 31 31 i=1 Die mittlere Strafe beträgt etwa 1.87. 105 / 185 3.9. Rückkehrzeiten Wie lange dauert im Mittel, bis die Markov-Kette nach einem Start in Zustand xi wieder im Zustand xi anlangt? Es sei τ (i) = min{k ≥ 1 : Xn = i}. Satz 3.21 Eine irreduzible und aperiodische MarkovKette mit endlichem Zustandsraum habe die stationäre Verteilung π = (π1 , . . . , πN ). Dann gilt 1 E[τ (i)|X0 = i] = . πi 106 / 185 4. Poisson-Prozesse 4.1. Erdbeben und Zählprozesse Eine Versicherung will Erdbebenschäden abschätzen und möchte dazu ein mathematisches Modell konstruieren. Ein Seismograph zeichnet über einen längeren Zeitraum Beben verschiedener Stärke auf. Es sollen nur Erdbeben betrachtet werden, die eine bestimmte Stärke überschreiten. 107 / 185 Die relevanten Erdbeben treten zu zufälligen Zeitpunkten auf, die wir mit den Zufallsvariablen T1 , T2 , . . . identifizieren: Wir setzen T0 = 0. (Tk )k =1,2,... ist ein stochastischer Prozess in diskreter Zeit. Die Zufallsvariablen Xk sind nicht-negativ. In dem vereinfachten Modell werden die Erdbebenstärken nicht weiter berücksichtigt. 108 / 185 Die Pausenzeiten, also die Länge der Zeitabschnitte zwischen den Erdbeben, bezeichnen wir mit X1 , X2 , . . .. Auch (Xk )k =1,2,... ist ein stochastische Prozess in diskreter Zeit mit nicht-negativen Zufallsvariablen Xk . Der Prozess (Tk ) ist durch den Prozess (Xk ) eindeutig festgelegt und umgekehrt. Es gilt Xn = Tn − Tn−1 und n X Tn = Xk , n = 1, 2, . . . k =1 109 / 185 Es sei N(t) die Anzahl der Erdbebenereignisse im Zeitintervall von 0 bis t, also N(t) = max{j ∈ N0 |Tj ≤ t}. Gilt z.B. T1 = 1.876, T2 = 1.901, T1 = 2.817 und T1 = 3.182 dann ist N(1.0) = 0, N(2.1) = 2, N(2.7) = 2, N(2.817) = 3, N(3.1) = 3. (N(t))t∈R+ ist ein stochastischer Prozess in stetiger Zeit. 110 / 185 N(t) hat folgende Eigenschaften: 1. N(t) hat Werte in Z+ = {0, 1, 2, 3, 4, . . .}, 2. N(0) = 0, 3. N(t) ist nicht-fallend und 4. der Zuwachs N(t) − N(s) entspricht der Anzahl der Erdbebenereignisse im Zeitintervall (s, t]. Ein stochastischer Prozess mit diesen vier Eigenschaften ist ein Zählprozess. Typische Verläufe für N(t): 111 / 185 Für das Erdbebenmodell nehmen wir noch zwei zusätzliche Eigenschaften an. (1) Die Zuwächse N(t + u) − N(t) und N(s + v ) − N(s) seien unabhängig, wenn (t, t + u] und (s, s + v ] sich nicht überschneiden. 112 / 185 (2) Die Zuwächse N(t + u) − N(t) und N(s + u) − N(s) besitzen die gleiche Verteilung, die nur von u und nicht von t uns s abhängt. Ein Zählprozess mit diesen Eigenschaften heißt Poisson-Prozess, wenn diese Verteilung der Zuwächse eine Poisson-Verteilung ist mit Mittelwert λ · u, für ein λ > 0. 113 / 185 4.2. Definition: Poisson-Prozess Definition 4.1 Ein (homogener) Poisson-Prozess mit Intensität λ > 0 ist ein Zählprozess (N(t))t∈R+ mit folgenden Eigenschaften: 1. (Unabhängige Zuwächse) N(t + u) − N(t) ist unabhängig von N(s + v ) − N(s) , 2. (Stationäre Zuwächse) N(t + u) − N(t) hat eine Poisson-Verteilung mit Parameter λu, d.h. es gilt (λu)n P(N(t + u) − N(t) = n) = e−λu , n ∈ N0 . n! Dabei sei 0 ≤ t < t + u ≤ s < s + v . 114 / 185 Weitere Eigenschaften: N(t) ist stückweise konstant, rechtsseitig stetig und hat Aufwärtssprünge der Größe 1, I N(t) = N(t) − N(0) hat eine Poisson-Verteilung: n −λt (λ · t) P(N(t) = n) = e , n! I E[N(t)] = λ · t, I Man kann zeigen, dass P(N(t) = 1) = λ · t + o(t), P(N(t) > 1) = o(t), wobei o(t) eine Funktion von t bezeichnet, für die o(t)/t → 0 gilt, wenn t gegen 0 konvergiert. Wenn t sehr klein ist, dann ist P(N(t) = 1) ≈ λ · t, P(N(t) > 1) ≈ 0. I 115 / 185 Drei Poisson-Prozesse mit λ = 2.0, t ∈ [0, 10] 116 / 185 4.3. Gedächtnislosigkeit der exponentiellen Verteilung Eine stetige Zufallsvariable X besitzt eine exponentielle Verteilung mit Rate λ, wenn FX (x) = P(X ≤ x) = 1 − e−λx ist. Für die zugehörige Dichtefunktion ergibt sich fX (x) = λe−λx . Es gilt E[X ] = 1 , λ Var[X ] = 1 . λ2 117 / 185 Exponentielle Zufallsvariablen besitzen ein besondere Eigenschaft, die Gedächtnislosigkeit: P(X > x + y |X > x) = P(X > y ). Beweis: ,X >x) P(X > x + y |X > x) = P(X >x+y P(X >x) = P(X >x+y ) P(X >x) −λ(x+y ) = e e−λx = e−λy . Keine andere stetige Zufallsvariable hat diese Eigenschaft. 118 / 185 4.4. Verteilung der Pausenzeiten Erinnerung: Xn = Tn − Tn−1 und Tn = Pn k =1 Xk . Da N(t) ein Zählprozess mit konstanter Rate ist, kann man annehmen, dass X1 , X2 , . . . i.i.d sind. P(X1 ≤ x) = P(N(x) > 0) = 1 − P(N(x) = 0) = 1 − e−λx . Satz 4.2 Die Pausenzeiten des Poisson-Prozesses mit Intensität λ haben eine exponentielle Verteilung mit Parameter λ. Insbesondere ist 1 E[X1 ] = E[X2 ] = . . . = . λ 119 / 185 4.5. Pausenzeiten und Ereigniszeitpunkte Erinnerung: Tn = n X Xk . k =1 Es folgt, dass die Verteilung von Tn der n-fachen Faltung der Exponentialverteilung entspricht: G1 (x) = P(T1 ≤ x) = F (x) = 1 − e−λx , Z x G2 (x) = P(T2 ≤ x) = F (x − y ) dG1 (y ) = F ∗ F (x), 0 G3 (x) = F ∗ F ∗ F (x), Gn (x) = |F ∗ F ∗{z· · · ∗ F}(x). n× ⇒ Gn ist schwierig zu berechnen. 120 / 185 Statt die Faltungsintegrale zu berechnen, kann man eine weitere Eigenschaft der Ereigniszeitpunkte ausnutzen. Es gilt: N(t) ≥ n ⇔ Tn ≤ t. Dann ist also P(Tn ≤ t) = P(N(t) ≥ n) n−1 X = 1− P(N(t) = k ) k =0 = 1−e −λt n−1 X (λt)k k =0 k! . 121 / 185 Satz 4.3 Der n-te Ereigniszeitpunkt Tn eines PoissonProzesses mit Intensität λ besitzt eine Erlang-Verteilung mit Parametern n und λ: n−1 X (λt)k P(Tn ≤ t) = 1 − e−λt . k! k =0 Z.B. ist P(T1 ≤ t) = 1 − e−λt P(T2 ≤ t) = 1 − e−λt (1 + λt) (λt)2 ) 2 (λt)2 (λt)3 −λt + ). P(T4 ≤ t) = 1 − e (1 + λt + 2 6 P(T3 ≤ t) = 1 − e−λt (1 + λt − 122 / 185 Beispiel 4.4 Die Kundenankünfte an einem Schalter einer Bank werden durch einen Poisson-Prozess modelliert. Die mittlere Anzahl der Ankünfte beträgt 2 Kunden in der Minute. Wie groß ist die Wahrscheinlichkeit, dass in 5 Minuten weniger als 4 Kunden die Bank besuchen? Es ist λ = 2. Es ergibt sich 102 103 P(N(5) ≤ 3) = e−10 (1 + 10 + + ) ≈ 0.010 2 6 Alternativ P(T4 > 5) = 1 − P(T4 ≤ 5) = e−10 (1 + 10 + 102 103 + ) ≈ 0.010. 2 6 123 / 185 4.6. Normalapproximation Häufig ist es sehr mühsam die Verteilungsfunktion von N(t) und Tk auszurechnen, wenn t oder k sehr groß sind. Beispiel 4.5 Bei einer Maschine treten Defekte zufällig, aber mit einer konstanten Rate von einem Defekt in 10 Tagen auf. Wie groß ist die Wahrscheinlichkeit, dass in einem Jahr mehr als 40 Defekte eintreten? Es ist λ = 1/10 (Zeiteinheit=Tage). Wir suchen P(N365 > 40) also 40 1 X ( 10 365)k 1 − 10 365 P(N365 > 40) = 1 − e k! k =0 =??? 124 / 185 Ist t sehr groß, so ist N(t) ≈ λt: Poisson-Prozess mit λ = 3 und die Gerade t 7→ 3t. 125 / 185 Abstand N(t) zu λt: N(t) − λt für λ = 3 126 / 185 Es ist Tn = n X Xk . k =1 Nach dem zentralen Grenzwertsatz ist also x − nµ P(Tn ≤ x) ≈ Φ( √ ) σ n t − n/λ = Φ( √ ) n/λ λt − n = Φ( √ ). n Satz 4.6 Für die Eintrittszeiten der Ereignisse eines homogenen Poissonprozesses mit Intensität λ gilt λt − n P(Tn ≤ t) = P(N(t) ≥ n) ≈ Φ √ , n wenn n entsprechend groß ist. 127 / 185 Beispiel 4.7 Bei einer Maschine treten Defekte mit einer konstanten Rate 0.1 Defekte/Tag auf. Wie groß ist die Ws., dass in einem Jahr mehr als 40 Defekte eintreten? Wir suchten P(N365 > 40) also 39 1 X ( 10 365)k 1 − 10 365 P(N365 > 40) = 1 − e k! k =0 36.5 − 40 ≈ Φ( √ ) = Φ(−0.55) ≈ 0.2912. 40 Wahrer Wert: ≈ 0.3025. 128 / 185 4.7. Exkurs: Ordnungsstatistik der Gleichverteilung Eine Zufallsvariable besitzt eine Gleichverteilung auf dem Intervall [0, t], wenn ( x ; x ∈ [0, t] P(X ≤ x) = t 0 ; sonst gilt. Wir betrachten n gleichverteilte unabhängige Zufallsvariablen X1 , . . . , Xn auf dem Intervall [0, t]. Als Ordnungsstatistik von X1 , . . . , Xn bezeichnet man die geordnete Menge X(1) < X(2) < . . . < X(n) der aufsteigend sortierten Zufallsvariablen X1 , . . . , Xn . Speziell ist dann X(1) = min Xi , i=1,2,...,n X(n) = max Xi . i=1,2,...,n 129 / 185 Die gemeinsame Dichtefunktion der Ordnungsstatistik X(1) , X(2) , . . . , X(n) von auf [0, t] gleichverteilten unabhängigen Zufallsvariablen ist gegeben durch ( n!/t n ; 0 ≤ t1 ≤ t2 ≤ . . . ≤ tn ≤ t f (t1 , t2 , . . . , tn ) = 0 ; sonst. Beispiel: E[X(1) X(n) ] = = = = Z Z Z t2 n! t tn ··· t1 tn dt1 dt2 . . . dtn−1 dtn tn 0 0 0 Z Z tn Z t3 2 n! t t2 t · · · dt2 . . . dtn−1 dtn n tn 0 0 0 2 Z Z n! t tnn 1 t n+1 dtn tn dtn = n t t n 0 n! t 0 n t2 . n+2 130 / 185 4.8. Ereigniszeitpunkte bei fester Ereigniszahl Angenommen, es ist für einen Zeitpunkt t > 0 schon bekannt, dass N(t) = n ist. Wie lautet die Verteilung der Ereigniszeitpunkte T1 , T2 , . . . , Tn ? Satz 4.8 Die gemeinsame Verteilung von T1 , T2 , . . . , Tn , gegeben N(t) = n, ist gleich der Verteilung der Ordnungsstatistik von n unabhängigen auf [0, t] gleichverteilten Zufallsvariablen. Gegeben N(t) = n, liegen also die Ereigniszeiten T1 , T2 , . . . , Tn in einem gewissen Sinne „maximal zufällig” im Zeitintervall [0, t]. 131 / 185 Man kann also die Ankünfte eines Poisson-Prozesses bis zum Zeitpunkt t simulieren, indem man entweder I Exponentielle Zufallsvariablen X1 , X2 , X3 , . . . mit Mittelwert P 1/λ erzeugt, solange bis Tn = ni=1 Xi ≥ t ist, oder I zunächst N(t) simuliert (dazu muss die Poissonverteilung implementiert sein) und dann N(t) gleichverteilte Variablen in [0, t] simuliert. 132 / 185 Beispiel 4.9 Es sei N(t) = 2. Wie lautet die Verteilung von T1 ? Z Z 2 t u P(s ≤ x) ds du P(T1 ≤ x) = 2 t 0 0 Z Z 2 t min{u,x} ds du = 2 t 0 0 Z Z 2 x t du ds = 2 t 0 s Z 2 x = 2 (t − s) ds t 0 2 1 = 2 (tx − x 2 ) t 2 2 2tx − x . = t2 133 / 185 4.9. Vorwärts- und Rückwärtsrekurrenzzeit Seien nun t∗ = TN(t) , t ∗ = TN(t)+1 die Eintrittszeiten des vorhergehenden bzw. folgenden Ereignisses nach dem Zeitpunkt t, Wir wollen die Verteilung der Zufallsvariablen A(t) = t − t∗ (Rückwärtsrekurrenzzeit) ∗ B(t) = t − t (Vorwärtsrekurrenzzeit) finden. Die Verteilung von B(t) ist offenbar exponentiell (Gedächtnislosigkeit der Exponentialverteilung): P(B(t) ≤ s) = 1 − e−λs . 134 / 185 Die Verteilung von A(t) is etwas schwieriger zu finden. Es ist für 0 ≤ s ≤ t ∞ X P(A(t) > s) = P(t∗ ≤ t − s|N(t) = n) · P(N(t) = n) n=0 = ∞ X P(max{U1 , U2 , . . . , Un } ≤ t − s) · e−λn n=0 (λt)n , n! wobei die Uk i.i.d. gleichverteilte ZV in [0, t] sind. ∞ X (λt)n = P(U1 ≤ t − s, . . . , Un ≤ t − s) · e−λn n! = n=0 ∞ X n P(U1 ≤ t − s) · e n=0 = e−λt eλs ∞ X t − s n −λt (λt)n = ·e n! t n! −λn (λt) n n=0 ∞ X n=0 e−λ(t−s) n (λ(t − s)) = e−λs . n! 135 / 185 Satz 4.10 Für die Rückwärtsrekurrenzzeit gilt ( 1 − e−λs ; s ∈ [0, t] P(A(t) ≤ s) = 1 ; sonst und E[A(t)] = λ1 (1 − e−λt ). Für die Vorwärtsrekurrenzzeit gilt P(B(t) ≤ s) = 1 − e−λs , s ∈ [0, ∞) und E[B(t)] = λ1 . A(t) und B(t) sind unabhängig. Wartezeitenparadoxon: Es ist für t > 0 2 e−λt 1 E[A(t) + B(t)] = − > . λ λ λ 136 / 185 Beispiel 4.11 Eine Bushaltestelle fahren im Mittel 6 Busse pro Stunde an. In einem mathematischen Modell werden die ankommenden Busse als Ereignisse eines Poisson-Prozesses modelliert. Der erste Bus erreicht die Haltestelle morgens exakt um 7 Uhr. Wie groß ist die Wahrscheinlichkeit einen Bus innerhalb von 10 Minuten anzutreffen, wenn man um 13 Uhr die Bushaltestelle erreicht? 1 1 P(B(6) ≤ ) = 1 − e−6· 6 ≈ 0.632. 6 Wie groß ist die Wahrscheinlichkeit dass der letzte Bus vor weniger als 10 Minuten fuhr? 1 1 P(A(6) ≤ ) = 1 − e−6· 6 ≈ 0.632. 6 137 / 185 4.10. Zusammenführung von Poisson-Prozessen N(t) und M(t) seien zwei unabhängige Poisson-Prozesse mit Intensitäten λ und µ. Es sei K (t) der Zählprozess, der die Ereignisse von N(t) und M(t) zählt, d.h. K (t) = N(t) + M(t). Ist dann K (t) auch ein Poisson-Prozess? I Offenbar hat K (t) auch unabhängige und stationäre Zuwächse. I Hat K (t) eine Poisson-Verteilung? 138 / 185 Es ist P(K (t) = k ) = k X P(N(t) = n, M(t) = k − n) n=0 = k X P(N(t) = n)P(M(t) = k − n) n=0 = k X e−λt n=0 (λt)n −µt (µt)k −n e n! (k − n)! k = e −(λ+µ)t 1 X k! (λt)n (µt)k −n k! n!(k − n)! n=0 139 / 185 Binomische Formel: k (a + b) = k X n=0 k! an bk −n . n!(n − k )! Also ist k P(K (t) = k ) = e −(λ+µ)t k! 1 X (λt)n (µt)k −n k! n!(k − n)! n=0 1 (λt + µt)k . k! ((µ + λ)t)k . = e−(λ+µ)t k! = e−(λ+µ)t Satz 4.12 Der zusammengeführte Zählprozess K (t) = N(t)+M(t) ist wieder ein Poisson-Prozess mit Intensität λ + µ. 140 / 185 Beispiel 4.13 An zwei Schaltern einer Bank werden die Kundenankünfte durch zwei Poisson-Prozesse N(t) und M(t) modelliert. Am ersten Schalter kommen 10 Kunden pro Stunde an, an dem zweiten Schalter ist die Rate doppelt so hoch. Der Zählprozess K (t), der die Ankünfte für beide Schalter zählt, ist dann ein Poisson-Prozess mit Intensität λ = 10 + 20 = 30. Im Mittel betritt also alle 2 Minuten ein Kunde die Bank. 141 / 185 4.11. Ausdünnung von Poisson-Prozessen Wir wollen jetzt aus einem Poisson-Prozess K (t) mit Intensität λ + µ zwei Poisson-Prozesse gewinnen, und zwar I einen Prozess N(t) mit Intensität λ und I einen Prozess M(t) mit Intensität µ. 142 / 185 Idee: Wir werfen bei jedem Ereignis des Prozesses K eine unfaire Münze: I mit Wahrscheinlichkeit p = λ/(λ + µ) ordnen wir das Ereignis dem Prozess N zu, I mit Wahrscheinlichkeit 1 − p = µ/(λ + µ) ordnen wir das Ereignis dem Prozess M zu. Satz 4.14 Die beiden so konstruierten Zählprozesse N(t) und M(t) sind unabhängige Poisson-Prozesse mit Intensitäten λ und µ. Mit anderen Worten: werden bei einem Poisson-Prozess mit Intensität κ die Ereignisse mit Wahrscheinlichkeit p einem Prozess N und mit Wahrscheinlichkeit 1 − p einem Prozess M zugeordnet, dann sind N und M unabhängige Poisson-Prozesse mit Intensitäten λ = pκ und µ = (1−p)κ. 143 / 185 Beispiel 4.15 Ein Seismograph zeichnet Erdbeben verschiedener Stärke auf. Die Verteilungsfunktion der Erdbebenstärke S sei s2 , P(S ≤ s) = 1 + s2 Es ist also P(S > 3) = 0.1, P(S > 5) = 0.038, P(S > 5|S > 3) = 0.38. 144 / 185 Die Erdbeben der Stärke >3 werden als Poisson-Prozess modelliert. Empirisch ergab sich eine Rate von κ = 2.4 Erdbeben dieser Stärke pro Tag. Dann ist der Prozess, der die Erbeben der Stärke >5 zählt ebenfalls ein Poisson-Prozess. Seine Intensität ist λ = P(S > 5|S > 3)κ = 0.38 · 2.4 = 0.91. 145 / 185 4.12. Inhomogene Poisson-Prozesse Ein inhomogener Poisson-Prozess N(t) mit Intensitätsfunktion λ(t) liegt vor, wenn I N(t) ein Zählprozess ist, I N(t) unabhängige Zuwächse besitzt I und für t > s die Zuwächse N(t) − N(s) eine Poisson-Verteilung mit Parameter Λ(t) − Λ(s) besitzen. Rt Dabei sei Λ(t) = 0 λ(u) du. Es gilt also (Λ(t) − Λ(s))n P(N(t) − N(s) = n) = eΛ(s)−Λ(t) . n! Die Zuwächse sind nicht mehr stationär. Spezialfall: für λ(t) = λ ergibt sich der homogene Poisson-Prozess. 146 / 185 Beispiel 4.16 Das Auftreten von Erdbeben werde mit einem inhomogenen Poisson-Prozess modelliert. Dabei geht man davon aus, dass die Instensität mit der Zeit abnimmt: 1 λ(t) = . 1+t 147 / 185 Dann ist Λ(t) = Rt 1 0 1+u du = ln(1 + t) und daher (ln(1 + t) − ln(1 + s))n n! 1+t n 1 + s (ln( 1+s )) = . 1+t n! P(N(t) − N(s) = n) = eln(1+s)−ln(1+t) Speziell gilt also 1 (ln(1 + t))n . P(N(t) = n) = 1+t n! 148 / 185 In einem sehr kurzen Zeitintervall [t, t + h] ist die erwartete Anzahl von Ereignissen gegeben durch E[N(t + h) − N(t)] ≈ λ(t) · h + o(h). Dann ist d E[N(t)] = λ(t) dt und damit Satz 4.17 Für den inhomogenen Poisson-Prozess ergibt sich die erwartete Anzahl von Ereignissen als Z t E[N(t)] = λ(u) du = Λ(t). 0 149 / 185 Beispiel 4.18 Es sei N(t) die Anzahl der Anfragen von Internetnutzern an einem Server. Die Intensität (Ankünfte/Zeit) sei abhängig von der Tageszeit und den Wochentagen. In der Woche gibt es mehr Anfragen als am Wochenende, nachts ist die Intensität geringer: λ(t) = 3 + 2 cos(2πt) − cos(2πt/7) 150 / 185 Es ist E[N(t)] = Λ(t) = 3t + 1 7 sin(2πt) − sin(2πt/7) π 2π 151 / 185 4.13. Zusammengesetzte Poisson-Prozesse, Waldsche Gleichung Manchmal ist es sinnvoll zu jedem Ereigniszeitpunkt Tn eines Poisson-Prozesses (homogen oder inhomogen) jeweils auch eine zufällige Größe Zn zu betrachten, die unabhängig vom Poisson-Prozess ist Zn kann z.B. ein Gewinn, eine Strafe, die Erdbebenstärke (oder freigewordene Energie) oder die Schadenshöhe sein. Wir gehen davon aus dass die Zufallsvariablen Z1 , Z2 , . . . unabhängig von X1 , X2 , . . . und identisch verteilt sind (man könnte die Bedingungen noch allgemeiner fassen). Interessant: N(t) X S(t) = Zk k =1 152 / 185 Wenn N(t) = N eine feste (deterministische) Größe wäre, ergäbe sich für den Erwartungswert von S(t) N X E[S(t)] = E[ Zk ] = E[Z1 ] · N. k =1 Gilt eine ähnliche Gleichung auch für unseren Fall? Satz 4.19 (Waldsche Gleichung) Es gilt für einen inhomogenen zusammengesetzten Poisson-Prozess E[S(t)] = E[Z1 ]E[N(t)] = E[Z1 ]Λ(t) d.h., dass der Erwartungswert von S(t) proportional zu E[N(t)] ist. 153 / 185 Beispiel 4.20 Eine Versicherung rechnet mit einer zeitlich wachsenden Zahl von Schäden der zufälligen Höhe Z1 , Z2 , . . .. Ein entsprechendes Modell sieht einen inhomogenen Poisson-Prozess mit Intensitätsfunktion 1 λ(t) = 1 − 1+t vor. Also ergibt sich Λ(t) = t − ln(1 + t). 154 / 185 Die Schadenshöhen Zn besitzen die Verteilungsfunktion ;z < 0 0 (15−3z)z 3 F (z) = P(Zn ≤ z) = ;0 ≤ z < 4 256 1 ;4 ≤ z besitzen. Dann ist die Dichtefunktion gegeben durch ( 0 ; z 6∈ [0, 4] f (z) = 3 2 z (4 − z) ; z ∈ [0, 4] 64 155 / 185 Für den Erwartungswert berechnen wir Z 4 3 E[Zn ] = z z 2 (4 − z) dz 64 0 Z 4 3 = 4z 3 − z 4 dz 64 0 3 4 1 5 4 12 = [z − z ]0 = = 2.4 64 5 5 Für den Erwartungswert der Gesamtsumme S(t) = der Schäden ergibt sich dann E[S(t)] = E[Zn ]Λ(t) = 2.4(t − ln(t)). PN(t) k =1 Zk 156 / 185 5. Brownsche Bewegung 5.1. Noch einmal Irrfahrten Es sei Sn eine symmetrische einfache Irrfahrt: n X 1 Sn = Xk , P(Xk = −1) = P(Xk = 1) = . 2 k =1 Wir betrachten den stochastischen Prozess S[nt] 157 / 185 158 / 185 Es ist E[S[nt] ] = 0 und Var[S[nt] ] = [nt] · Var[X1 ] ≈ nt. Für n → ∞ konvergiert die Verteilung von S[nt] nicht gegen eine interessante Verteilung. Daher betrachten wir S[nt] Bn (t) = √ n Dann ist E[Bn (t)] = 0 und Var[Bn (t)] ≈ t. 159 / 185 n=5000 n=50000 160 / 185 Für n → ∞ konvergiert nach dem zentralen Grenzwertsatz die Verteilung von Bn (t) gegen eine Normalverteilung mit Varianz t: √ P(Bn (t) ≤ x) → Φ(x/ t). Der ’Grenzprozess’ B(t) = limb→∞ Bn (t) hat folgende Eigenschaften: 1. B(0) = 0 fast sicher (also P(B(0) = 0) = 1), 2. B(t) is normalverteilt mit Erwartungswert 0 und Varianz t. 3. B(t) hat unabhängige Zuwächse: B(t2 ) − B(t1 ) und B(s2 ) − B(s1 ) sind unabhängig, wenn s1 ≥ t2 ist. 4. B(t) hat stationäre Zuwächse. B(t2 ) − B(t1 ) hat dieselbe Verteilung wie B(s2 ) − B(s1 ), wenn t2 − t1 = s2 = s1 ist. Definition 5.1 Ein Prozess mit solchen Eigenschaften heißt Brownsche Bewegung 161 / 185 Simulation von 5 Brownschen Bewegungen 162 / 185 5.2. Eigenschaften der Brownschen Bewegung Weitere Eigenschaften: B(t) ist fast sicher stetig, I B(t) ist fast sicher nirgendwo differenzierbar. Es gilt B(t + h) − B(t) Var[B(h)] 1 Var[ ]= = . 2 h h h I I I I B(t) − B(s) ist Normalverteilt mit Erwartungswert 0 und Varianz t − s, B(t) ist ein Markov-Prozess: Für t, h > 0 gilt P(B(t + h) ∈ A|B(s), s ∈ [0, t]) = P(B(t + h) ∈ A|B(t)). Übergangswahrscheinlichkeit für t > s: P(B(t) ≤ x|B(s) = y ) = P(B(t − s) ≤ x − y ) x −y = Φ( √ ). t −s 163 / 185 Die Kovarianzfunktion Cov[B(t), B(s)] ist für t > s gegeben durch Cov[B(t), B(s)] = E[B(t)B(s)] − E[B(t)]E[B(s)] = E[B(t)B(s)] = E[(B(t) − B(s))B(s)] + E[B(s)2 ] = E[(B(t) − B(s))]E[B(s)] + Var[B(t)] = s. Dann ist allgemein Cov[B(t), B(s)] = min{s, t}. 164 / 185 5.3. Treffzeit, einseitig Wir definieren die Treffzeit T (a) = inf{t > 0|B(t) = a}. 165 / 185 Wir interessieren uns für die stochastischen Eigenschaften von T (a): Wie lautet die Verteilung, der Erwartungswert, die Varianz von T (a) in Abhängigkeit von a? Es gilt für a ≥ 0: P(B(t) ≥ a) = P(B(t) ≥ a|T (a) ≤ t)P(T (a) ≤ t) +P(B(t) ≥ a|T (a) > t)P(T (a) > t) = P(B(t) ≥ a|T (a) ≤ t)P(T (a) ≤ t) = P(B(t − T (a)) ≥ 0)P(T (a) ≤ t) 1 = P(T (a) ≤ t). 2 Satz 5.2 Es gilt für die Verteilung der Treffzeit T (a): √ P(T (a) ≤ t) = 2(1 − Φ(|a| / t)), t > 0. (Inverse Gaussverteilung) 166 / 185 Damit gilt also Z ∞ u2 2 e− 2 du P(T (a) ≤ t) = √ √ 2 |a|/ t r Z 2 ∞ − u2 e 2t du, t > 0. = t |a| Die zugehörige Wahrscheinlichkeitsdichte ist dann a2 d |a| e− 2t . P(T (a) ≤ t) = √ dt 2πt 3/2 Daraus ergibt sich: E[T (a)2 ] = ∞, Var[T (a)2 ] = ∞, E[T (a)] = ∞. 167 / 185 5.4. Maximumprozess Sei jetzt M(t) = sup{B(s), s ∈ [0, t]}. 168 / 185 Es gilt M(t) ≥ a ⇔ T (a) ≤ t also P(M(t) ≥ a) = P(T (a) ≤ t) √ = 2(1 − Φ(|a| / t)). Satz 5.3 Für den Maximumprozess M(t) gilt √ P(M(t) ≤ a) = 2Φ(|a| / t) − 1. 169 / 185 5.5. Treffzeit, beidseitig Sei nun T (a, b) = inf{t > 0|B(t) = −a oder B(t) = b}. 170 / 185 Man kann (mit sog. Martingalen) zeigen, dass E[B(T (a, b))] = 0 E[B(T (a, b))2 ] = E[T (a, b)] gelten. Dann ergibt sich 0 = E[B(T (a, b))] = E[B(T (a, b))|B(T (a, b)) = −a] · P(B(T (a, b)) = −a) +E[B(T (a, b))|B(T (a, b)) = b] · P(B(T (a, b)) = b) = −a · P(B(T (a, b)) = −a) + b · (1 − P(B(T (a, b)) = −a). Also ist a · P(B(T (a, b)) = −a) = b − bP(B(T (a, b)) = −a) und demnach b a P(B(T (a, b)) = −a) = , P(B(T (a, b)) = b) = . a+b a+b 171 / 185 Außerdem ist E[T (a, b)] = E[B(T (a, b))2 |B(T (a, b)) = −a] · P(B(T (a, b)) = −a) +E[B(T (a, b))2 |B(T (a, b)) = b] · P(B(T (a, b)) = b) b a = a2 · + b2 · a+b a+b = a · b. Satz 5.4 Für die Brownsche Bewegung gilt a b P(B(T (a, b)) = −a) = , P(B(T (a, b)) = b) = a+b a+b und E[T (a, b)] = a · b. 172 / 185 5.6. Verhalten der Pfade für wachsendes t Wir wissen schon: B(t) erreicht fast sicher irgendwann jeden Wert a ∈ R (P(T (a) < ∞) = 1). Daraus folgt (fast sicher): lim sup B(s) = ∞, lim inf B(s) = −∞ t→∞ s≤t t→∞ s≤t Weil B(t) stetig ist folgt insbesondere, dass für jedes T > 0, B(t) unendlich viele Nullstellen hat für t > T . 173 / 185 5.7. Weitere Konstruktionen Folgende stochastischen Prozesse sind auch Brownsche Bewegungen: 1. A(t) = B(s + t) − B(s) (das ist klar), 2. C(t) = aB(t/a2 ) mit a 6= 0 (z.B. B(−t)), 3. D(t) = tB(1/t) (mit D(0) = 0). Insbesondere ergibt sich, dass für jedes ε > 0, die Brownsche Bewegung D(t) = tB(1/t) unendlich viele Nullstellen hat für 0 < t < ε. 174 / 185 5.8. Die Brownsche Brücke Die Brownsche Brücke R(t) kann man durch R(t) = B(t) − tB(1) definieren. Eigenschaften: 1. R(0) = R(1) = 0, 2. R(t) ist fast sicher stetig, 3. R(t) hat eine Normalverteilung mit E[R(t)] = 0 und Var[R(t)] = t(1 − t). 175 / 185 6. Die geometrische Brownsche Bewegung 6.1. Definition Für die Modellierung von Aktienkursen ist B(t) nicht sehr geeignet, weil B(t) auch negative Werte annimmt (sogar irgendwann fast sicher). Auß erdem sind die relativen Zuwächse B(t2 )/B(t1 ) weder unabhängig noch stationär. Stattdessen könnte man eB(t) betrachten: Definition 6.1 Der Prozess σ2 S(t) = S(0) · e(µ− 2 )t+σB(t) heißt geometrische Brownsche Bewegung (GBB). Dabei treten zwei Parameter auf: µ ∈ R (die Drift) und σ > 0 (die Volatilität). 176 / 185 GBB mit µ ∈ {−1.5, −1, −0.5, 0, 0.5, 1, 2} und σ = 1.0 GBB mit µ = 0.8 und σ ∈ {0, 0.25, 0.5, 0.75, 1.0} 177 / 185 6.2. Eigenschaften Es ist E[S(t)] = S0 eµt und 2 Var[S(t)] = S02 e2µt eσ t − 1 . Die Verteilungsfunktion (Lognormalverteilung) läßt sich wie folgt berechnen: P(S(t) ≤ x) = P(S(0) · e(µ− σ2 )t+σB(t) 2 ≤ x) log(x/S0 ) − (µ − = P(B(t) ≤ σ log(x/S ) − (µ − σ2 )t 0 2 √ = Φ . σ t σ2 )t 2 ) 178 / 185 Relativer Zuwachs (Anlagenrendite): σ2 2 S(t2 ) S(0) · e(µ− 2 )t2 +σB(t2 ) (µ− σ2 )(t2 −t1 )+σ(B(t2 )−B(t1 )) = = e . σ2 S(t1 ) S(0) · e(µ− 2 )t1 +σB(t1 ) Unabhängige relative Zuwächse: S(t2 )/S(t1 ) und S(s2 )/S(s1 ) sind unabhängig, wenn [t1 , t2 ] und [s1 , s2 ] disjunkt sind. Stationäre relative Zuwächse: S(t + h)/S(t) und S(s + h)/S(s) besitzen die gleiche Verteilung. Es gilt log(x) − (µ − σ2 )(t − t ) S(t2 ) 2 1 2 √ ≤ x) = Φ . P( S(t1 ) σ t2 − t1 179 / 185 Beispiel 6.2 Ein Aktienkurs werde durch eine GBB modelliert. Dabei sei µ = 0.1 und σ = 0.3. Es sei S0 = 6.0 der Kurs zu Anfang des Jahres. Wie groß ist die Wahrscheinlichkeit, dass die Rendite nach einem Jahr größer als 10% ist? 180 / 185 Es ergibt sich S(1) S(1) P( > 1.1) = 1 − P( ≤ 1.1) S(0) S(0) log(1.1) − (µ − σ2 ) 2 = 1−Φ σ = 1 − Φ(0.14531) = Φ(−0.14531) ≈ 0.4443. Die Wahrscheinlichkeit beträgt etwa 44 Prozent. Der Mittelwert für die Rendite beträgt E[S(1)/S(0)] = E[S(1)]/S(0) = e0.1 = 1.10517, also etwa 10.5 %. 181 / 185 6.3. Optionspreise Es beschreibe S(t) den Kurs einer Aktie. Eine europäische Verkaufsoption auf eine Aktie erlaubt zu einem festen Zeitpunkt T (Fälligkeit) den Verkauf zu einem Preis K (Ausübungspreis). Der Verkauf ist optional. Ausgezahlt wird also zum Zeitpunkt T : (K − S(t))+ = max{K − S(T ), 0} Preis C der Option: C = e−rT E[max{K − S(T ), 0}], wo r der Zins (Kalkulationszins) ist. 182 / 185 Den Optionsreis C = e−cT E[max{K − S(T ), 0}] kann man ausrechnen, da die Verteilung von S(T ) ja bekannt ist: Z K −rT (K − s) dFS(T ) (s) = . . . C=e −∞ (Rechnung ist etwas komplizierter) Es ergibt sich dann die berühmte Satz 6.3 (Black-Scholes-Formel) (r + σ2 )T − log(K /S ) 0 2 √ C = S0 · Φ σ T (r + σ2 )T − log(K /S ) √ 0 2 √ − Ke−rT Φ −σ T . σ T 183 / 185 Beispiel 6.4 Es sei ein Aktienkurs S(t) gegeben mit S0 = 45, µ = 0.3 und σ = 0.5. Es sei T = 2.0, K = 80 und r = 1.1. Hier ist S(2.0) = 106 und damit max{0, K − S(t)} = 26 184 / 185 Dann ergibt sich ein Optionspreis von (r + σ2 )T − log(K /S ) 0 2 √ C = S0 · Φ σ T (r + σ2 )T − log(K /S ) √ 0 2 √ −Ke−rT Φ −σ T σ T = 45 · Φ − 0.177292 − 65.4985 · Φ − 0.884 = 7.004 185 / 185
© Copyright 2024 ExpyDoc