Markovkette und Übergangsmatrix: Motivation und einfache Beispiele

Einordnung des Artikels

• Ausgewählte Kapitel der Mathematik (für Programmierer, Informatiker, Ingenieure und Naturwissenschaftler)
  • Wahrscheinlichkeitsrechnung
    • Markov-Ketten
      • Markovkette und Übergangsmatrix: Motivation und einfache Beispiele

Einführung

Betrachtet man eine Folge von unabhängigen Zufallsvariablen X₁, X₂, ..., X_n-1, X_n, so besagt die Unabhängigkeit, dass die Kenntnis der Werte der Zufallsvariablen X₁, X₂, ..., X_n-1 keinen Einfluss auf den Wert von X_n hat. Man drückt dies oft aus durch "der Zufall hat kein Gedächtnis".

Eine Markov-Kette ist eine Folge von Zufallsvariablen, die ein "kurzes Gedächtnis" haben: Hier hängt der Wert von X_n vom Wert von X_n-1, aber nicht von den Werten der vorhergehenden Zufallsvariablen X₁, X₂, ..., X_n-2 ab.

In diesem Sinne ist die Markov-Kette eine Verallgemeinerung der Unabhängigkeit von Zufallsvariablen. Die "Abhängigkeit" zwischen den Zufallsvariablen X_n-1 und X_n wird durch die Übergangswahrscheinlichkeiten

P(X_n = x_n | X_n-1 = x_n-1)

ausgedrückt. Dabei ist P(X_n = x_n | X_n-1 = x_n-1) die bedingte Wahrscheinlichkeit dafür, dass die Zufallsvariable X_n den Wert x_n annimmt, wenn bekannt ist, dass die Zufallsvariable X_n-1 den Wert x_n-1 angenommen hat.

Die Übergangswahrscheinlichkeiten werden dann zur sogenannten Übergangsmatrix zusammengefasst. Ist die Wahrscheinlichkeitsverteilung einer Zufallsvariable X₁ bekannt, so kann mit Hilfe der Übergangsmatrix sukzessive die Verteilung der Zufallsvariablen X₂, X₃, ... berechnet werden.

Im Folgenden sollen

• einige einfache Beispiele für Markov-Ketten vorgestellt werden,
• die wichtigsten Begriffe definiert werden, nämlich Markov-Kette und Übergangsmatrix,
• die wichtigsten Eigenschaften der Übergangsmatrix besprochen werden sowie
• ein Ausblick auf weitere Fragestellungen gegeben werden.

Motivation der Markov-Kette

Unabhängigkeit beim Münzwurf

Der unabhängige Münzwurf ist das Paradebeispiel der Wahrscheinlichkeitsrechnung für unabhängige Zufallsvariablen: Wird eine Münze n-mal hintereinander geworfen, so entsteht eine Folge von gleichverteilten Zufallsvariablen

X₁, X₂, ..., X_n,

die paarweise voneinander unabhängig sind.

Jede dieser Zufallsvariablen kann die gleichen Werte ("Kopf" oder "Zahl" beziehungsweise 0 oder 1) annehmen und alle Zufallsvariablen gehorchen der gleichen Verteilung, speziell für eine Laplace-Münze gilt:

P(X_i = 0) = 1/2 = P(X_i = 1), i = 1, 2, ..., n.

Unabhängigkeit der Zufallsvariablen bedeutet hier, dass gilt

P(X_i = x_i, X_j = x_j) = P(X_i = x_i) · P(X_j = x_j).

Oder salopp ausgedrückt: "Der Zufall hat kein Gedächtnis". Aus dem Ergebnis eines Wurfes kann nicht auf das Ergebnis eines anderen Wurfes (speziell des nächsten Wurfes) geschlossen werden.

Die Irrfahrt als Beispiel einer Markov-Kette

Der unabhängige Münzwurf kann jetzt verwendet werden, um eine Markov-Kette zu erzeugen – hier der Spezialfall einer Irrfahrt: Dazu stelle man sich ein Teilchen vor, das bei y = 0 startet und sich in jedem Zeitschritt entweder nach oben oder unten bewegen kann (jeweils um die gleiche Strecke, deren Länge gleich 1 gewählt wird, siehe Abbildung 1). Der Münzwurf wird verwendet, um die Richtung der Bewegung festzulegen, etwa 1 für eine Bewegung nach oben und 0 für eine Bewegung nach unten.

