Markow-Kette n-ter Ordnung

Gelegentlich werden auch Markow-Ketten ${\displaystyle n}$-ter Ordnung untersucht. Bei diesen hängt der zukünftige Zustand von den ${\displaystyle n}$ vorherigen Zuständen ab:

${\displaystyle {\begin{aligned}&\ P(X_{t+1}=s_{j_{t+1}}\mid X_{t}=s_{j_{t}},X_{t-1}=s_{j_{t-1}},\dots ,X_{0}=s_{j_{0}})\\=&\ P(X_{t+1}=s_{j_{t+1}}\mid X_{t}=s_{j_{t}},\dots ,X_{t-n+1}=s_{j_{t-n+1}}).\end{aligned}}}$

In diesem Sinn sind die oben betrachteten Markow-Ketten Ketten erster Ordnung. Ketten höherer Ordnung werden hier aber nicht weiter betrachtet.

Endlicher Zustandsraum

Wir versuchen, mithilfe einer Markow-Kette eine einfache Wettervorhersage zu bilden. Dazu kodieren wir 1 = „die Sonne scheint“, 2 = „es ist bewölkt“ und 3 = „es regnet“. Als Zeitschritt wählen wir einen Tag. Aus Erfahrung wissen wir, dass wenn heute die Sonne scheint, die Wahrscheinlichkeit, dass es morgen regnet, ungefähr 80 % ist und die Wahrscheinlichkeit, dass es bewölkt ist, ca. 20 % beträgt. Außerdem treffen wir die Annahme, dass sich diese Wahrscheinlichkeiten nicht ändern, die Markow-Kette also homogen ist. Somit wissen wir nun

${\displaystyle P(X_{t+1}=i|X_{t}=1)={\begin{cases}0&{\text{ falls }}\quad i=1\\0{,}2&{\text{ falls }}\quad i=2,\\0{,}8&{\text{ falls }}\quad i=3\end{cases}}}$

Ist es aber bewölkt, so regnet es mit Wahrscheinlichkeit 0,5 am folgenden Tag und mit Wahrscheinlichkeit von 0,5 scheint die Sonne. Es gilt also

${\displaystyle P(X_{t+1}=i|X_{t}=2)={\begin{cases}0{,}5&{\text{ falls }}\quad i=1\\0&{\text{ falls }}\quad i=2,\\0{,}5&{\text{ falls }}\quad i=3\end{cases}}}$

Regnet es heute, so scheint danach nur mit Wahrscheinlichkeit von 0,1 die Sonne und mit Wahrscheinlichkeit von 0,9 ist es bewölkt. Damit folgt für die Übergangswahrscheinlichkeiten

${\displaystyle P(X_{t+1}=i|X_{t}=3)={\begin{cases}0{,}1&{\text{ falls }}\quad i=1\\0{,}9&{\text{ falls }}\quad i=2,\\0&{\text{ falls }}\quad i=3\end{cases}}}$

Damit ist die Markow-Kette vollständig beschrieben. Anschaulich lassen sich solche Markow-Ketten gut durch Übergangsgraphen darstellen, wie oben abgebildet. Ordnet man nun die Übergangswahrscheinlichkeiten zu einer Übergangsmatrix an, so erhält man

${\displaystyle M={\begin{bmatrix}0&0{,}2&0{,}8\\0{,}5&0&0{,}5\\0{,}1&0{,}9&0\end{bmatrix}}}$

Wir wollen nun wissen, wie sich das Wetter entwickeln wird, wenn heute die Sonne scheint. Dazu geben wir die Anfangsverteilung ${\displaystyle X_{0}}$ vor in Form des stochastischen Startvektors ${\displaystyle v_{0}=(1;0;0)}$. Wir starten also im Zustand 1. Multiplikation von rechts mit der Übergangsmatrix liefert ${\displaystyle v_{1}=v_{0}M=(0;0{,}2;0{,}8)}$. Mit achtzigprozentiger Wahrscheinlichkeit regnet es also. Am dritten Tag gilt ${\displaystyle v_{3}=v_{0}M^{3}\approx (0{,}3700;0{,}1260;0{,}5040)}$. Somit ist die Regenwahrscheinlichkeit am dritten Tag knapp über 50 % und die Sonnenwahrscheinlichkeit knapp unter 40 %. Somit lässt sich für jedes vorgegebene Wetter am Starttag die Regen- und Sonnenwahrscheinlichkeit an einem beliebigen Tag angeben. Auch Fragestellungen wie: „Heute scheint die Sonne. Wie groß ist die Wahrscheinlichkeit, dass es vor drei Tagen geregnet hat?“ lassen sich mit dem Satz von Bayes beantworten.

