Markov-Ketten

Markov-Ketten sind stochastische Prozesse, die sich durch ihre „Gedächtnislosigkeit“ auszeichnen. Konkret bedeutet dies, dass für die Entwicklung des Prozesses lediglich der zuletzt beobachtete Zustand eine Rolle spielt. Alles was davor passiert ist, ist nicht von Interesse. Diese Eigenschaft wird auch Markov-Eigenschaft genannt. Anders ausgedrückt: Die Zukunft ist bedingt auf die Gegenwart unabhängig von der Vergangenheit. Das hört sich beim ersten Lesen durchaus etwas ungewohnt an, macht aber durchaus Sinn, wie man nachfolgend in diesem Artikel sehen wird. (Hinweis: Der Artikel basiert auf weiten Teilen auf das Buch Stochastische Modelle: Eine anwendungsorientierte Einführung (EMIL@A-stat) (German Edition). Hier findet man alle Beweise der hier aufgeführten Sätze, sowie auch einige Beispielaufgaben samt Lösungen für ein besseres Verständnis)

Formal sieht eine Markov-Kette per Definition folgendermaßen aus:
Markov Kette Definition
Xn ist hierbei die Zufallsvariable, während s und xn der entsprechende Wert ist, den die Zufallsvariable annimmt bzw. angenommen hat.

Die Übergangswahrscheinlichkeit, in dem von Zustand i in den Zustand j gewechselt wird, ist dabei folgendermaßen definiert:
Übergangswahrscheinlichkeit einer Markov-Kette
Dies stellt also die Abfolge der Werte da, welche die Zufallsvariable X annehmen kann. Falls diese Wahrscheinlichkeiten nicht von i abhängen, dann spricht man von einer homogenen Markov-Kette.

Homogene Markov-Kette

Von einer homogenen Markov-Kette spricht man, wenn die Übergangswahrscheinlichkeiten unabhängig von der Zeit t sind (andernfalls spricht man von einer inhomogenen Markov-Kette). Formal definiert bedeutet dies:
Homogene Markov-Kette
Die nachfolgenden Themen beziehen sich im Allgemeinen immer auf eine homogene Markov-Kette, weshalb das homogen nachfolgend weggelassen wird nur noch von der Markov-Kette die Rede ist.

Übergangsmatrix

In der Übergangsmatrix P werden nun die Werte von pij zusammengefasst. Es handelt sich dabei um eine stochastische Matrix. Das bedeutet, dass für jedes pij größer gleich 0 gelten muss und die Summe von pij = 1 ist, also die Zeilen sich zu eins addieren.

Langzeitentwicklung

Die Übergangsmatrix P beschreibt lediglich die Kurzzeitentwicklung (Ein-Schritt-Übergangswahrscheinlichkeit) einer homogenen Markov-Kette. Die Langzeitentwicklung (n-Schritt-Übergangswahrscheinlichkeit) bekommt man hingegen über die n-Schritt Übergangsmatrix P heraus. Diese ist die n-te Potenz von P. Mächte man also die Übergangsmatrix nach dem 3 Schritt, dann muss man P3 berechnet, indem man die Matrix dreimal mit sich selbst multipliziert.

Anfangsverteilung

Neben der Übergangsmatrix P wird für die Spezifizierung einer Markov-Kette auch noch die sogenannte Anfangsverteilung benötigt. Diese besagt, in welcher Wahrscheinlichkeit die Markov-Kette in welchem Zustand startet.

Klassen

Man kann Zustände in Klassen zusammenfassen und so die Klassen separat, losgelöst von der gesamten Markov-Kette betrachten. Die Übergangsmatrix wird dazu in stochastische Teilmatrizen zerlegt, die wiederum selbst als Übergangsmatrizen für Markov-Ketten angesehen werden können.

Eine Klasse nennt man dabei eine Gruppe von Zuständen, bei denen jeder Zustand von jedem anderen Zustand der Klasse erreichbar ist. Man spricht von einer abgeschlossenen Klasse, falls jeder Zustand j, der von i der Klasse erreichbar ist, auch in der Klasse liegt.

Irreduzibel

Von einer irreduziblen Klasse spricht man, falls eine Markov-Kette nur eine Klasse besitzt, bei der jeder Zustand von jedem Zustand erreichbar ist.

Reduzibel

Eine Markov-Kette mit mehreren Klassen heißt hingegen reduzibel.

Rekurrenz

Ein Zustand i einer Markov-Kette heißt rekurrent, falls gilt
Pi(Xn=I für unenedliche viele n) = 1
Dies bedeutet letztendlich nichts anders, als dass ein rekurrenter Zustand im Laufe der Zeit unendlich oft angenommen wird. Generell gilt, ein Zustand kann entweder rekurrent oder transient sein, nicht beides gleichzeitig. Was Transienz ist, erfährt man gleich.

Transienz

Ein Zustand i einer Markov-Kette heißt transient, falls gilt
Pi(Xn=I für unenedliche viele n) = 0
Dies wiederum bedeutet nichts anderes, alls das ein transienter Zustand im Laufe der Zeit nur endlich oft angenommen wird.

Markov-Ketten Aufgaben und Lösungen

Viele unterschiedliche Aufgaben mit ausführlichen Lösungen zu den verschiedenen Themenbereichen der Markov-Ketten findet man im Buch Stochastische Modelle: Eine anwendungsorientierte Einführung. Aber auch im Internet habe ich einige Aufgabensammlungen samt Lösungen gefunden, auf die ich nachfolgend hinweisen möchte:

Interessante Links zu Markov-Ketten

Nachfolgend findet man weitere interessante Seiten rund um das Thema Markov-Ketten:

Quellen