Aus der Folge der Zufallsvariablen X₁, X₂, ..., X_n entsteht somit eine Folge von Zufallsvariablen

Y₀, Y₁, Y₂, ..., Y_n,

welche die Position des Teilchens auf der y-Achse beschreibt.

Anders formuliert: Die Zuwächse der Zufallsvariablen Y sind gerade die X:

Y_i - Y_{i - 1} = X_i, i = 1, 2, ...

Startet das Teilchen bei y = 0 und wird die Münze n-mal geworfen, so kann das Teilchen die Positionen

-n, -n+1, ..., -1, 0, 1, ..., n-1, n

annehmen.

Wird eine Laplace-Münze verwendet, so gilt für die Position Y₁ nach dem ersten Münzwurf:

P(Y₁ = -1) = 1/2 und P( Y₁ = 1) = 1/2.

Die Wahrscheinlichkeiten für die Position Y₂ nach dem zweiten Münzwurf hängt jetzt davon ab, welche Position Y₁ das Teilchen einnimmt:

Für Y₁ = -1 gilt:

P(Y₂ = -2) = 1/2 und P( Y₂ = 0) = 1/2.

Für Y₁ = 1 gilt:

P(Y₂ = 0) = 1/2 und P( Y₂ = 2) = 1/2.

Andere Positionen kann das Teilchen nicht einnehmen.

Man erkennt jetzt: Aus den Wahrscheinlichkeiten der Ereignisse des Münzwurfes werden Übergangswahrscheinlichkeiten für das Teilchen, um eine Position nach oben oder unten zu wandern. Und die Unabhängigkeit der Münzwürfe sorgt dafür, dass diese Übergangswahrscheinlichkeiten nur von der aktuellen Position, aber nicht von der "Vorgeschichte" abhängen. Mit der "Vorgeschichte" sind die Werte der Zufallsvariablen gemeint, die zeitlich vor dem aktuellen Wert liegen.

Man kann jetzt diese Übergangswahrscheinlichkeiten in eine Tabelle eintragen, siehe Abbildung 1 unten. Die Tabelle ist zeilenweise zu lesen – man beginnt mit der Zeile zur Position y = 0 (mittlere Zeile):

• Die Spalten geben jeweils das Ziel eines Schrittes an.
• Startet man bei y = 0, so kann man lediglich die Positionen y = -1 und y = 1 erreichen.
• Die zugehörigen Übergangswahrscheinlichkeiten sind jeweils 1/2.
• Alle Wahrscheinlichkeiten für andere Übergänge, die bei y = 0 starten, sind gleich 0.

Entsprechend liest man in den anderen Zeilen die erlaubten Übergänge und zugehörigen Wahrscheinlichkeiten ab.

Mit Hilfe der Tabelle kann man daher eine Matrix definieren, in welche diese Übergangswahrscheinlichkeiten p_ij eingetragen werden. Es gilt:

p_ij = 1/2 für j = i+1 oder j = i-1.

Alle anderen Einträge der Matrix sind gleich 0.

Dies Matrix wird als die Übergangsmatrix bezeichnet. Die Anzahl der Zeilen und Spalten der Übergangsmatrix muss an die Anzahl der Münzwürfe angepasst werden.

Abbildung 1: Aus den Zufallsvariablen X₁, X₂, ..., X_n für den Münzwurf wird eine Irrfahrt konstruiert: Die Irrfahrt startet bei y = 0 und der Wert X_i gibt an, ob man sich in positive oder negative y-Richtung bewegt. Es entsteht eine neue Folge von Zufallsvariablen Y₁ = 0 (Startwert), Y₁, ... In der Tabelle unten erkennt man, welche Übergänge erlaubt sind und mit welchen Wahrscheinlichkeiten sie stattfinden.

Die Ergebnisse des unabhängigen Münzwurfes können leicht verwendet werden, um die Irrfahrt zu simulieren:

