Beispiele

Im folgenden werden einige einfache Beispiele von Markov-Ketten vorgestellt.

1. Irrfahrt (Diffusion) Der Irrfahrer in einem unbegrenzten eindimensionalen Raum ist das Paradebeispiel für eine Markov-Kette. Der diskrete Wertebereich kann durch die Menge der ganzen Zahlen ausgedrückt werden. In jedem Zeitschritt wird der Irrfahrer mit der Wahrscheinlichkeit $p$ um 1 nach rechts und mit der Wahrscheinlichkeit $q$ um eins nach links wandern. Eine Trajektorie als Realisation der Markov-Kette beginnt also bei einer vorgegebenen ganzen Zahl als Anfangsbedingung und kann mit der Zeit immer weiter von diesem Anfangsort abdriften. Andererseits kann eine Trajektorie auch sehr lange in der Nähe des Anfangs bleiben. Falls $p$ recht groß ist (dann ist $q=1-p$ recht klein), wird der Irrfahrer wahrscheinlicher zu höheren Zahlen abdriften, als zu niedrigeren. Wie bei jeder Markov-Kette kann man die Wahrscheinlichkeit den Irrfahrer zu einem bestimmten Zeitpunkt an einem bestimmten Ort zu treffen, mit Hilfe der Übergangsmatrix und deren Potenzen berechnen. Die Elemente der Übergangsmatrix folgen aus der Bedingung, daß der Irrfahrer von einem Zustand $X_{i}$ nur in die beiden benachbarten Zustände $j=i\pm 1$ kommen kann. Damit hat die Übergangsmatrix nur in den Nebendiagonalen von 0 verschiedene Elemente. Es gilt
   

   $$p_{i,j}=\left\{ \begin{array}{ll} p, & \mbox{ falls }j=i+... ... falls }j=i-1\\ 0, & \mbox{ sonst } \end{array} \right. .$$ (3.9)

   
   
   Für die unendlich große Übergangsmatrix folgt dann
   

   $$P= \left(\begin{array}{cccccccc} \cdots & & & & & & & \cd... ...dots \\ \cdots & & & & & & & \cdots\\ \end{array}\right).$$ (3.10)

   
   
   Für praktische Berechnungen benötigt man diese unendlich große Matrix nicht. Für den ersten Zeitschritt wird zum Beispiel nur ein Ausschnitt mit $3\cdot 3=9$ Elementen benötigt. Für $n$ Zeitschritte wird eine Matrix der Größe $(1+2n)^{2}$ benötigt. Nach $n$ Zeitschritten kann der Irrfahrer maximal $n$ Orte von seiner Startposition entfernt sein. Am Beispiel des Irrfahrers läßt sich sehr viel veranschaulichen, so daß wir darauf zurückkommen werden.
2. Irrfahrt mit einem absorbierenden Rand (Ruinproblem) In diesem Fall steht dem Irrfahrer kein unbegrenzter Raum in beiden Richtungen zur Verfügung. Stattdessen soll bei 0 ein Rand sein. Dadurch wird der Wertebereich auf die Menge der natürlichen Zahlen eingeschränkt. Falls der Irrfahrer nun bei 0 vorbeikommt wird er dort gefangen werden, d.h. $p_{0,0}=1$ und $p_{0,j}=0$ für alle $j$. Da man den Anfangszustand als Kapital zu Beginn einer Reihe von aufeinanderfolgenden Einzelspielen mit jeweils gleicher Gewinnwahrscheinlichkeit ansehen kann, wird diese Form der Irrfahrt in der Spieltheorie als Ruinproblem bezeichnet. Falls man einmal kein Kapital mehr besitzt, ist das Spiel verloren. Die Übergangsmatrix ist jetzt nur noch in einer Richtung unendlich weit ausgedehnt:
   

   $$P= \left(\begin{array}{cccccc} 1 & 0 & \cdots & & & \\ ... ... & p & 0 \\ \cdots & & & & & \cdots\\ \end{array}\right).$$ (3.11)

   
   

