Stationäre Verteilung

Begriff aus der Theorie der Markow-Ketten
(Weitergeleitet von Invariante Verteilung)

Invariante Verteilung oder stationäre Verteilung ist ein Begriff aus der Theorie der Markow-Ketten. Diese sind spezielle stochastische Prozesse und damit Untersuchungsobjekte der Stochastik.

Eine Markow-Kette besitzt eine stationäre Verteilung genau dann, wenn es eine Startverteilung gibt, die sich im Zeitverlauf nicht ändert.

Stationäre Verteilungen sind nicht zu verwechseln mit der Stationarität eines stochastischen Prozesses oder mit stationären Übergangswahrscheinlichkeiten.

Definition

Bearbeiten

Gegeben sei eine homogene Markow-Kette   in diskreter Zeit mit höchstens abzählbarem Zustandsraum  . Dann heißt eine Verteilung   auf   stationäre Verteilung, wenn

 

für alle   gilt, wobei   die Übergangswahrscheinlichkeit von Zustand   in den Zustand   ist (die unabhängig vom Zeitpunkt   ist). Im Falle eines endlichen Zustandsraumes entspricht dies

 ,

wobei   die Übergangsmatrix ist und   ein Wahrscheinlichkeitsvektor als Zeilenvektor geschrieben. Damit sind die stationären Verteilungen in diesem Fall genau die Linkseigenvektoren der Übergangsmatrix zum Eigenwert 1, die bezüglich der Summennorm normiert wurden.

Existenz und Eindeutigkeit

Bearbeiten

Im Allgemeinen müssen keine stationären Verteilungen existieren. Beispiel hierfür sind transiente Markow-Ketten. Diese besitzen nie stationäre Verteilungen. Umgekehrt lässt sich auch zeigen, dass irreduzible Markow-Ketten höchstens eine stationäre Verteilung besitzen. Für die Eindeutigkeit der stationären Verteilungen gelten folgende Aussagen:

 .
Hierbei ist   die Wiederkehrzeit in den Zustand  , wenn in diesem gestartet wurde.
  • Im Falle eines endlichen Zustandsraumes sind Irreduzibilität der Markow-Kette und Irreduzibilität der Übergangsmatrix äquivalent. Daraus folgt aber sofort mit dem Satz von Perron-Frobenius, dass eine eindeutige invariante Verteilung (bzw. Linkseigenvektor) existiert und damit, dass die Markow-Kette positiv-rekurrent ist. Somit folgt hier aus Irreduzibilität positive Rekurrenz.
  • Demnach hat eine irreduzible Markow-Kette mit endlichem Zustandsraum immer eine stationäre Verteilung. Diese entspricht genau dem normierten Linkseigenvektor zum Eigenwert 1 der Übergangsmatrix   bzw. dem normierten Eigenvektor der transponierten Übergangsmatrix   zum Eigenwert 1.
  • Erfüllt eine Verteilung die Detailed-Balance-Gleichung, so ist diese Verteilung eine stationäre Verteilung.

Konvergenz

Bearbeiten

Eine irreduzible, positiv rekurrente Markow-Kette konvergiert genau dann gegen eine stationäre Verteilung, wenn sie aperiodisch ist. Konvergenz bedeutet hier, dass

 

für jede Startverteilung von   und jeden Zustand   gilt.

Ist der Zustandsraum endlich, so konvergieren dann die Zeilen von   gegen die stationäre Verteilung.

Bei endlichen Zustandsräumen findet sich oft das Konvergenzkriterium, dass ein   existieren muss, sodass für die Übergangsmatrix   gilt, dass   ist. Dies entspricht der Überprüfung der Matrix auf Aperiodizität und Irreduzibilität.

Verzichtet man auf die Aperiodizität, so lässt sich folgende Aussage zeigen: Ist eine Markow-Kette irreduzibel und rekurrent, so ist

 .

Der Mittelwert der Eintrittswahrscheinlichkeiten konvergiert also komponentenweise gegen die stationäre Verteilung.

Allgemeiner gilt: Ist die Markow-Kette nicht irreduzibel, so zerfällt sie in mehrere Teilmengen von Zuständen, die miteinander kommunizieren und alle dieselbe Periode   besitzen. Sei   so eine Menge mit einem beliebigen, aber fixierten Zustand   aus dieser Menge. Dann lässt sich jeder Zustand   aus dieser Menge in einer eindeutigen Zahl   von Schritten von   aus erreichen. Ist die Teilmenge   nun rekurrent, so gilt

 .

Konvergenzgeschwindigkeit

Bearbeiten

Für einige Anwendungen ist vor allem interessant, wie schnell die stationäre Verteilung erreicht wird. Es lässt sich zeigen, dass wenn   für   gilt und alle Eigenwerte einfach sind, die folgende Abschätzung gilt:

 

