Markow-Kette

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Markow-Kette mit drei Zuständen und unvollständigen Verbindungen

Eine Markow-Kette (engl. Markov chain, auch Markow-Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov-Kette, Markoff-Kette, Markof-Kette) ist ein spezieller stochastischer Prozess. Eine Markow-Kette ist darüber definiert, dass durch Kenntnis einer begrenzten Vorgeschichte ebenso gute Prognosen über die zukünftige Entwicklung möglich sind wie bei Kenntnis der gesamten Vorgeschichte des Prozesses.

Man unterscheidet Markow-Ketten unterschiedlicher Ordnung. Im Falle einer Markow-Kette erster Ordnung heißt das: Die Zukunft des Systems hängt nur von der Gegenwart (dem aktuellen Zustand) und nicht von der Vergangenheit ab. Die mathematische Formulierung im Falle einer endlichen Zustandsmenge benötigt lediglich den Begriff der diskreten Verteilung sowie der bedingten Wahrscheinlichkeit, während im zeitstetigen Falle die Konzepte der Filtration sowie der bedingten Erwartung benötigt werden.

Ziel bei der Anwendung von Markow-Ketten ist es, Wahrscheinlichkeiten für das Eintreten zukünftiger Ereignisse anzugeben.

Die Begriffe Markow-Kette und Markow-Prozess werden im Allgemeinen synonym verwendet. Zum Teil sind aber zur Abgrenzung mit Markow-Ketten Prozesse in diskreter Zeit (diskreter Zustandsraum) gemeint und mit Markow-Prozessen Prozesse in stetiger Zeit (stetiger Zustandsraum).

Beispiele[Bearbeiten]

Numerisches Beispiel einer einfachen Markow-Kette mit den zwei Zuständen E und A.

Markow-Ketten eignen sich sehr gut, um zufällige Zustandsänderungen eines Systems zu modellieren, falls man Grund zu der Annahme hat, dass die Zustandsänderungen nur über einen begrenzten Zeitraum hinweg Einfluss aufeinander haben oder sogar gedächtnislos sind. Ein Beispiel sind Auslastungen von Bediensystemen mit gedächtnislosen Ankunfts- und Bedienzeiten.

Stetige Markow-Kette[Bearbeiten]

Das Paradebeispiel für einen stetigen Markow-Prozess mit den reellen Zahlen als Zustandsraum ist der Wiener-Prozess.

Diskrete, endliche Markow-Kette[Bearbeiten]

Ein populäres Beispiel für eine zeitdiskrete Markow-Kette mit endlichem Zustandsraum ist die zufällige Irrfahrt (engl. Random Walk) auf einem diskreten Kreis, modelliert durch den Restklassenring \Bbb Z/n\Bbb Z. Dies führt zum endlichen Zustandsraum S = \left\{ 0,1,2, \dots ,(n-1) \right\} . Hierbei startet man in der Äquivalenzklasse  [0] der 0, und bewegt sich in jedem Schritt aus dem aktuellen Zustand  [i] jeweils mit Wahrscheinlichkeit  1/2 nach  [i+1] oder nach  [i-1] (also anschaulich: einen Schritt nach links oder nach rechts).

Eine (endliche) zufällige Irrfahrt mit zwei absorbierenden Zuständen (ganz links und ganz rechts). Die Zustände "-1", "0" und "1" haben jeweils die gleiche Übergangswahrscheinlichkeit (0.5) zu den Zuständen links und rechts von ihnen.

Bei einem anderen Beispiel wirft man eine Münze immer wieder und notiert bei jedem Wurf, wie oft bislang 'Kopf' erschienen ist. Die Abfolge der so gebildeten Zahlen bildet ebenfalls eine (zeitdiskrete) Markow-Kette, diesmal mit Zustandsraum S = \{0,1,2, \dots \} mit jeweils der Übergangswahrscheinlichkeit  1/2 für den Übergang von  [i] nach  [i+1] und für das Verbleiben in  [i] .

