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:
- Eine irreduzible Markow-Kette besitzt genau dann eine stationäre Verteilung, wenn sie positiv rekurrent ist. Die Verteilung ist dann gegeben durch
- 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
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
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 des Random Walk Bearbeiten
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 Markov-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 Markov-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 Markov-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 Markov-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:
- Alle Zustände kommunizieren miteinander, da jeder Zustand die 0 erreichen kann und die 0 jeden Zustand erreicht. Demnach ist die Markow-Kette irreduzibel.
- 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.
- 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
- Ulrich Krengel: Einführung in die Wahrscheinlichkeitstheorie und Statistik. 8. Auflage, Vieweg, 2005. ISBN 978-3-8348-0063-3.
- Hans-Otto Georgii: Stochastik: Einführung in die Wahrscheinlichkeitstheorie und Statisti. 4. Auflage, de Gruyter, 2009. ISBN 978-3-11-021526-7.
- Christian Hesse: Angewandte Wahrscheinlichkeitstheorie. Eine fundierte Einführung mit über 500 realitätsnahen Beispielen und Aufgaben, Vieweg, Braunschweig/Wiesbaden 2003, ISBN 978-3-528-03183-1.
- Achim Klenke: Wahrscheinlichkeitstheorie. 2. Auflage. Springer-Verlag, Berlin/Heidelberg 2008, ISBN 978-3-540-76317-8.