1. Ein Zufallsgenerator erzeugt die Ergebnisse des Münzwurfes (mit möglichen Ergebnissen +1 oder -1 und den zugehörigen Wahrscheinlichkeiten p und q = 1 - p).
2. Bildet man von der Folge dieser Zahlen die kumulierten Summen, erhält man die Position der Irrfahrt, die bei y = 0 startet.

Die Abbildungen 2 und 3 zeigen derartige Simulationen mit n = 500 Zeitschritten und Wahrscheinlichkeiten p = 1/2 beziehungsweise p = 1/5. Dabei wird auf der x-Achse die Zeit und auf der y-Achse die Position des Teilchens aufgetragen.

Grün eingetragen ist der Erwartungswert der Position des Teilchens. Die Gleichung der Gerade lässt sich aus dem Erwartungswert für den Zuwachs pro Zeitschritt berechnen

E(X_i) = p·(+1) + (1 - p)·(-1) = 2p - 1.

Abbildung 2: Simulation von 9 Irrfahrten mit n = 500 Zeitschritten zum Anfangswert y = 0 und einer Wahrscheinlichkeit p = 1/2 dafür, dass ein Schritt nach oben ausgeführt wird.

Abbildung 3: Analog zu Abbildung 2 mit p = 1/5.

Das Beispiel der Irrfahrt, die mit Hilfe des Münzwurfes erzeugt wird, zeigt eine sehr einfache Markov-Kette. Folgende Merkmale werden eine Markov-Kette kennzeichnen:

• Es gibt endlich viele oder abzählbar viele Zustände, zwischen denen Übergänge möglich sind.
• In jedem Zeitschritt wird ein Übergang ausgeführt.
• Die Wahrscheinlichkeiten für einen Übergang hängen nur vom aktuellen Zustand ab, aber nicht davon, welche Zustände früher angenommen wurden.

Das Beispiel der Irrfahrt kann den Eindruck erwecken, dass in jedem Zeitschritt lediglich eine Veränderung des Zustandes um "eine Position" möglich ist. Diese Eigenschaft gilt speziell für Irrfahrten (manchmal erlaubt man auch, dass das Teilchen die Position beibehält). Für Markov-Ketten werden beliebige Übergänge zwischen den Zuständen erlaubt.

Definitionen

Markov-Kette und Übergangsmatrix

Die zuletzt beschriebenen Merkmale der Irrfahrt werden jetzt verwendet (siehe Abbildung 4), um folgende Begriffe zu definieren:

• Markov-Kette
• homogene Markov-Kette
• Übergangsmatrix.

Abbildung 4: Definition einer Markov-Kette und der Übergangsmatrix.

Die Gleichung (1) drückt aus, dass eine Markov-Kette eine Verallgemeinerung der Unabhängigkeit beschreibt:

Bei einer Folge von unabhängigen Zufallsvariablen Y₀, Y₁, Y₂, ... kann aus dem Wert von Y_n-1 nicht auf den Wert von Y_n geschlossen werden – jede Zufallsvariable gehorcht ihrer eigenen Verteilung und der Wert von Y_n wird allein gemäß der eigenen Verteilung bestimmt.

Dagegen hängt bei einer Markov-Kette der Wert von Y_n davon ab, welcher Wert unmittelbar zuvor angenommen wurde – also von Y_n-1. Die weitere "Vorgeschichte" – also die Werte von Y₀, Y₁, Y₂, ..., Y_n-2 haben keinen Einfluss auf den Wert von Y_n.

Von einer homogenen Markov-Kette spricht man, wenn für jedes n die gleichen Übergangswahrscheinlichkeiten zwischen den Zuständen bestehen (siehe Gleichung (2) in Abbildung 4). Allein aus der "Unabhängigkeit von der Vorgeschichte" folgt noch nicht die Homogenität. Im Folgenden werden ausschließlich homogene Markov-Ketten betrachtet.

Markov-Ketten bei unendlich vielen Zuständen