Diskrete, unendliche Markow-Kette: Lamplighter[Bearbeiten]

Bei einer zufälligen Irrfahrt auf \Bbb Z^d wird zu jedem Zeitpunkt eine Lampe am jeweiligen Standort ein- oder ausgeschaltet. Der aktuelle Zustand zum Zeitpunkt n des Markow-Prozesses wird durch zwei Variablen beschrieben: den aktuellen Ort P_n des Lamplighters und die Lampenkonfiguration \eta (z. B. durch eine Abbildung von \Bbb Z^d nach \{0,1\}). Dann ist (Pn, η) ein Markow-Prozess und sogar (Pn) alleine ist ein Markow-Prozess; für sich alleine ist (η) aber kein Markow-Prozess. Ein weiteres Beispiel für eine Markow-Kette mit unendlichem Zustandsraum ist der Galton-Watson-Prozess, der oftmals zur Modellierung von Populationen genutzt wird.

Diskrete Zeit und endliche Zustandsmenge[Bearbeiten]

Definition[Bearbeiten]

Im Fall einer endlichen Zustandsmenge  S = \{s_1, \dots, s_m\} und der diskreten Zeit  t=0,1,2,\dots  ist eine Markow-Kette n-ter Ordnung auf S ein stochastischer Prozess  X = (X_t)_{t =0,1,\dots}  mit Werten in S und der Eigenschaft

\begin{align}
  &\ 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{align}

Die Gleichung bedeutet, dass die Wahrscheinlichkeitsverteilung für den Zustand zum Zeitpunkt t+1 nur von den n vorhergehenden Zuständen, aber nicht von noch weiter zurückliegenden abhängt. Von besonderem Interesse sind Markow-Ketten erster Ordnung, also Ketten mit

\begin{align}
 &\ 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}}).
 \end{align}

Das lässt sich so interpretieren, dass das zukünftige Verhalten des Systems nur vom aktuellen Zustand und nicht von den vorigen Zuständen abhängt. Diese Eigenschaft bezeichnet man als Gedächtnislosigkeit oder auch Markow-Eigenschaft. Üblicherweise meint man mit dem Begriff Markow-Kette lediglich eine Markow-Kette erster Ordnung; dies wird auch im Rest des Artikels so gehandhabt.

Ein Wahrscheinlichkeitsvektor  \pi ist ein (als Zeilenvektor geschriebener) Vektor im  \R^{m} mit der Eigenschaft, dass  \pi_i \ge 0 für alle  i und  \sum_{i=1}^m \pi_i = 1 . Solche Vektoren entsprechen mittels  P(\{s_i\}) = \pi_i  genau den Wahrscheinlichkeitsverteilungen auf dem Zustandsraum  S . Der Einfachheit halber sagen wir zu  \pi auch Verteilung. (Man beachte, dass – genau wie bei der unten eingeführten Übergangsmatrix – die zugeordnete Verteilung von der Nummerierung des Zustandsraumes abhängt, und daher nur modulo Basisumordnung eindeutig ist.)

Wir betrachten nun im Folgenden eine zeitdiskrete Markow-Kette  X = (X_t)_{t=0,1,2, \dots}  auf einem endlichen Zustandsraum  S = \{s_1, \ldots, s_m \}. Der Wahrscheinlichkeitsvektor  \mu , der durch

 \mu_i  = P(X_0 = s_i)

gegeben ist, heißt Anfangsverteilung. Die Übergangswahrscheinlichkeiten sind gegeben durch

p_{ij}(t):=P(X_{t+1}=s_j \mid X_t=s_i),\quad i,j=1,\dots,m

und werden in einer Übergangsmatrix (auch Transitionsmatrix) zusammengefasst:

(p_{ij}(t)) = \mathbf{M}(t)= \begin{pmatrix} p_{11}(t) & \dots & p_{1m}(t) \\ \vdots & \ddots & \vdots \\ p_{m1}(t) & \dots & p_{mm}(t) \end{pmatrix}