Abzählbar unendlicher Zustandsraum

Definieren wir nun eine Markow-Kette auf dem Zustandsraum ${\displaystyle \mathbb {Z} }$ und mit Übergangswahrscheinlichkeiten

${\displaystyle P(X_{t+1}=i|X_{t}=j)={\begin{cases}p&{\text{ falls }}\quad i=j+1\\q&{\text{ falls }}\quad i=j-1,\\0&{\text{sonst}}\end{cases}}}$

wobei ${\displaystyle p+q=1}$, ${\displaystyle p,q\geq 0}$ gelten. Dies lässt sich so veranschaulichen: Startet man an einem beliebigen Punkt, so bewegt man sich entweder mit einer Wahrscheinlichkeit von ${\displaystyle p}$ nach „rechts“, sprich, begibt sich zur Nachfolgerzahl. Mit Wahrscheinlichkeit ${\displaystyle q}$ wandert man nach „links“ zur Vorgängerzahl. Entsprechend diesem Vorgehen irrt man dann über die Zahlengerade. Daher wird diese Markow-Kette auch Irrfahrt auf ${\displaystyle \mathbb {Z} }$ genannt. Gelegentlich wird für solche Markow-Ketten auch der Begriff des Random Walk verwendet. Starten wir im Zustand 0, so ist mit den obigen Übergangswahrscheinlichkeiten

${\displaystyle P^{0}(X_{1}=i)={\begin{cases}p&{\text{ falls }}\quad i=1,\\q&{\text{ falls }}\quad i=-1,\\0&{\text{ sonst.}}\end{cases}}}$

Daraus folgen dann ${\displaystyle P^{0}(X_{2}=-2)=q^{2}}$, ${\displaystyle P^{0}(X_{2}=0)=2pq}$, ${\displaystyle P^{0}(X_{2}=2)=p^{2}}$. Hier zeigt sich ein gewisser Zusammenhang zur Binomialverteilung. Außerdem gilt aber auch ${\displaystyle P^{0}(X_{2}=-1)=P^{0}(X_{2}=1)=0}$. Gewisse Zustände können also nur zu bestimmten Zeiten besucht werden; diese Eigenschaft wird Periodizität genannt.

Ist allgemeiner ${\displaystyle (Z_{n})_{n\in \mathbb {N} }}$ eine Folge unabhängiger und identisch verteilter Zufallsvariablen mit Werten in ${\displaystyle \mathbb {Z} }$, dann ist durch

${\displaystyle X_{t}=\sum _{n=1}^{t}Z_{n}}$

eine Markow-Kette ${\displaystyle (X_{t})_{t\in \mathbb {N} }}$ mit Übergangswahrscheinlichkeiten ${\displaystyle p_{ij}=P(Z_{1}=j-i)}$ gegeben.

Klassische Beispiele

Einige der bekanntesten Markow-Ketten sind

• Die Irrfahrt auf ${\displaystyle \mathbb {Z} ^{D}}$ sowie Verallgemeinerungen auf Graphen.
• Der Galton-Watson-Prozess, welcher die Fortpflanzung einer sich eingeschlechtlich fortpflanzenden Spezies modelliert
• Das Ehrenfest-Modell zur Modellierung der Diffusion von Molekülen durch Membrane.

Irreduzibilität