Die Definition der Übergangsmatrix (siehe Gleichung (3) in Abbildung 4) setzt voraus, dass die Menge M der möglichen Zustände endlich ist. Die Definition der Markov-Kette nach Gleichung (1) kann natürlich auch für Mengen M mit abzählbar vielen Elementen verwendet werden. Anstelle der Übergangsmatrix muss dann ein Operator definiert. Dazu muss man die Matrizenmultiplikationen, die später mit der Übergangsmatrix T ausgeführt werden, als unendliche Summen lesen.

Eigenschaften der Übergangsmatrix

Aus der Definition der Markov-Kette lässt sich ablesen, dass ihre Eigenschaften von zwei Größen bestimmt werden:

1. Übergangsmatrix T,
2. Startverteilung μ.

Es wird sich im Laufe der Untersuchungen zeigen: Die Markov-Eigenschaft (Gleichung (1) in Abbildung 4) sorgt dafür, dass – auf größeren Zeitskalen betrachtet – das Verhalten der Markov-Kette nur von der Übergangsmatrix T und nicht mehr von der Startverteilung μ abhängt. Die Übergangsmatrix soll daher näher untersucht werden.

Dazu werden an einem sehr einfachen Beispiel die elementaren Eigenschaften der Übergangsmatrix diskutiert:

1. Die Übergangsmatrix als stochastische Matrix.
2. Anwendung der Übergangsmatrix auf eine Wahrscheinlichkeitsverteilung.
3. Bedeutung der Potenzen der Übergangsmatrix.

Beispiel für eine Übergangsmatrix

In diesem Abschnitt wird ein einfaches Beispiel verwendet, um mit den Eigenschaften der Übergangsmatrix vertraut zu werden:

• Die Menge M der Zustände besteht aus drei Elementen M = {1, 2, 3}.
• Die Übergangswahrscheinlichkeiten werden so gewählt, dass der aktuelle Zustand im nächsten Zeitschritt mit hoher Wahrscheinlichkeit wiederum angenommen wird (hier 80 Prozent).
• Dagegen finden Übergänge zu anderen Zustände nur mit einer kleiner Wahrscheinlichkeit statt (hier 10 Prozent).

Abbildung 5 zeigt oben die erlaubten Übergänge und die zugehörige Übergangsmatrix T. Wie oben beschrieben, müssen die Einträge zeilenweise gelesen werden:

Zeile 1: Vom Zustand 1 ausgehend wird der Zustand 1 mit Wahrscheinlichkeit 0.8 erneut angenommen; die Zustände 2 und 3 werden jeweils mit Wahrscheinlichkeit 0.1 angenommen.

Entsprechend sind Zeile 2 und 3 zu lesen.

Abbildung 5: Beispiel einer Übergangsmatrix, die dafür sorgt, dass ein einmal erreichter Zustand mit hoher Wahrscheinlichkeit erneut angenommen wird.

Abbildung 6 zeigt einige Simulationen zu der von T erzeugten Markov-Kette:

• Zu Beginn wird jeweils der Zustand 1 angenommen.
• Mit einem Zufallsgenerator wird gemäß den Übergangswahrscheinlichkeiten der neue Zustände bestimmt.
• Es werden 500 Zeitschritte durchlaufen.

Abbildung 6: Simulationen der Markov-Kette. Auf der x-Achse werden die Zeitschritte aufgetragen, auf der y-Achse ist der jeweils angenommene Zustand zu erkennen.

Man erkennt deutlich, dass immer wieder längere Phasen auftreten, in denen kein Übergang stattfindet.

Die Übergangsmatrix als stochastische Matrix

Da die i-te Zeile einer Übergangsmatrix die Wahrscheinlichkeiten dafür angibt, um man vom Zustand i in einen der anderen Zustände aus M zu gelangen, müssen sich die Einträge jeder Zeile zu 1 addieren. Und alle Einträge sind nicht-negative Zahlen. (Ein Eintrag null ist auch erlaubt und er bedeutet, dass der entsprechende Übergang niemals stattfinden kann.)

Matrizen mit diesen beiden Eigenschaften werden als stochastische Matrizen bezeichnet.