[Falls einige bedingte Wahrscheinlichkeiten nicht definiert sind, wird anstelle derselben einfach 0 in die Matrix geschrieben.]

Sind die Übergangswahrscheinlichkeiten unabhängig von dem Zeitpunkt t, gilt also p_{ij} = p_{ij}(t) für alle t, so spricht man von einer homogenen Markow-Kette mit Übergangsmatrix \mathbf{M}.

n-Schritt-Übergangswahrscheinlichkeiten und Stationarität[Bearbeiten]

Für eine homogene Markow-Kette kann die Wahrscheinlichkeit, in n Schritten vom Zustand i in den Zustand j überzugehen, mit Hilfe der n-ten Potenz der Übergangsmatrix berechnet werden:

p^n_{ij} := P(X_n = s_j \mid X_0 = s_i) = \mathbf{M}^n(i,j)

Hieraus folgt auch leicht, dass die Verteilung von  X_n durch  \mu und \mathbf{M} bereits eindeutig bestimmt ist,

 P(X_n = s_{j}) = (\mu \cdot \mathbf{M}^n)(j)\,,

d. h., die Verteilung von X_n ist durch den Wahrscheinlichkeitsvektor \mu \mathbf{M}^n gegeben.

Eine Verteilung  \pi^* heißt stationär (bezüglich der Markow-Kette), falls gilt

 \pi^* = \pi^* \cdot \mathbf{M}\,.

Dies lässt sich so interpretieren: Würfelt man gemäß  \pi^* einen Zustand aus, und wendet nun die durch die homogene Markow-Kette beschriebene zufällige Transition auf diesen Zustand an, so erhält man zwar im Allgemeinen ein anderes Ergebnis, aber die Wahrscheinlichkeitsverteilung bleibt dieselbe; der durch  \pi^* beschriebene Zufall ist also invariant unter der Transformation der Markow-Kette. Anders gesagt: Würde man anstatt mit  \mu mit  \pi^* als Startverteilung beginnen, so hätte man einen stationären Prozess vorliegen. (Manchmal wird auch, etwas ungenau, von einem stationären Zustand gesprochen.)

Es kann durchaus mehr als eine stationäre Verteilung geben; im degenerierten Extremfall, dass die Transition durch die Einheitsmatrix beschrieben wird (die Markow-Kette also stets gleich dem Anfangswert ist), sind sogar alle Verteilungen stationär. Es gibt aber eine große Klasse von interessanten Markowprozessen, für die es genau eine stationäre Verteilung gibt:

Eine irreduzible, aperiodische homogene Markow-Kette besitzt genau eine stationäre Verteilung  \pi^* , vgl. den Satz von Perron-Frobenius; diese kann man auf zwei Arten beschreiben: Ist erstens  \mathbf{M} die Übergangsmatrix, so konvergiert die Folge der Matrizen  \mathbf{M}^n gegen die Matrix, welche in jeder Zeile die Verteilung  \pi^* einbeschrieben hat. Diese Beziehung lässt sich auch noch anders formulieren: Für die Verteilungen von  X_n hat man  \lim_{n\to\infty}  P(X_n = s_i) = \lim_{n\to\infty} (\mu \mathbf{M}^n)(i) = \pi^*(i) , die Verteilungen der Markow-Kette konvergieren also gegen die stationäre Verteilung.

Bezeichnet man zweitens mit  \mu_{i,j} die durchschnittliche Wartezeit, die der Prozess braucht, um von dem Punkt  s_i zu dem Punkt  s_j zu gelangen, so folgt  \pi^*(i) = 1/\mu_{i,i} für alle  i .

Beispiel: Als ein Beispiel, wie die zweite Beziehung genutzt werden kann, betrachten wir die (symmetrische) zufällige Irrfahrt auf der Menge  \{0,1,2\}; hier ist die Übergangsmatrix gegeben durch

 
\begin{pmatrix} 0 & \frac{1}{2} & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} & 0 \end{pmatrix}

