Quelltext der Seite Stationäre Verteilung

Eine '''invariante Verteilung''' oder '''stationäre Verteilung''' ist ein Begriff aus der Theorie der [[Markow-Ketten]]; diese wiederum sind spezielle [[Stochastischer Prozess|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 [[Stationärer stochastischer Prozess|Stationarität eines stochastischen Prozesses]] oder [[Markow-Kette#Diskrete Zeit und höchstens abzählbar unendliche Zustandsmenge|stationären Übergangswahrscheinlichkeiten]].

== Definition ==
Gegeben sei eine homogene Markow-Kette <math>(X_n)_{n \in \N}</math> in diskreter Zeit mit höchstens abzählbarem Zustandsraum <math> Z </math>.
Dann heißt eine Verteilung <math> P_\pi </math> auf <math> Z </math> stationäre Verteilung, wenn
:<math> P_\pi(\{j\})=\sum_{i \in Z}P_\pi(\{i\})p(i,j) </math>
für alle <math> j \in Z </math> gilt, wobei <math> p(i,j)=P(X_n=j|X_{n-1}=i) </math> die [[Übergangswahrscheinlichkeit]] von Zustand <math>i</math> in den Zustand <math>j</math> ist (die unabhängig vom Zeitpunkt <math>n</math> ist). Im Falle eines endlichen Zustandsraumes entspricht dies
:<math> \pi M= \pi </math>,
wobei <math> M </math> die [[Übergangsmatrix]] ist und <math> \pi </math> ein [[Wahrscheinlichkeitsvektor]] als Zeilenvektor geschrieben. Damit sind die stationären Verteilungen in diesem Fall genau die [[Linkseigenvektor]]en der Übergangsmatrix zum Eigenwert 1, welche bezüglich der [[Summennorm]] normiert wurden.

== Existenz und Eindeutigkeit ==

Im Allgemeinen müssen keine stationären Verteilungen existieren. Beispiel hierfür sind [[transiente Markow-Kette]]n. 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 rekurrente Markow-Kette|positiv rekurrent]] ist. Die Verteilung ist dann gegeben durch
::<math> P_\pi(\{i\})=\frac{1}{\operatorname{E}(\tau_{ii})} </math>.
:Hierbei ist <math> \tau_{ii} </math> die [[Rekurrente Markow-Kette#Definition|Wiederkehrzeit]] in den Zustand <math>i</math>, 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 <math> M </math> bzw. dem normierten Eigenvektor der transponierten Übergangsmatrix <math> M^T </math> zum Eigenwert 1.
* Erfüllt eine Verteilung die [[Detailed Balance|Detailed-Balance-Gleichung]], so ist diese Verteilung eine stationäre Verteilung.

== Konvergenz ==
Eine irreduzible, positiv rekurrente Markow-Kette konvergiert genau dann gegen eine stationäre Verteilung, wenn sie aperiodisch ist. Konvergenz bedeutet hier, dass
:<math> \lim_{n\to\infty}P(X_n=i)=P_\pi(\{i\})</math>
für jede Startverteilung von <math> X_0 </math> und jeden Zustand <math> i \in Z </math> gilt.

Ist der Zustandsraum endlich, so konvergieren dann die Zeilen von <math> M^n </math> gegen die stationäre Verteilung.

Bei endlichen Zustandsräumen findet sich oft das Konvergenzkriterium, dass ein <math> k \in \mathbb{N} </math> existieren muss, so dass für die Übergangsmatrix <math> M </math> gilt, dass <math> M^k > 0 </math> 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
:<math> \lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1}P(X_n=i)=\frac{1}{\operatorname{E}(\tau_{ii})} = P_\pi(\{i\})</math>.
<math> </math>
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 <math> d </math> besitzen. Ist <math> K (i) </math> solch eine Menge mit einem beliebigen aber fixierten Zustand <math> i </math> aus dieser Menge. Dann lässt sich jeder Zustand <math> j </math> aus dieser Menge in einer eindeutigen Zahl <math> k </math> von Schritten von <math> i </math> aus erreichen. Ist die Teilmenge <math> T(i) </math> nun rekurrent, so gilt
:<math> \lim_{n \to \infty}p_{ij}^{nd+k}= \frac{d}{\operatorname{E}(\tau_{jj})} </math>.

=== Konvergenzgeschwindigkeit ===
Für einige Anwendungen ist vor allem interessant, wie schnell die stationäre Verteilung erreicht wird. Es lässt sich zeigen, dass wenn <math> 1=\lambda_1>|\lambda_2|\geq|\lambda_3|\dots </math> für <math> M </math> gilt, und alle Eigenwerte einfach sind, die folgende Abschätzung gilt:
:<math> \Vert v_0M^n-P_\pi\Vert \leq C|\lambda_2|^n</math>

Für eine beliebige Startverteilung <math> v_0 </math>. 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 ==
=== Endlicher Zustandsraum ===
==== Existenz ====
Betrachten wir die Markow-Kette mit der folgenden Übergangsmatrix:
:<math> M=
\begin{bmatrix}
1      & 0  & 0 & 0  & 0\\
0{,}1 & 0 & 0{,}8  & 0{,}1 &0\\
0  &0{,}5 & 0 & 0 & 0{,}5 \\
0      & 0   & 0 & 0 & 1 \\
0     & 0  & 0 & 1  & 0
 \end{bmatrix}</math>
Diese Markow-Kette hat zwei [[Absorbierender Zustand|absorbierende Mengen]]: <math> A= \{1\} </math> und <math> B=\{4,5\} </math>. 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 <math> \pi_1=(1,0,0,0,0) </math> und <math> \pi_2=(0,0,0,0{,}5,0{,}5) </math>. Somit ist hier die stationäre Verteilung nicht eindeutig.

==== Eindeutigkeit ====
[[Datei:Kolmogorov criterion dtmc.svg|mini|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 Matrix|irreduzible Übergangsmatrix]] ist dann
:<math>M = \begin{bmatrix}
0 & 0{,}5 & 0 & 0{,}5 \\
0{,}5 & 0 & 0{,}5 & 0 \\
0 & 0{,}5 & 0 & 0{,}5 \\
0{,}5 & 0 & 0{,}5 & 0 
\end{bmatrix}</math>
Der Satz von Perron-Frobenius garantiert die Eindeutigkeit des Eigenvektors, da die Matrix zusätzlich [[Doppelt-stochastische Matrix|doppelt-stochastisch]] ist, hat sie die stationäre Verteilung <math> \pi= \frac{1}{4}(1,1,1,1) </math>. Die Matrixpotenzen konvergieren aber nicht, insbesondere ist <math> M^{2n+1} = M</math> und
:<math>M^{2n} =M^2 = \begin{bmatrix}
0{,}5 & 0 & 0{,}5 & 0 \\
0 & 0{,}5 & 0 & 0{,}5 \\
0{,}5 & 0 & 0{,}5 & 0 \\
0 & 0{,}5 & 0 & 0{,}5 
\end{bmatrix}</math>
Betrachten wir aber nun die Mittelwerte, so konvergieren diese gegen die entsprechende Komponente der stationären Verteilung:
:<math> \lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1}P(X_n=1|X_0=1)=\lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1} p_{11}^n \rightarrow \frac{1}{4} \text{ für } N \to \infty</math>.
Dies folgt hier mithilfe der entsprechenden Einträge (im Beispiel die erste Zeile und Spalte) der obigen Übergangsmatrix.

==== Konvergenz ====
[[Datei:Simple markov chain.svg|mini|Eine einfache Markow-Kette]]
Betrachte die rechts dargestellte Markow-Kette mit den Übergangswahrscheinlichkeiten wie in der Übergangsmatrix angegeben:
:<math>M = \begin{bmatrix}
0{,}5 & 0 & 0{,}5  \\
0 {,}1 & 0{,}5 & 0{,}4 \\
0  & 0{,}5 & 0{,}5 
\end{bmatrix}</math>

Es gilt dann
:<math> M^2= \frac{1}{100}
\begin{bmatrix}
25 & 25 & 50  \\
10 & 45 & 45 \\
5  & 50 & 45 
\end{bmatrix}  >0 </math>
Somit ist die Markow-Kette irreduzibel (und damit auch positiv rekurrent), aperiodisch und konvergiert demnach gegen eine stationäre Verteilung. Ein Eigenvektor von <math> M^T </math> zum Eigenwert 1 ist <math> v=(1,5,5) </math>, Normierung auf 1 bzgl. der Summennorm liefert als eindeutige invariante Verteilung
:<math> \pi=\frac{1}{11} (1,5,5) = (0.0909,0.4545,0.4545)</math>.

Berechnet man die Matrixpotenzen, so stimmen bei <math> M^6 </math> schon zwei Nachkommastellen mit der exakten Lösung überein, bei <math> M^{12} </math> 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:
:<math> \lim_{n \to \infty} M^n= \frac{1}{11} \cdot
\begin{bmatrix}
1 & 5 & 5  \\
1 & 5 & 5 \\
1 & 5 & 5 
\end{bmatrix}
</math>
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
:<math> \operatorname{E}(\tau_{11})= \frac{1}{\pi_1}=11</math>.

==== Variante des Random Walk ====
[[Datei:Transition graph pac-man.png|mini|Ü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 <math>3\times3</math>-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 <math>2</math> und <math>8</math> (siehe nebenstehenden Übergangsgraphen).

Der Zustandsraum lautet <math>Z=</math>{<math>1,2,3,4,5,6,7,8,9</math>}. In der nun folgenden Übergangsmatrix <math>P</math> wurden Einträge mit Wahrscheinlichkeit <math>0</math> entfernt, um eine bessere Übersichtlichkeit zu erhalten:
:<math>P=\begin{pmatrix} & \frac{1}{2} & & \frac{1}{2}\\
\frac{1}{4} & & \frac{1}{4} & & \frac{1}{4}&&&\frac{1}{4}\\
& \frac{1}{2} & & & & \frac{1}{2}\\
\frac{1}{3} & & & & \frac{1}{3} & & \frac{1}{3}\\
& \frac{1}{4} & & \frac{1}{4} & & \frac{1}{4} & & \frac{1}{4}\\
& & \frac{1}{3} & & \frac{1}{3} & & & & \frac{1}{3}\\
& & & \frac{1}{2} & & & & \frac{1}{2}\\
& \frac{1}{4} & && \frac{1}{4} & & \frac{1}{4} & & \frac{1}{4}\\
& & & & & \frac{1}{2} & & \frac{1}{2}\end{pmatrix}</math>
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
:<math>\pi_{n}=\pi_{0}\cdot P^{n}</math>
für eine beliebige Startverteilung <math>\pi_{0}</math> ein großes <math>n</math> eingesetzt wird, weil die Matrixpotenzen wie im obigen Beispiel konvergieren. Um eine analytische Lösung zu berechnen, ist das lineare Gleichungssystem
:<math>\pi=\pi\cdot P</math>
nach <math>\pi</math> aufzulösen, unter der Nebenbedingung einer Zeilensumme von <math>1</math>. Das Einsetzen der naiven Lösung in diese Gleichung dient als Kontrolle. Die obige Gleichung ist äquivalent zu
:<math>(P^{T}-I)\cdot\pi^{T}=0</math>.
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
:<math>\pi=(7.7,15.4,7.7,11.5,15.4,11.5,7.7,15.4,7.7)</math>%.

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 <math>2</math> und <math>8</math>, welche aufgrund des Geheimwegs durchschnittlich genauso oft besucht werden wie das zentrale Spielfeld.

=== Abzählbar unendlicher Zustandsraum ===
Betrachten wir eine Markow-Kette auf dem Zustandsraum <math> Z=\mathbb{N}_0 </math> mit Übergangswahrscheinlichkeiten
:<math> p_{ij}=
\begin{cases}
\frac{1}{i+1}, & \text{ falls } j=i+1, \\
1-\frac{1}{i+1}, & \text{ falls } j=0, \\
0 & \text{sonst}.
\end{cases}
</math>

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 [[Kommunizierende 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 <math> \{2,3,4,\dotsc \} </math> und demnach hat die 0 die Periode 1, ist also aperiodisch. Aufgrund der Irreduzibilität ist dann auch die gesamte Markow-kette aperiodisch.
# Die erwartete Rückkehrzeit zu 0 ist gegeben durch
:<math> \operatorname{E}(\tau_{00})=\sum_{k=2}^\infty \frac{k}{(k-1)!}\cdot (1-\frac{1}{k})   =e </math>
Somit ist die 0 positiv rekurrent und aufgrund der Irreduzibilität der Markow-Kette auch die gesamte Kette positiv rekurrent.

Die Kette konvergiert also gegen eine von der Startverteilung unabhängige invariante Verteilung. Da wir bereits wissen, dass <math> P_\pi(\{0\})= \frac{1}{e}</math>, können wir die Definition als Rekursionsgleichung nutzen und folgern, dass <math> P_\pi(\{i\})=\frac{1}{i!e} </math> gilt. Dass die Berechnung der stationären Verteilung direkt möglich ist, ist aber die Ausnahme.

== Verwendung ==
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 des [[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 [[PageRank]]s 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|Markov-Chain-Monte-Carlo]]-Verfahren. Sie sind genau die Verteilungen, für die eine Stichprobe erstellt werden soll.

== Literatur ==
* [[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 Statistik'', 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

[[Kategorie:Markow-Prozesse]]