3. Irrfahrt mit zwei absorbierenden Rändern Bei der Irrfahrt mit zwei Rändern ist der Wertebereich endlich. Wir können den kleinsten Wert 0 und den größten Wert $c$ nennen. Dann gilt zusätzlich zu $p_{0,0}=1$ auch noch $p_{c,c}=1$ und deshalb auch $p_{c,j}=0$ für alle $j$. Wenn die Zustände 0 oder $c$ einmal eingenommen sind, ist ein stationärer Zustand erreicht. Eine Solche Markov-Kette kann als Nullsummenspiel zweier Spieler interpretiert werden. Diese machen fortlaufend Spiele gegeneinander mit gleichbleibender Gewinnwahrscheinlichkeit. Gerecht währe dabei die Anfangsbedingung, daß jeder $c/2$ Mark hat. Der Verlierer eines Spiels zahlt dem Gewinner eine Mark. Die Summe des Geldes ist dabei konstant (deshalb der Name Nullsummenspiel). Versetzt man sich in die Position des einen Spielers, so hat er gewonnen, wenn er $c$ Mark hat. Er hat verloren, wenn er kein Geld mehr besitzt. Die Wahrscheinlichkeit, mit der er den Abend gewinnt, hängt von der Anfangsverteilung des Geldes unter den beiden Spielern und seiner Gewinnwahrscheinlichkeit bei den Einzelspielen ab. Die Übergangsmatrix, mit der er seine Gewinnwahrscheinlichkeit berechnen kann ist eine endliche quadratische Matrix der Ordnung $c+1$. Für $c=4$ folgt zum Beispiel
   

   $$P= \left(\begin{array}{ccccc} 1 & 0 & 0 & 0 & 0 \\ q & ... ...0 & q & 0 & p \\ 0 & 0 & 0 & 0 & 1 \\ \end{array}\right).$$ (3.12)

   
   

4. Irrfahrt mit zwei reflektierenden Rändern Die Irrfahrt mit reflektierenden Rändern ist als Diffusion in einem begrenzten Gebiet interpretierbar. Spieltheoretisch ist dieser Fall nicht besonders interessant, da immer wenn ein Spieler verlieren würde, dieser wieder ins Spiel gebracht wird. Die Randbedingungen reflektierender Ränder bei 0 und $c$ sind gegeben durch $p_{0,0}=0$, $p_{0,1}=1$, $p_{c,c}=0$ und $p_{c,c-1}=1$. Bei einer Kette mit den $5$ Zuständen 0 bis $4$ folgt dann für die Übergangsmatrix
   

   $$P= \left(\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ q & ... ...0 & q & 0 & p \\ 0 & 0 & 0 & 1 & 0 \\ \end{array}\right).$$ (3.13)

   
   