Wir überlegen zunächst, wie lange die durchschnittliche Wartezeit für einen Wechsel von einem Punkt zu einem anderen, verschiedenen ist. Weil die Matrix invariant unter Permutationen der Elemente des Zustandsraumes ist, ist diese Wartezeit immer die gleiche. Betrachten wir also die Wartezeit von Punkt 0 zu Punkt 1. Mit Wahrscheinlichkeit  \frac{1}{2} ist sie 1, mit Wahrscheinlichkeit  \frac{1}{2} treffen wir im ersten Zug anstatt der '1' die '2'. In diesem Falle müssen wir nun von der '2' zur '0'; die Wartezeit hierfür ist jedoch im Mittel dieselbe wie für den Weg von '1' zur '0'. Wir erhalten also die Beziehung  \mu_{1,0} = \dfrac{1}{2} + \dfrac{1}{2}(1 + \mu_{1,0}) Diese Gleichung hat die eindeutige Lösung  \mu_{1,0} = 2 . Nun betrachten wir die durchschnittliche Wartezeit, um von '0' nach '0' zu gelangen. Der Prozess wird in Schritt 1 in jedem Fall auf die '1' oder die '2' wandern; in beiden Fällen beträgt die erwartete Restwartezeit, wie oben errechnet, 2 Schritte, wir erhalten also  \mu_{0,0} = 3 und damit  \pi^*_{0} = \frac{1}{3} . Aus Symmetriegründen gilt dann auch  \pi^*_{1} = \frac{1}{3} = \pi^*_{2}. Hier ist also die Gleichverteilung \left(\frac{1}{3}, \frac{1}{3}, \frac{1}{3}\right) stationär.

Rekurrent und transient[Bearbeiten]

Ein Zustand s \in S heißt rekurrent, wenn die Markow-Kette bei Start in s mit Wahrscheinlichkeit 1, also fast sicher, irgendwann in diesen Zustand zurückkehrt.

Für die formale Definition bezeichne

\tau_s := \inf\{n \geq 1 : X_n = s\}

den ersten Rückkehrzeitpunkt der Kette in den Zustand s mit der Konvention, dass \tau_s = \infty ist, wenn die Kette niemals in den Zustand s zurückkehrt. Dann heißt s rekurrent, wenn P(\tau_s < \infty \mid X_0 = s) = 1 gilt, anderenfalls heißt der Zustand transient.

Rekurrenz und Transienz lassen sich auch folgendermaßen charakterisieren: Es bezeichne f_s^{(n)} ist die Wahrscheinlichkeit, nach n Schritten das erste Mal vom Zustand s wieder in den Zustand s zu gelangen, also

f_s^{(n)} = P(X_n=s, X_k \ne s, k = 1, 2, \dotsc, n-1 \mid X_0 = s) = P(\tau_s = n \mid X_0 = s).

Sei f_s = \sum_{n=1}^\infty f_s^{(n)} die Wahrscheinlichkeit bei einem Start in s nach irgendeiner Anzahl von Schritten nach s zurückzukehren. Falls f_s < 1, so ist der Zustand s transient. Falls f_s = 1, so ist der Zustand s rekurrent.[1][2]

Eine Markow-Kette heißt rekurrent (transient), falls jeder Zustand rekurrent (transient) ist.

Modellierung[Bearbeiten]

Oft hat man in Anwendungen eine Modellierung vorliegen, in welcher die Zustandsänderungen der Markow-Kette durch eine Folge von zu zufälligen Zeiten stattfindenden Ereignissen bestimmt wird (man denke an obiges Beispiel von Bediensystemen mit zufälligen Ankunfts- und Bedienzeiten). Hier muss bei der Modellierung entschieden werden, wie das gleichzeitige Auftreten von Ereignissen (Ankunft vs. Erledigung) behandelt wird. Meist entscheidet man sich dafür, künstlich eine Abfolge der gleichzeitigen Ereignisse einzuführen. Üblicherweise unterscheidet man dabei zwischen den Möglichkeiten Arrival First und Departure First.

