Beispiele

1. Wettervorhersage
   (vgl. O. Häggström (2002) Finite Markov Chains and Algorithmic Applications. CU Press, Cambridge)
   • Wir betrachten zunächst Regionen, in denen sich typischerweise längere Regen- bzw. Trockenperioden abwechseln, wobei Regentage bzw. Sonnentage im Mittel etwa gleich oft vorkommen.
     • Dann ist es relativ einfach, das Wetter des folgenden Tages vorherzusagen, falls dabei nur die beiden ,,Zustände'' $1=$ ,,Regen'' bzw. $2=$ ,,Sonnenschein'' betrachtet werden.
     • Wenn wir annehmen, dass die Prognose in 75% aller Fälle richtig ist (und zwar unabhängig davon, ob es zum gegenwärtigen Tag regnet oder die Sonne scheint),
     • dann kann die Wettervorhersage durch eine Markov-Kette mit der folgenden Übergangsmatrix modelliert werden:

       $${\mathbf{P}}=\left(\begin{array}{ll} 0.75 & 0.25\\ 0.25 & 0.75\end{array}\right)\,.$$ (7)

       
       

   • In Regionen, in denen diese Symmetrie zwischen ,,Regen'' bzw. ,,Sonnenschein'' nicht vorliegt, sondern Sonnentage wesentlich öfter als Regentage vorkommen, sollte
     • die Wettervorhersage nicht durch die in (7) betrachtete Übergangsmatrix modelliert werden.
     • In diesem Fall könnte beispielsweise die Übergangsmatrix

       $${\mathbf{P}}=\left(\begin{array}{ll} 0.5 & 0.5\\ 0.1 & 0.9\end{array}\right)$$ (8)

       
       
       ein geeignetes Modell sein.

   
   

2. Zufällige Irrfahrten; Risikoprozesse 
   • Klassische Beispiele für Markov-Ketten sind durch sogenannte zufällige Irrfahrten gegeben, die auch in der deutschsprachigen Literatur Random Walk genannt werden, wobei das (unbeschränkte) Basismodell auf die folgende Weise gegeben ist.
     • Sei $Z,Z_1,Z_2,\ldots:\Omega\to\mathbb{Z}$ eine Folge von unabhängigen und identisch verteilten Zufallsvariablen, die nur Werte in der Menge $\mathbb{Z}=\{\ldots,-1, 0,1,\ldots\}$ der ganzen Zahlen annehmen.
     • Sei $X_0:\Omega\to\mathbb{Z}$ eine beliebige Zufallsvariable, die von den ,,Zuwächsen'' $Z_1,Z_2,\ldots$ unabhängig ist, und sei

       $$X_n=X_{n-1}+Z_n\,,\qquad\forall\,n\ge 1\,.$$ (9)

       
       

     • Dann bilden die Zufallsvariablen $X_0,X_1,\ldots$ eine Markov-Kette mit dem (abzählbar unendlichen) Zustandsraum $E=\mathbb{Z}$, mit der Anfangsverteilung ${\boldsymbol{\alpha}}=(\alpha_1,\alpha_2,\ldots)^\top$, wobei $\alpha_i=P(X_0=i)$, und mit den Übergangswahrscheinlichkeiten $p_{ij}=P(Z=j-i)$.

     
     

   • Beachte
     • Durch die in (9) gegebene Markov-Kette kann die Risikoreserve von versicherungs- bzw. finanztechnischen Bilanzierungprozessen modelliert werden, wobei $X_0$ als (zufällige) Anfangsreserve aufgefasst wird und der ,,Zuwachs'' $Z_n$ beispielsweise die Differenz $Z_n=a-Z_n^\prime$ aus risikofreien Einnahmen $a>0$ und zufallsbedingten Ausgaben/Verlusten $Z_n^\prime$ sein kann.
     • Ein anderer Spezialfall ist das bereits in Abschnitt WR-1.3 betrachtete Beispiel des zufälligen Gesamtgewinns $X_n$ aus $n$ Roulette-Spielen, bei dem $X_0=0$ angenommen wird und
     • die Verteilung des zufälligen ,,Zuwachses'' $Z$ für jedes einzelne Spiel durch $P(Z=i)=1/2$ für $i=-1,1$ und $P(Z=i)=0$ für $i\in\mathbb{Z}\setminus\{-1,1\}$ gegeben ist.