5. Irrfahrt mit Pausen (Unentschiedene Einzelspiele) Falls der Irrfahrer nicht in jedem Zeitschritt um eine Einheit wandern muß, sondern mit einer gewissen Wahrscheinlichkeit $r$ in dem Zustand bleibt, in dem er gerade ist, so sind auch die Hauptdiagonalen der Übergangsmatrix gefüllt. Für die Übergangswahrscheinlichkeiten $p_{ij}$ folgt dann
   

   $$p_{ij}= \left\{\begin{array}{ll} p, & \mbox{ falls } i=j+... ...{ falls } i=j \\ 0, & \mbox{ sonst. } \end{array}\right.$$ (3.14)

   
   
   Auch hier ist die Übergangsmatrix von der Ordnung unendlich.
6. Nichtlokale Markov-Ketten Alle bis jetzt explizit besprochenen Markov-Ketten waren lokale Markov-Ketten, da in jedem Zeitschritt nur direkt benachbarte Zustände erreicht werden konnten. Dies ist keinesfalls eine notwendige Eigenschaft. Die Formulierung durch Übergangsmatrizen entfaltet ihren Sinn erst dann klar, wenn nicht nur die Diagonalen und ersten Nebendiagonalen mit Elementen ungleich 0 gefüllt sind. Dann sind nicht nur Übergänge zu direkten Nachbarn möglich, und man spricht von nichtlokalen Ketten.
7. Räumlich und zeitlich homogene Markov-Ketten Die bisher betrachteten Beispiele waren alle zeitlich homogen und räumlich homogen, da $p_{ij}$ nicht explizit von $i$ oder $j$, sondern nur von der Differenz $j-i$ abhingen. Allgemein gilt für räumich homogene Markov-Ketten
   

   $$p_{ij}=a_{j-i}.$$ (3.15)

   
   
   Die Übergangswahrscheinlichkeit ist demnach für jeden Abstand eine Konstante. Mit $a_{-1}=q$, $a_{0}=r$ und $a_{1}=p$ erhält man die Irrfahrt mit Pausen.
8. Zustandsabhängige Markovketten Zustandsabhängige Markov-Ketten sind räumich nicht homogene Markov-Ketten. Das bedeutet, das bei diesen Markov-Ketten die Übergangswahrscheinlichkeiten explizit vom Zustand des Systems abhängen. Es gilt dann z.B. für den zustandsabhängigen Irrfahrer mit Pausen
   

   $$p_{ij}= \left\{\begin{array}{ll} p_{i}, & \mbox{ falls } ... ...{ falls } i=j \\ 0, & \mbox{ sonst. } \end{array}\right.$$ (3.16)

   
   

9. Ehrenfest-Modell Das Ehrenfest-Modell ist ein Spezialfall der zustandsabhängigen Markov-Ketten. Es hat als Wertebereich die Werte $0$ bis $c$. Die Übergangswahrscheinlichkeiten hängen nun vom Ort ab, und zwar in der Form $p_{i,i+1}=\frac{c-i}{c}$ und $p_{i,i-1}=\frac{i}{c}$. Das bedeutet, das sich eine Realisation eher von den Rändern entfernt, als diesen nahe zu kommen. Für $i=c/2$ befindet sich die Realisation in der Mitte des Wertebereichs. Die Übergangswahrscheinlichkeiten für beide Richtungen sind dann gleich groß. Für ein Ehrenfest-Modell mit den 5 Zuständen 0 bis 4 folgt dann die Übergangsmatrix
   

   $$P= \left(\begin{array}{ccccc} 0 & 1 & 0 & 0 & 0 \\ 1/4 ... ...3/4 & 0 & 1/4 \\ 0 & 0 & 0 & 1 & 0 \\ \end{array}\right).$$ (3.17)

   
   

10. Wartezeit-Modell Da Wartezeiten nicht kleiner als 0 sein sollten, ist der Wertebereich des Wartezeit-Modells durch die natürlichen Zahlen inkl. 0 gegeben. Es werden nun die Wahrscheinlichkeiten von einem Ort $i$ auf $0$ zu springen oder einen Wert höher (also auf $i+1$) zu springen vorgegeben:
    

    $$\begin{array}{lcl} p_{i,0} & = & p_{i}\\ p_{i,i+1} & = & 1-p_{i}. \end{array}$$ (3.18)

    
    
    Das bedeutet, daß die Realisation der Markov-Kette entweder um einen Wert höher springt, oder auf 0 zurückgeht. Der Sprung auf 0 soll nun immer ein Ereignis darstellen. Dann ist der Wert $i$ die Zeit, die seit dem letzten Eintreten des Ereignisses vergangen ist. In einem solchen Wartezeit-Modell ist es möglich, die Wahrscheinlichkeit für das Eintreten des Ereignisses beliebig von der Zeit seit dem letzten Eintreten abhängig zu machen. Betrachtet man den Spezialfall, daß die Wahrscheinlichkeit für das Eintreten des Ereignisses eine Konstante ist $(p_{i,0}=p)$, so ist die Wahrscheinlichkeit dafür, daß erst im $n$-ten Schritt auf 0 gesprungen wird, gegeben durch $p(x(\nu)\neq 0, \mbox{f\uml {u}r } 1\le\nu<n, x_{n}=0\vert x_{0}=0) = p\,(1-p)^{n-1}$. Das sollte dem interessierten Leser bekannt vorkommen.
11. Zweidimensionale Irrfahrt Markov-Ketten können natürlich auch mehrdimensional sein. Das einfachste Beispiel einer mehrdimensionalen Markov-Kette ist der zweidimensionale Irrfahrer. Man kann ihn als Zufallswanderer in den Straßen einer sehr symmetrischen Stadt interpretieren. An jeder Kreuzung hat er vier Möglichkeiten, von denen jede mit einer bestimmten Wahrscheinlichkeit $p_{k}$ gewählt wird. Wenn der Wanderer keine Pausen machen darf, muß gelten $p_{1}+p_{2}+p_{3}+p_{4}=1$. Die beiden Dimensionen werden nun dadurch formal unterschieden, daß die zweite Dimension durch gestrichene Größen dargestellt wird. Damit geht der Zufallswanderer in jedem Zeitschritt vom Zustand $i,i'$ in den Zustand $j,j'$ über. Der Zufallswanderer wird aber immer nur in eine Richtung pro Zeitschritt wandern können. Es ergibt sich deshalb für die zweidimensionale Übergangswahrscheinlichkeit
    

    $$p(i,i')(j,j')= \left\{ \begin{array}{lll} p_{1} & \mbox{... ... & \mbox{ f\uml {u}r } j=i, & j'=i'-1. \end{array} \right.$$ (3.19)