Arrival First (AF)[Bearbeiten]

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.

Mk af.png

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 P_V rechnen.

Als Nachteil kann eine Forderung die im Zeitschlitz z_t eintrifft frühestens in 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)[Bearbeiten]

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.

Mk df.png

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.

Stetige Zeit und diskreter Zustandsraum[Bearbeiten]

Analog lässt sich die Markow-Kette auch für kontinuierliche Zeit und diskreten Zustandsraum bilden. Das heißt, dass sich zu bestimmten Zeitpunkten der Zustand sprunghaft ändert.

Sei (X(t))_{t \ge 0} ein stochastischer Prozess mit kontinuierlicher Zeit und diskretem Zustandsraum. Dann gilt bei einem homogenen Markow-Prozess

\forall n \in\N,\ 0 < t_1 < \dotsb < t_n,\ t > 0,\ i_1, \ldots, i_n, j \in S:
\begin{align}
 P(X(t_n + t) = j \mid X(t_n) = i_n, \ldots, X(t_1) = i_1)
 &= P(X(t_n + t) = j \mid X(t_n) = i_n)\\
 &= P(X(t) = j \mid X(0) = i_n)\\
 &=: p_{i_n,j}(t)
\end{align}

Auch hier lassen sich Übergangsmatrizen bilden: P(t) := [ p_{i,j} (t) ] für alle t > 0 und P(0) := I (Hierbei steht I wie üblich für die Einheitsmatrix).

Es gilt die Chapman-Kolmogorow-Gleichung und (P(t))_{t\geq0} ist entsprechend eine Halbgruppe, die unter gewissen Voraussetzungen einen infinitesimalen Erzeuger, nämlich die Q-Matrix hat.

Diskrete Zeit und allgemeiner Zustandsraum[Bearbeiten]

Markow-Ketten können auch auf allgemeinen messbaren Zustandsräumen definiert werden. Ist der Zustandsraum nicht abzählbar so benötigt man hierzu den stochastischen Kern als Verallgemeinerung zur Übergangsmatrix. Dabei ist eine Markow-Kette durch die Startverteilung auf dem Zustandsraum und den stochastischen Kern (auch Übergangskern oder Markowkern) schon eindeutig bestimmt.

Auf dem Gebiet der allgemeinen Markow-Ketten gibt es noch viele offene Probleme. Gut erforscht sind lediglich Harris-Ketten.

Anwendungen[Bearbeiten]

Markow-Ketten werden in unterschiedlichen Bereichen verwendet.

Literatur[Bearbeiten]

  • Philipp von Hilgers, Wladimir Velminski (Hg.): Andrej A. Markov. Berechenbare Künste, Zürich/Berlin: diaphanes, 2007. ISBN 978-3-935300-69-8
  • Andrei A. Markov, An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains, trans. Classical Text in Translation. David Link, Science in Context 19.4 (2006): S. 591–600.
  • Pierre Brémaud: Markov Chains. Springer Verlag, 1999, ISBN 0-387-98509-3
  • Ehrhard Behrends: Introduction to Markov Chains. Vieweg, 2000, ISBN 3-528-06986-4
  • Olle Häggström: Finite Markov Chains and Algorithmic Applications. Cambridge University Press, 2002
  • Daniel W. Stroock: An introduction to Markov processes. Second edition. Graduate Texts in Mathematics, 230. Springer, Heidelberg, 2014. ISBN 978-3-642-40522-8; 978-3-642-40523-5

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise[Bearbeiten]

  1. Allen, Arnold O.: Probability, Statistics, and Queueing Theory with Computer Science Applications, Academic Press Inc., San Diego, 1990, 2nd ed., Seite 226
  2. Mathar, R.; Pfeifer, D.: Stochastik für Informatiker, Teubner Stuttgart 1990, Seite 190