für eine beliebige Startverteilung  . Wichtigster Einflussfaktor auf die Konvergenzgeschwindigkeit ist also der betragsmäßig zweitgrößte Eigenwert.

Es lassen sich noch vergleichbare Aussagen für schwächere Voraussetzungen an die Übergangsmatrix zeigen, dabei müssen aber Korrekturterme für die Jordanblöcke eingeführt werden.

Beispiele

Bearbeiten

Endlicher Zustandsraum

Bearbeiten

Existenz

Bearbeiten

Betrachten wir die Markow-Kette mit der folgenden Übergangsmatrix:

 

Diese Markow-Kette hat zwei absorbierende Mengen:   und  . Da diese Zustände nicht mehr verlassen werden können, haben sie einen Einfluss auf die Existenz der stationären Verteilungen. Dies zeigt sich auch in den normierten Eigenvektoren. Diese sind   und  . Somit ist hier die stationäre Verteilung nicht eindeutig.

Eindeutigkeit

Bearbeiten
 
Die untersuchte Markow-Kette

Betrachten wir die Markow-Kette mit dem rechts dargestellten Übergangsgraph. Der Einfachheit halber setzen wir alle Übergangswahrscheinlichkeiten auf 0,5. Die Markow-Kette ist irreduzibel, da man sich von jedem Zustand in maximal zwei Schritten in jeden anderen Zustand bewegen kann. Sie ist aber auch periodisch, da eine Rückkehr zum Startpunkt nur zu geraden Zeitpunkten möglich ist. Die ebenfalls irreduzible Übergangsmatrix ist dann

 

Der Satz von Perron-Frobenius garantiert die Eindeutigkeit des Eigenvektors. Da die Matrix zusätzlich doppelt-stochastisch ist, hat sie die stationäre Verteilung  . Die Matrixpotenzen konvergieren aber nicht, insbesondere ist   und

 

Betrachten wir aber nun die Mittelwerte, so konvergieren diese gegen die entsprechende Komponente der stationären Verteilung:

 

Dies folgt hier mithilfe der entsprechenden Einträge (im Beispiel die erste Zeile und Spalte) der obigen Übergangsmatrix.

Konvergenz

Bearbeiten
 
Eine einfache Markow-Kette

Betrachte die rechts dargestellte Markow-Kette mit den Übergangswahrscheinlichkeiten wie in der Übergangsmatrix angegeben:

 

Es gilt dann

 

Somit ist die Markow-Kette irreduzibel (und damit auch positiv rekurrent), aperiodisch und konvergiert demnach gegen eine stationäre Verteilung. Ein Eigenvektor von   zum Eigenwert 1 ist  , Normierung auf 1 bzgl. der Summennorm liefert als eindeutige invariante Verteilung

 .

Berechnet man die Matrixpotenzen, so stimmen bei   schon zwei Nachkommastellen mit der exakten Lösung überein, bei   schon mehr als vier Nachkommastellen. Umgekehrt kann man aus der als Linkseigenvektor berechneten stationären Verteilung bei Konvergenz sofort den Grenzwert der Matrixpotenzen angeben, da diese zeilenweise gegen die stationäre Verteilung konvergieren:

 

Aus der stationären Verteilung kann man auch die erwartete Rückkehrzeit berechnen, diese ist genau der Kehrwert der entsprechenden Komponente der Verteilung. Somit ist hier die durchschnittliche Zeit beim Start in 1 bis zur Rückkehr

 .

Variante einer stochastischen Irrfahrt

Bearbeiten
 
Übergangsgraph mit Übergangswahrscheinlichkeiten exemplarisch für die Zustände 1, 5, 6 und 8. Es gibt einen Geheimgang zwischen den Zuständen 2 und 8 für beide Richtungen.

Die Spielfigur Pac-Man frisst in einem Labyrinth kleine Kugeln und Kirschen und wird dabei von Gespenstern verfolgt. Der Einfachheit halber ist die Spielwelt in diesem Beispiel ein kleines  -Gitter und die Monster bewegen sich rein zufällig. Jedes horizontal und vertikal angrenzende Spielfeld ist mit gleicher Wahrscheinlichkeit der nächste Aufenthaltsort des Gespensts, mit Ausnahme eines Geheimgangs zwischen den Zuständen   und   (siehe nebenstehenden Übergangsgraphen).

Der Zustandsraum lautet  . In der nun folgenden Übergangsmatrix   wurden Einträge mit Wahrscheinlichkeit   entfernt, um eine bessere Übersichtlichkeit zu erhalten:

 