Irreduzibilität ist wichtig für die Konvergenz gegen einen stationären Zustand. Vereinfacht gesagt ist eine Markow-Kette irreduzibel, wenn für alle Zustände ${\displaystyle i}$ und ${\displaystyle j}$ gilt, dass die Wahrscheinlichkeit, in endlicher Zeit von ${\displaystyle i}$ nach ${\displaystyle j}$ zu kommen, echt positiv ist. Gilt dies für fixierte ${\displaystyle i}$ und ${\displaystyle j}$, so sagt man auch, dass ${\displaystyle i}$ und ${\displaystyle j}$ miteinander kommunizieren.

Periodizität

Periodische Markow-Ketten erhalten trotz aller Zufälligkeit des Systems gewisse deterministische Strukturen. Ist eine Markow-Kette periodisch mit Periode ${\displaystyle d}$, so kann sie höchstens alle ${\displaystyle d}$ Zeitschritte wieder zu ihrem Startpunkt zurückkehren (dies ist aber nicht zwingend).

Rekurrenz und Transienz

Die Rekurrenz und die Transienz beschreiben das Langzeitverhalten einer Markow-Kette. Wird ein Zustand fast sicher unendlich oft besucht, so heißt er rekurrent, ansonsten transient. Sind alle Zustände rekurrent (transient), so heißt die Markow-Kette rekurrent (transient). Wichtiges Hilfsmittel zur Bestimmung von Rekurrenz ist die Green-Funktion.

Absorbierende Zustände

Absorbierende Zustände sind Zustände, welche nach dem Betreten nicht wieder verlassen werden können. Hier interessiert man sich insbesondere für die Absorptionswahrscheinlichkeit, also die Wahrscheinlichkeit, einen solchen Zustand zu betreten.

Stationäre Verteilungen

In der Anwendung sind oftmals besonders stationäre Verteilungen interessant. Gibt man diese Verteilungen als Startverteilung von ${\displaystyle X_{0}}$ vor, so sind alle darauf folgenden Verteilungen der Zustände ${\displaystyle X_{n}}$ für beliebiges ${\displaystyle n}$ gleich der Startverteilung. Interessant ist hier die Frage, wann solche Verteilungen existieren und wann eine beliebige Verteilung gegen solch eine stationäre Verteilung konvergiert.

Reversibilität

Bei reversiblen Markow-Ketten lässt sich nicht unterscheiden, ob sie in der Zeit vorwärts oder rückwärts laufen, sie sind also invariant unter Zeitumkehr. Insbesondere folgt aus Reversibilität die Existenz eines stationären Zustandes.

Arrival First (AF)

Bei dieser Disziplin wird zu Beginn eines Zeitschrittes das Bedienen gestartet. Danach treffen neue Forderungen ein, und erst am Ende eines Zeitschrittes tritt das Bedien-Ende auf.

Der Vorteil dieser Disziplin ist, dass Forderungsankünfte immer vor einem möglichen Bedien-Ende eintreffen und damit die PASTA-Eigenschaft (Poisson Arrivals See Time Averages) gilt. Mit Hilfe dieser Eigenschaft lassen sich für Ankünfte, die als Bernoulli-Prozess modelliert sind, unter anderem sehr einfach für Bediensysteme wichtige Eigenschaften wie die Verlustwahrscheinlichkeit ${\displaystyle P_{V}}$ berechnen.

Als Nachteil kann eine Forderung, die im Zeitschlitz ${\displaystyle z_{t}}$ eintrifft, frühestens in ${\displaystyle z_{t+1}}$ fertig bedient werden. Dies führt unter Umständen zu einer höheren Anzahl von benötigten Warteplätzen im modellierten System.

Departure First (DF)

Im Fall von Departure First kommen zu Beginn eines Zeitschrittes Forderungen im System an. Darauf folgt der Start von Bedienzeiten und am Ende eines Zeitschrittes das Ende von Bedienzeiten.

Bei diesem Ansatz gilt die PASTA Eigenschaft nicht mehr, was im Allgemeinen zu komplizierteren Berechnungen als im Falle von Arrival First führt. Eine Forderung kann im selben Zeitschritt eintreffen und fertig bedient werden.