Man beachte, dass über die Spaltensummen keine Aussage gemacht wird. Das Beispiel oben verwendet eine Übergangsmatrix, bei der auch die Spaltensummen gleich 1 sind – diese Eigenschaft ist aber nicht zwingend gegeben.

Gegenbeispiel: Verändert man die dritte Zeile der Übergangsmatrix T zu (0.2, 0, 0.8), so sind die erste und zweite Spaltensumme von 1 verschieden. Die Matrix ist dennoch eine stochastische Matrix und die Übergangsmatrix einer Markov-Kette (jetzt kann ausgehend von Zustand 3 der Zustand 2 nicht erreicht werden – er kann nur über den Umweg 1 erreicht werden).

Anwendung der Übergangsmatrix auf eine Wahrscheinlichkeitsverteilung

In den Simulationen in Abbildung 6 wurde jeweils ein Startwert fest vorgegeben (hier jeweils der Zustand 1) und der folgende Zustand gemäß den Übergangswahrscheinlichkeiten ausgewürfelt. Man kann sich aber auch eine allgemeinere Situation vorstellen:

Für den Anfangszustand (Zufallsvariable Y₀) ist eine Wahrscheinlichkeitsverteilung μ⁽⁰⁾ auf der Menge M gegeben (dies ist gerade die Startverteilung aus der Definition der Markov-Kette, siehe Abbildung 4). Das heißt für jeden der N Zustände aus M besteht eine gewisse Wahrscheinlichkeit μ₁⁽⁰⁾, μ₂⁽⁰⁾, ..., μ_N⁽⁰⁾ dafür, dass er als Anfangswert vorliegt, also

μ₁⁽⁰⁾ = P(Y₀ = 1), μ₂⁽⁰⁾ = P(Y₀ = 2), ..., μ_N⁽⁰⁾ = P(Y₀ = N).

Es ist jetzt naheliegend zu fragen, wie man aus der Startverteilung μ⁽⁰⁾ und der Übergangsmatrix T die Verteilung der Zufallsvariable Y₁ berechnet: Um in einem Zustand Y₁ = j zu gelangen, können alle Zustände Y₀ = i vorliegen und es muss ein Übergang i → j stattfinden. Die entsprechende Wahrscheinlichkeit berechnet sich nach Gleichung (2) in Abbildung 4.

Da man diese Berechnung für jedes j ∈ M durchführen kann, kann man die Berechnung der Verteilung von Y₁ als eine Summe von Produkten schreiben (siehe Gleichung (2) in Abbildung 7).

Interpretiert man die Startverteilung μ^{(0) als Zeilenvektor, so kann man diese Berechnungen nach Gleichung (2) als Matrizenmultiplikation auffassen: der Zeilenvektor μ}(0) wird von links mit der Übergangsmatrix T multipliziert. Das Ergebnis (wieder ein Zeilenvektor) ist die Verteilung μ⁽¹⁾ der Zufallsvariable Y₁. Und indem man diese Multiplikationen iteriert, erhält man die Verteilungen der Zufallsvariablen Y_n, n = 1, 2, ...

Abbildung 7: Die Übergangsmatrix wird verwendet, um aus einer gegebenen Wahrscheinlichkeitsverteilung die Verteilung im nächsten Zeitschritt zu berechnen. Entsprechend kann man die Potenzen der Übergangsmatrix interpretieren.

Abbildung 8 und 9 zeigen die Anwendung der Übergangsmatrix T aus Abbildung 5:

• In Abbildung 8 wird diejenige Startverteilung gewählt, in der mit Sicherheit der Zustand 1 vorliegt (Verteilung von Y₀ links oben). Die Verteilungen für die 8 folgenden Zeitschritte werden sukzessive durch Matrizenmultiplikation berechnet (Verteilung von Y₁ bis Y₈)
• Analog wird in Abbildung 9 die Startverteilung gewählt, in der entweder der Zustand 1 oder der Zustand 2 vorliegt – und zwar jeweils mit Wahrscheinlichkeit 1/2. Wieder werden die Verteilungen der 8 folgenden Zeitschritte berechnet.

Grün eingetragen sind jeweils die Geraden zur Wahrscheinlichkeit 1 beziehungsweise 1/3.