Diese Markow-Kette ist irreduzibel, da sich die Gespenster in endlicher Zeit von jedem beliebigen Zustand in jeden beliebigen Zustand begeben können. Dank des Geheimgangs sind hierfür nur maximal drei Zustandswechsel nötig. Durch den Geheimgang ist die Markow-Kette auch aperiodisch, weil die Monster sowohl in einer geraden als auch in einer ungeraden Anzahl an Zustandswechseln von jedem beliebigen Zustand in jeden beliebigen Zustand wechseln können. Ohne den Geheimgang wäre die Markow-Kette periodisch, weil dann ein Übergang von einem geraden in einen geraden Zustand bzw. von einem ungeraden in einen ungeraden Zustand nur in einer geraden Anzahl von Zustandswechseln möglich wäre.

Wegen der Irreduzibilität und Aperiodizität gibt es genau eine stabile Gleichgewichtsverteilung, welche die Markow-Kette nach einer unendlich langen Zeit annimmt. Die Aufenthaltswahrscheinlichkeiten für die einzelnen Zustände ändern sich nach langer Zeit (fast) nicht mehr. Die stationäre Verteilung lässt sich naiv bestimmen, indem in die Gleichung

 

für eine beliebige Startverteilung   ein großes   eingesetzt wird, weil die Matrixpotenzen wie im obigen Beispiel konvergieren. Um eine analytische Lösung zu berechnen, ist das lineare Gleichungssystem

 

nach   aufzulösen, unter der Nebenbedingung einer Zeilensumme von  . Das Einsetzen der naiven Lösung in diese Gleichung dient als Kontrolle. Die obige Gleichung ist äquivalent zu

 .

Die Übergangsmatrix wird demnach transponiert und die Einheitsmatrix subtrahiert. Der gesuchte Vektor der Zustandswahrscheinlichkeiten ist nun ein Spaltenvektor. Die Lösung des linearen Gleichungssystems ergibt:

 

Die Gespenster halten sich demnach am häufigsten in der Mitte auf, weniger oft am Rand und am seltensten in der Ecke. Eine Ausnahme bilden die Randzustände   und  , die aufgrund des Geheimwegs durchschnittlich genauso oft besucht werden wie das zentrale Spielfeld.

Abzählbar unendlicher Zustandsraum

Bearbeiten

Betrachten wir eine Markow-Kette auf dem Zustandsraum   mit Übergangswahrscheinlichkeiten

 

Mit einer gewissen Wahrscheinlichkeit steigt man also zu einer Zahl eins höher auf. Falls dies nicht geschieht, startet man wieder am Nullpunkt. Es gilt:

  1. Alle Zustände kommunizieren miteinander, da jeder Zustand die 0 erreichen kann und die 0 jeden Zustand erreicht. Demnach ist die Markow-Kette irreduzibel.
  2. Die Rückkehrzeiten in die 0 sind   und demnach hat die 0 die Periode 1, ist also aperiodisch. Aufgrund der Irreduzibilität ist dann auch die ganze Markow-kette aperiodisch.
  3. Die erwartete Rückkehrzeit zu 0 ist gegeben durch:
 

Somit ist die 0 positiv rekurrent und aufgrund der Irreduzibilität der Markow-Kette auch die ganze Kette positiv rekurrent.

Die Kette konvergiert also gegen eine von der Startverteilung unabhängige invariante Verteilung. Da wir bereits wissen, dass  , können wir die Definition als Rekursionsgleichung nutzen und folgern, dass   gilt. Dass die Berechnung der stationären Verteilung direkt möglich ist, ist aber die Ausnahme.

Verwendung

Bearbeiten

Stationäre Verteilungen haben zahlreiche Anwendungen in der Praxis. Stellt man sich die Markow-Kette als zufällig durch einen Graphen wandernden Punkt vor, so ist die i-te Komponente der stationäre Verteilung genau die relative Wahrscheinlichkeit, ihn im Zustand i anzutreffen. Ein Beispiel hierfür ist das Ehrenfest-Modell. Es modelliert die Diffusion von Molekülen durch eine Membran. Der stationäre Zustand ist dann genau die Konzentration, wenn sich ein Diffusionsgleichgewicht eingestellt hat. Ein anderes Beispiel ist die Berechnung des PageRanks mittels des Zufalls-Surfer-Modells. Hier modelliert die Markow-Kette das Verhalten eines Internetnutzers: Mit einer bestimmten Wahrscheinlichkeit wählt er einen der Links auf der Homepage, auf der er sich befindet, aus, andernfalls wählt er eine andere Homepage per Browser aus. Die stationäre Verteilung ist dann die relative Wahrscheinlichkeit, dass der Zufallssurfer auf eine bestimmte Seite trifft. Dies ist dann ein Maß für die Wichtigkeit dieser Seite und auch der normierte PageRank dieser Seite.

Des Weiteren spielen stationäre Verteilungen eine wichtige Rolle bei Markov-Chain-Monte-Carlo-Verfahren. Sie sind genau die Verteilungen, für die eine Stichprobe erstellt werden soll.

Literatur

Bearbeiten