3. Warteschlangen
   • Die Anzahl der Kunden, die vor einer beliebigen, jedoch fest vorgegebenen Kasse eines Supermarktes warten, lässt sich wie folgt durch eine Markov-Kette modellieren.
     • Sei $X_0=0$ die Anzahl der Kunden, die bei Öffnung des Supermarktes vor der Kasse warten.
     • Mit $Z_n$ bezeichnen wir die zufällige Anzahl derjenigen Kunden, die sich vor der Kasse anstellen, während der $n$-te Kunde bedient wird; $n=1,2,\ldots$.
     • Dabei setzen wir voraus, dass die Zufallsvariablen $Z,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots\}$ unabhängig und identisch verteilt sind.
   • Die rekursiv definierte Folge $X_0,X_1,\ldots\Omega\to\{0,1,\ldots\}$ von Zufallsvariablen mit

     $$X_n= \max\{0,X_{n-1}+Z_n-1\}\,,\qquad\forall\,n\ge 1\,,$$ (10)

     
     
     bildet dann eine Markov-Kette, deren Übergangsmatrix ${\mathbf{P}}=(p_{ij})$ gegeben ist durch
     $$p_{ij}=\left\{\begin{array}{ll} P(Z=j+1-i)\,, &\mbox{falls $j+1\g... ...0)+P(Z=1)\,, &\mbox{falls $j=i=0$,}\\ 0\,, &\mbox{sonst.} \end{array}\right.$$

   • Dabei ist $X_n$ die zufällige Anzahl von Kunden in der Warteschlange, unmittelbar nachdem die Bedienung des $n$-ten Kunden beendet wurde (d.h. ohne die Berücksichtigung desjenigen Kunden, mit dessen Bedienung gegebenenfalls gerade begonnen wurde und der die Warteschlange deshalb bereits verlassen hat).

4. Verzweigungsprozesse
   • Wir betrachten den Fortpflanzungsprozess einer bestimmten Population, wobei $X_n$ die (zufällige) Gesamtanzahl der Nachkommen in der $n$-ten Generation sei; $X_0=1$.
   • Wir nehmen an, dass

     $$X_n= \sum\limits_{i=1}^{X_{n-1}} Z_{n,i}\,,$$ (11)

     
     
     wobei $\{Z_{n,i},\, n,i\in\mathbb{N}\}$ eine Familie von unabhängigen und identisch verteilten Zufallsvariaben ist, die ihre Werte in der Menge $E=\{0,1,\ldots\}$ annehmen.
   • Die Zufallsvariable $Z_{n,i}$ ist dabei die zufällige Anzahl der (unmittelbaren) Nachkommen des $i$-ten Individuums der $(n-1)$-ten Generation.
   • Die Folge $X_0,X_1,\ldots:\Omega\to\{0,1,\ldots\}$ von Zufallsvariablen, die durch $X_0=1$ und durch die Rekursionsgleichung (11) gegeben ist, wird Verzweigungsprozess genannt.
   • Man kann zeigen (vgl. Abschnitt 2.1.3), dass $X_0,X_1,\ldots$ eine Markov-Kette ist mit den Übergangswahrscheinlichkeiten
     $$p_{ij}=\left\{\begin{array}{ll} P\Bigl(\sum\limits_{k=1}^i Z_{1,k... ...$,}\\ 1\,, &\mbox{falls $i=j=0$,}\\ 0\,, &\mbox{sonst.} \end{array}\right.$$

5. Zyklische zufällige Irrfahrten 
   • Weitere Beispiele von Markov-Ketten können wie folgt konstruiert werden (vgl. E. Behrends (2000) Introduction to Markov Chains. Vieweg, Braunschweig, S.4).
     • Wir betrachten den endlichen Zustandsraum $E=\{0,1,\ldots,999\}$, die Anfangsverteilung

       $${\boldsymbol{\alpha}}=(1/16,4/16,6/16,4/16,1/16,0,\ldots,0)^\top$$ (12)

       
       
       und die Übergangswahrscheinlichkeiten
       $$p_{ij}=\left\{\begin{array}{ll} \displaystyle\frac{1}{6}\;, & \mb... ...od(1000)\in\{1,\ldots,6\}$,}\\ [3\jot] 0\,, &\mbox{sonst.} \end{array}\right.$$

     • Seien $X_0,Z_1,Z_2,\ldots:\Omega\to\{0,1,\ldots,999\}$ unabhängige Zufallsvariablen, wobei die Verteilung von $X_0$ durch (12) gegeben sei und
       $$P(Z_1=i)=P(Z_2=i)=\ldots=1/6\,,\qquad\forall\,i=1,\ldots,6\,.$$

     • Die rekursiv definierte Folge $X_0,X_1,\ldots\Omega\to\{0,1,\ldots,999\}$ von Zufallsvariablen mit

       $$X_n= (X_{n-1}+Z_n)\mod(1000)$$ (13)

       
       
       für $n\ge 1$ bildet dann eine Markov-Kette, die zyklischer Random Walk genannt wird; vgl. auch Übungsaufgabe 1.3.

     
     

   • Beachte 
     • Dieses Modell einer Markov-Kette kann auf die folgende Weise experimentell realisiert werden: Wir werfen zunächst $4$-mal eine Münze und registrieren, wie oft dabei das Ereignis ,,Zahl'' eintritt. Die Anzahl $x_0$ dieser Ereignisse fassen wir als Realisierung des zufälligen Anfangszustandes $X_0$ auf; vgl. das Bernoulli-Schema in Abschnitt WR-3.2.1.
     • Danach werfen wir $n$-mal einen Würfel und registrieren die jeweiligen Augenzahlen. Die Augenzahl $z_i$, die beim $i$-ten Wurf des Würfels eintritt, fassen wir als Realisierung des zufälligen ,,Zuwachses'' $Z_i$ auf; $i=1,\ldots,n$.
     • Der neue ,,Systemzustand'' $x_n$ ergibt sich dann durch die ,,Aktualisierung'' des alten Systemzustandes $x_{n-1}$ gemäß (13), und zwar unter Berücksichtigung des ,,Zuwachses'' $z_{n-1}$.
     • Wenn das Experiment nicht tatsächlich durch das Werfen einer Münze bzw. eines Würfels, sondern durch die Erzeugung entsprechender Pseudozufallszahlen $x_0,z_1,z_2,\ldots$ mit dem Computer durchgeführt wird, dann spricht man von Monte-Carlo-Simulation.
     • Methoden zur Konstruktion von dynamischen Simulationsalgorithmen, die auf Markov-Ketten beruhen, werden im zweiten Teil der Vorlesung ausführlich behandelt.