Markov-Kette

Markov-Kette

  • 25. April 2018
  • Posted by: Mika
Keine Kommentare

Hat Dein stochastischer Prozess ein „kurzes Gedächtnis“ bzw., präzise ausgedrückt, ist für die Verteilung von X(t) ausschließlich die vorherige Realisation von X(t-1) relevant und alle davor liegenden Werte besitzen keinen Einfluss, so ist Dein Prozess ein Markov-Prozess.

Die Verteilungsfunktion von X(t) wird dann nicht von weiter in der Vergangenheit liegenden Realisationen verändert:

    \begin{equation*} P[X(t) \le y | X(t-1)=x_{t-1}; ...;X(0)=x_0] =P[X(t) \le y | X(t-1)=x_{t-1}] \end{equation*}

Handelt es sich um einen zeitdiskreten Prozess, wenn also X(t) nur abzählbar viele Werte annehmen kann, so heißt Dein Prozess Markov-Kette.

Stell Dir vor, ein Spieler besitzt ein Anfangskapital X_0 von 30 Euro. Er spielt im Casino mit einem idealen Würfel nach den folgenden Spielregeln:

  • würfelt er eine Eins, Zwei oder Drei, so zahlt er 10 € an die Bank.
  • würfelt er die Vier, erhält niemand eine Auszahlung, und
  • wirft er fünf oder sechs Augen, so zahlt ihm die Bank 10 € aus.

Wegen des idealen Würfels, bei dem die Wahrscheinlichkeit für jede Augenzahl \frac 1 6 beträgt, kannst Du die Wahrscheinlichkeiten für die interessanten Ereignisse bestimmen:

P(1;2;3) = \frac 3 6 = \frac 1 2

P(4) = \frac 1 6

P(5;6) = \frac 2 6 = \frac 1 3

Vor Spielbeginn legt der Spieler noch die folgenden Ausstiegsregeln fest: Er beendet das Spiel, wenn sein Kapital auf 10 Euro geschmolzen oder auf 50 Euro angestiegen ist.

Du kannst die Höhe seines Kapitals jetzt als stochastischen Prozess X(t) betrachten, mit X(0)=30, der sich bei jedem Wurf t= 0,1,… entsprechend der Spielregeln erhöht, gleichbleibt oder reduziert: Mögliche Prozessverläufe in den ersten Runden sind in der Grafik dargestellt:

Markow-Kette

Das Anfangskapital in Periode t=0 ist mit X(0)=30 bekannt. Für Periode t=1 gibt es drei mögliche Kapitalbeträge, die mit den bekannten Wahrscheinlichkeiten eintreten. Der Spieler würfelt in t=1; entsprechend der geworfenen Augenzahl erhält er eine Auszahlung, muss selbst bezahlen oder sein Kapital bleibt gleich. Der gleiche Ablauf erfolgt in t=2. Dadurch ergeben sich die möglichen Kapitalbestände X(2).

In der Grafik kannst Du erkennen, dass sich bei der Variante X(2)=30 drei Zweige treffen: Dieser Kapitalbestand kann sich aus dem Anfangskapital entweder durch Zahlung von 10 € in der ersten Runde und Erhalt von 10 Euro in der zweiten Runde oder durch Erhalt von 10 € in der ersten Runde und Zahlung von 10 € in der zweiten Runde oder durch zweimaliges Würfeln der Vier, ohne irgendeine Auszahlung also, ergeben.

Wie aber die 30 € zustande gekommen sind, spielt für den Fortgang des Spiels keine Rolle: ausgehend von X(2)=30 € gibt es drei mögliche Spielausgänge.

Da für die Erwartungen von X(t) also nur die Realisation x(t-1) relevant ist, hast Du eine Markov-Kette gegeben. Diese stellst Du üblicherweise durch ein Prozessdiagramm dar, das die möglichen (abzählbar vielen) Zustände Z_i, i=1,2,..,I und die Übergangswahrscheinlichkeiten von einem Zustand in den anderen enthält: In Deinem Beispiel hast Du fünf mögliche Zustände gegeben:

  • Z_1=30 €
  • Z_2=20 €
  • Z_3=40 €
  • Z_4=10 €
  • Z_5=50 €

 

Markov-Prozess

Die verschiedenen Zustände sind mit gerichteten Pfeilen versehen, die in roter Schrift die Übergangswahrscheinlichkeiten von einem Zustand in den anderen aufzeigen. Befindest Du Dich etwa im Zustand Z_2 mit X(t)=20 €,

  • so führt ein Pfeil zu Z_1=30; ein Gewinn von 10€ und der Übergang zu Z_1 tritt mit einer Wahrscheinlichkeit von \frac 1 3 ein;
  • ein weiterer Pfeil führt zu Zustand Z_4=10; einen Verlust von 10 € und den Übergang zu Z_4 erleidest Du mit einer Übergangswahrscheinlichkeit von \frac 1 2;
  • ein dritter Preil führt von Z_2 zu Z_2 und zeigt die Bleibewahrscheinlichkeit in Höhe von \frac 1 6 an.