Abbildung 8: Darstellung der Verteilungen der Markov-Kette mit Startverteilung (1, 0, 0).

Abbildung 9: Darstellung der Verteilungen der Markov-Kette mit Startverteilung (0.5, 0.5, 0).

Die Bedeutung der Potenzen der Übergangsmatrix

Das Matrixelement T_ij gibt eine Übergangswahrscheinlichkeit vom Zustand i zum Zustand j an (siehe Gleichung (3) in Abbildung 4). Da man mit Hilfe der Matrix Tⁿ die Verteilung μ⁽ⁿ⁾ aus der Startverteilung μ⁽⁰⁾ berechnet, nämlich mit

μ⁽ⁿ⁾ = μ⁽⁰⁾ · Tⁿ,

sollte auch klar sein, welche Bedeutung die Einträge Tⁿ_ij der Matrix Tⁿ haben. Sie beschreiben die Wahrscheinlichkeit dafür, dass ein Übergang von i nach j in n Zeitschritten stattfindet:

(Tⁿ)_ij = P(Y_n = j|Y₀ = i).

Die Erklärung dazu ist in Abbildung 7 unten (Gleichung (4) und (5)) für den Spezialfall n = 2 gezeigt.

Weiteres Beispiel: Irrfahrt mit Absorption am Rand

Beschreibung des Modells

Oben wurde das Beispiel einer Irrfahrt besprochen, in dem sich ein Teilchen in jedem Zeitschritt entweder um eine Längeneinheit nach oben oder nach unten bewegen kann (siehe Abbildung 1). Dieses Modell besitzt eine abzählbar unendliche Menge M von Zuständen; die Übergangsmatrix kann daher nicht als endliche Matrix angegeben werden.

Es soll ein verwandtes Beispiel diskutiert werden: Es sind zwei Grenzen ("der Rand") vorgegeben, von denen das Teilchen absorbiert wird; es verbleibt dann für immer in dieser Position. Im Inneren der Menge M gehorcht die Irrfahrt den gleichen Gesetzen wie im Beispiel oben:

• Das Teilchen startet in y = 0.
• Es bewegt sich in jedem Zeitschritt entweder um eine Längeneinheit nach oben oder nach unten.
• Die Wahrscheinlichkeit für einen Schritt nach oben ist p (0 < p < 1), die Wahrscheinlichkeit für einen Schritt nach unten ist q = 1 - p.

Liegen die Grenzen symmetrisch zu y = 0, so wird die Menge M der Zustände modelliert durch:

M = {-N, -N + 1, ..., -1, 0, 1, ..., N},

wobei N einen natürliche Zahl ist.

Festlegen der Übergangsmatrix

Zum Aufstellen der Übergangsmatrix kann man etwa folgendermaßen vorgehen – die Menge M der Zustände wird dazu wie ein Graph (im Sinne der Graphentheorie) interpretiert:

• Man identifiziert zuerst die erlaubten Übergänge und stellt die Adjazenzmatrix A auf.
• Dann legt man für jeden der Übergänge die Wahrscheinlichkeit fest, mit der er stattfindet.

Festlegen der Adjazenzmatrix A:

1. Befindet man sich am Rand, also bei y = N oder y = -N, so wird der aktuelle Zustand im nächsten Zeitschritt erneut angenommen. Andere Übergänge sind vom Rand aus nicht erlaubt. (Siehe Zustand 4 und -4 in Abbildung 10.)
2. Im Inneren von M kann man sich von jedem y aus entweder nach y+1 oder y-1 bewegen. Auch hier gibt es keine anderen Übergänge. (Siehe Zustände -3, ..., 3 in Abbildung 10.)

Abbildung 10 zeigt in Gleichung (1) die Adjazenzmatrix für den Fall N = 4.

Abbildung 10: Adjazenzmatrix und Übergangsmatrix für die Irrfahrt mit Absorption am Rand für N = 4.

Festlegen der Übergangsmatrix T:

In der Adjazenzmatrix werden die Einträge 1 aufgesucht und durch die zugehörige Übergangswahrscheinlichkeit ersetzt. Die Übergangsmatrix T für das Beispiel N = 4 ist in Gleichung (2) in Abbildung 10 gezeigt.

Simulationen

Simulation der Irrfahrt

Abbildung 11 und 12 zeigen Simulationen der Irrfahrt mit Absorption am Rand, die analog zu Abbildung 2 durchgeführt werden:

• Die Menge der Zustände ist M = {-4, -3, ..., 3, 4}.
• Das Teilchen startet bei y = 0.
• Die Übergangswahrscheinlichkeiten werden verwendet, um den nächsten Zustand auszuwürfeln.
• Es werden jeweils n = 30 Zeitschritte betrachtet.
• In Abbildung 11 wird p = 0.5 gewählt, in Abbildung 12 ist p = 0.4 (dabei ist p die Wahrscheinlichkeit für einen Übergang nach oben y → y + 1).
• Im Diagramm wird jeweils der Zeitschritt angegeben, wann die Absorption stattfindet.
• Es werden jeweils 9 Simulationen durchgeführt.

Abbildung 11: Simulation für die Irrfahrt mit Absorption am Rand für N = 4, n = 30 und p = 0.5.

Abbildung 12: Simulation für die Irrfahrt mit Absorption am Rand für N = 4, n = 30 und p = 0.4.

Zeitentwicklung der Wahrscheinlichkeitsverteilung

Ist für die Zufallsvariable Y₀ kein fester Wert sondern eine Wahrscheinlichkeitsverteilung gegeben, so kann die Übergangsmatrix T verwendet werden, um die weiteren Verteilungen der Zufallsvariablen Y₁, Y₂, ... zu berechnen (analog zu Abbildung 8 und 9).

Abbildung 13 und 14 zeigt die Zeitentwicklung einer Wahrscheinlichkeitsverteilung, die zu Beginn bei y = 0 konzentriert ist – wieder für p = 0.5 beziehungsweise p = 0.4.

Abbildung 13: Zeitentwicklung einer Wahrscheinlichkeitsverteilung für die Irrfahrt mit Absorption am Rand für N = 4 und p = 0.5. Die Startverteilung ist in y = 0 konzentriert.

Abbildung 14: Zeitentwicklung der Wahrscheinlichkeitsverteilung unter den gleichen Bedingungen wie in Abbildung 13 aber mit p = 0.4.

Man erkennt in Abbildung 13 wie sich die Wahrscheinlichkeit über das zur Verfügung stehende Gebiet ausbreitet und sich an den Rändern anhäuft. In Abbildung 14 ist die Symmetrie dieser Ausbreitung gebrochen: Die Teilchen bevorzugen den Weg nach links (negative y) und die Wahrscheinlichkeit für den Zustand y = -4 wächst mehr als die Wahrscheinlichkeit für den Zustand y = 4.

In Abbildung 15 und 16 wird jetzt eine Startverteilung gewählt, die in den Zuständen -1, 0, 1 konzentriert ist, nämlich

P(Y₀ = -1) = P(Y₀ = 1) = 1/4, P(Y₀ = 0) = 1/2.

Abbildung 15: Zeitentwicklung einer Wahrscheinlichkeitsverteilung für die Irrfahrt mit Absorption am Rand für N = 4 und p = 0.5. Die Startverteilung ist in y = -1, 0, 1 konzentriert.

Abbildung 16: Zeitentwicklung der Wahrscheinlichkeitsverteilung unter den gleichen Bedingungen wie in Abbildung 15 aber mit p = 0.4.

Wieder erkennt man, dass sich die Wahrscheinlichkeiten mehr nach links (also zu negativen y) ausbreiten, wenn die Wahrscheinlichkeit p (für einen Sprung nach rechts) kleiner als 0.5 gewählt wird.

Ausblick auf weitere Fragestellungen

Bisher wurden einfache Beispiele für Markov-Ketten gezeigt und

• Simulationen für ihre Zeitentwicklung beziehungsweise
• die Zeitentwicklung einer Wahrscheinlichkeitsverteilung untersucht.