Um das Prozessdiagramm rechentechnisch besser handhaben zu können, fasst Du es in einer Übergangsmatrix zusammen, bei der die Zeilen die Zustände angeben, in die gewechselt wird und die Spalten die Zustände bezeichnen, aus denen gewechselt wird:

    \begin{equation*} M = \left(\begin {array}{ccccc} m_{11}&m_{12}&m_{13}&m_{14}&m_{15}\\ m_{21}&m_{22}&m_{23}&m_{24}&m_{25}\\ m_{33}&m_{32}&m_{33}&m_{34}&m_{35}\\ m_{41}&m_{42}&m_{43}&m_{44}&m_{45}\\ m_{51}&m_{52}&m_{53}&m_{54}&m_{55}\end{array}\right) = \left(\begin {array}{ccccc} \frac 1 6&\frac 1 3 &\frac 1 2& 0 &0\\ \\\frac 1 2&\frac 1 6&0&0&0\\\\ \frac 1 3&0&\frac 1 6&0&0\\\\ 0&\frac 1 2&0&1&0\\\\ 0&0&\frac 1 3&0&1 \end{array}\right) \end{equation*}

m_{13} gibt Dir die Wahrscheinlichkeit an, mit der sich der Spieler aus dem Zustand Z_3 in den Zustand Z_1 begibt: Die Wahrscheinlichkeit beträgt \frac 1 3.

Bezeichnest Du jetzt mit \vec z_t den Spaltenvektor der Wahrscheinlichkeiten, mit denen der Zustand i im Zeitpunkt t erreicht wird,

    \begin{equation*} \vec z_t^T=(z_{t1},...,z_{t5})\end{equation*}

so gilt für t=0 mit bekanntem Anfangskapital:

Mit Sicherheit ist in t=0 der Zustand 1 eingetreten.

Die Wahrscheinlichkeiten \vec z_1 im Zeitpunkt t=1 erhältst Du durch Multiplikation von M und \vec z_0:

    \begin{equation*} \vec z_1 = M \cdot \vec z_0 = \left(\begin {array}{ccccc} \frac 1 6&\frac 1 3 &\frac 1 2& 0 &0\\ \\ \frac 1 2&\frac 1 6&0&0&0\\\\ \frac 1 3&0&\frac 1 6&0&0\\\\ 0&\frac 1 2&0&1&0\\\\ 0&0&\frac 1 3&0&1 \end{array}\right) \cdot \left(\begin {array}{c} 1\\0\\0\\0\\0 \end{array}\right) = \left(\begin {array}{c} \frac 1 6\\ \\ \frac 1 2\\\\\frac 1 3\\\\0\\\\0 \end{array}\right) \end{equation*}

Allgemein erhältst Du die Wahrscheinlichkeiten z_{it}, mit denen der Zustand Z_ii in der Periode t erreicht wird, durch Multiplikation der Matrix der Übergangswahrscheinlichkeiten mit dem Vektor \z_{t-1} der Vorperiode:

    \begin{equation*} \vec z_t = M \cdot \vec z_{t-1} \end{equation*}

Für ausgewählte Zeitpunkte t zeigt Dir die Tabelle diese Wahrscheinlichkeiten für Dein Beispiel:

t 0 1 2 … 5 … 10 … 15
z_{t1} 1,00 0,17 0,36 … 0,11 … 0,03 … 0,01
z_{t2} – 0,50 0,17 0,10 0,02 0,01
z_{t3} – 0,33 0,11 0,07 0,01 0,00
z_{t4} – – 0,25 0,50 0,65 0,68
z_{t5} – – 0,11 0,22 0,29 0,30

Die letzte Spalte gibt also die Wahrscheinlichkeiten an, mit denen die Zustände Z_1 bis Z_5 nach der 15. Runde erreicht werden: die ersten drei (gemäßigten Zustände) sind dann sehr unwahrscheinlich; die Zahl 0,68 in der zweitunterste Zeile besagt, dass der Spieler nach der 15. Runde mit einer Wahrscheinlichkeit von 68\% im Zustand Z_4 ist, also mit einem Restkapital von 10 € ausgestiegen ist; mit einer Wahrscheinlichkeit von 30\% besitzt er dann ein Restkapital von 50 €.

Markov-Ketten können in sehr unterschiedlichen Bereichen eingesetzt werden, beispielsweise

  • in der Warteschlangentheorie, um die Wahrscheinlichkeiten für die Anzahl der in einer Schlange stehenden Kunden zu ermitteln;
  • in der der Finanztheorie, zur Modellierung von Aktenkursentwicklungen;
  • in der Versicherungsmathematik etwa zur Modellierung von Invaliditätsrisiken sowie
  • im Qualitätsmanagement, zur Quantifizierung der Ausfallwahrscheinlichkeiten von Systemen.