Spezielle Eigenschaften von Markov-Ketten wurden bisher noch nicht untersucht – an den vorgestellten Berechnen und Abbildungen lassen sich aber bereits zahlreiche Fragestellungen ablesen, die mit Markov-Ketten verbunden sind. Sie sollen hier kurz angedeutet, aber noch nicht im Detail diskutiert werden.

Klassifikation von Zuständen

Bei der in Abbildung 5 vorgestellten Markov-Kette sollte klar sein, dass jeder der 3 Zustände unendlich oft erreicht wird. Diese Eigenschaft hängt nicht davon ab, in welchem Zustand oder mit welcher Startverteilung die Markov-Kette startet. Ein Zustand, der – sobald er einmal erreicht wurde – unendlich oft erreicht wird, wird als rekurrenter Zustand bezeichnet.

Beim Beispiel der Irrfahrt ohne weitere Einschränkungen (siehe Abbildung 1 bis 3) ist es nicht klar, ob die (unendlich vielen) Zustände unendlich oft oder nur endlich oft erreicht werden. Dadurch, dass dem Teilchen "unendlich viel Platz" zur Verfügung steht, suggerieren die Abbildungen vielmehr, dass ein einmal erreichter Zustand entweder nie wieder oder höchstens endlich oft erreicht wird. Derartige Zustände werden als transiente Zustände bezeichnet.

Daher ist es eine relevante Frage, ob man Kriterien dafür angeben, ob ein Zustand rekurrent oder transient ist. Und es stellt sich dann sofort die nächste Frage: Wird die Entscheidung, ob ein Zustand rekurrent oder transient ist, allein mit Hilfe der Übergangsmatrix T getroffen oder hängt diese Entscheidung von der Startverteilung ab?

Bei der Irrfahrt mit Absorption treten zwei absorbierende Zustände auf, also Zustände, die nicht mehr verlassen werden, wenn sie einmal erreicht wurden. Der rekurrente Zustand unterscheidet sich vom absorbierenden Zustand dadurch, dass er zwar verlassen werden kann, dann aber doch wieder unendlich oft angenommen wird.

Es stellten sich dann die Fragen

• Gibt es noch weitere Zustände, die sich leicht charakterisieren lassen?
• Wie kann man Kriterien dafür formulieren, ob sie vorliegen oder nicht?

Verhalten von Markov-Ketten auf großen Zeitskalen

Eine weitere Eigenschaft von Markov-Ketten lässt sich aus dem Vergleich der Abbildungen 8 und 9 erahnen. Dort startet die Markov-Kette mit unterschiedlichen Startverteilungen. Aber schon nach 8 Zeitschritten sind die Verteilungen (auf der dargestellten Skala) kaum noch zu unterscheiden.

Man kann daher vermuten, dass sich eine "Grenzverteilung" einstellt, die unabhängig von der Startverteilung ist und die sich nur aus den Eigenschaften der Übergangsmatrix herleiten lässt.

Damit stellen sich sofort weitere Fragen:

• Gibt es zu jeder Übergangsmatrix eine Grenzverteilung?
• Gibt es Fälle, in denen die Grenzverteilung zusätzlich von der Startverteilung abhängt?
• Ist eine Grenzverteilung eindeutig bestimmt?

Algebraische Eigenschaften der Übergangsmatrix

Ein Kandidat für die Grenzverteilung ist natürlich ein Eigenvektor der Übergangsmatrix T zum Eigenwert 1:

μ·T = 1·μ = μ.

Eine derartige Verteilung wird auch als stationäre Verteilung bezeichnet.

Liegt eine stationäre Verteilung einmal vor, so wird sie beibehalten, da die Verteilung im nächsten Zeitschritt durch Multiplikation mit T berechnet wird.

Damit stellen sich sofort wieder weitere Fragen:

• Welche Bedeutung haben die Eigenwerte und Eigenvektoren der Übergangsmatrix?
• Lassen sich die oben beschriebenen Zustände (rekurrent, transient, absorbierend) aus der Übergangsmatrix ablesen?
• Oder allgemeiner: Welche algebraischen Eigenschaften der Übergangsmatrix sind für das Verhalten der Markov-Kette verantwortlich?