Markow-Kette

Eine Markow-Kette (oder auch Markow-Prozess, nach Andrei Andrejewitsch Markow, andere Schreibweisen: Markov-Kette, Markoff-Kette) ist ein spezieller stochastischer Prozess. Man unterscheidet eine Markow-Kette in diskreter und in stetiger Zeit. Markow-Ketten in stetiger Zeit werden meistens als Markow-Prozess bezeichnet. Das Spezielle einer Markow-Kette ist die Eigenschaft, dass durch Kenntnis einer begrenzten Vorgeschichte ebensogute Prognosen über die zukünftige Entwicklung möglich sind wie bei Kenntnis der gesamten Vorgeschichte des Prozesses. Im Falle einer Markow-Kette erster Ordnung wird hierfür sogar nur Kenntnis über den momentanen Zustand benötigt (Gedächtnislosigkeit). 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.

Das Paradebeispiel für einen stetigen Markow-Prozess mit den reellen Zahlen als Zustandsraum ist die brownsche Bewegung, während eine populäre zeitdiskrete Markow-Kette mit endlichem Zustandsraum die zufällige Irrfahrt auf einem diskreten Kreis, also $Z_{/nZ}$ , ist. Hierbei startet man in der Äquivalenzklasse $[0]$ der 0, und bewegt sich in jedem Schritt aus dem aktuellen Zustand $[i]$ mit Wahrscheinlichkeit $1/2$ nach $[i+1]$ und mit Wahrscheinlichkeit $1/2$ nach $[i-1]$ . Wirft man eine Münze immer wieder und notiert bei jedem Wurf, wie oft bislang 'Kopf' erschienen ist, so ist die Abfolge der so gebildeten Zahlen ebenfalls ein zeitdiskreter Markov-Prozess, diesmal mit Zustandsraum $S=\{0,1,2,\dots \}$ .

Markow-Ketten eignen sich sehr gut um zufällige Zustandsänderungen eines Systemes 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 gedächtnislosen Bedienzeiten.

Diskrete Zeit und endliche Zustandsmenge

Im Fall einer endlichen Grundmenge $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 folgender Eigenschaft:

Fehler beim Parsen (SVG (MathML kann über ein Browser-Plugin aktiviert werden): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „http://localhost:6011/de.wikipedia.org/v1/“:): {\displaystyle 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}})}

Dies ist im üblichen Sinne zu verstehen: Sobald eine der beiden Seiten wohldefiniert ist, ist es auch die andere, und beide stimmen überein. Die Gleichung bedeutet, dass die Wahrscheinlichkeit für den Zustand zum Zeitpunkt $t+1$ nur von den $n$ vorhergehenden Zuständen abhängt. Von besonderem Interesse sind Markow-Ketten erster Ordnung, also Ketten mit

P(X_{t+1}=x_{t+1}\mid X_{t}=s_{j_{t}},X_{t-1}=s_{j_{t-1}},\dots ,X_{0}=x_{0})=P(X_{t+1}=s_{j_{t+1}}\mid X_{t}=s_{j_{t}})

.

Dies 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 Vektor im $R^{m}$ mit der Eigenschaft, dass $\pi _{i}\geq 0$ für alle $i$ und $\sum _{i=1}^{m}\pi _{i}=1$ . Dieser Vektor induziert per $P(\{s_{i}\}=\pi _{i})$ eine Wahrscheinlichkeitsverteilung 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 Numerierung des Zustandsraumes abhängt, und daher nur modulo Basisumordnung eindeutig ist.)

Wir betrachten nun im Folgenden eine zeitdiskrete Markowkette $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, heisst Anfangsverteilung. Die Übergangswahrscheinlichkeiten (engl. transition probabilities) sind gegeben durch

p_{ij}(t):=P(X_{t+1}=s_{j}\mid X_{t}=s_{i})

,

i,j=1,\dots ,m

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

(p_{ij}(t))=\mathbf {M} ={\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.

Für eine homogene Markov-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_{ij}^{n}:=M^{n}(i,j)

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

P(X_{n}=i)=(M^{n}\cdot \mu )(i)

.

Eine Verteilung $\pi ^{*}$ heisst stationär (bezüglich der Markow-Kette), falls

\pi ^{*}=M\cdot \pi ^{*}

Dies lässt sich so interpretieren: Würfelt man gemäß $\pi ^{*}$ einen Zustand aus, und wendet nun die durch die homogene Markowkette 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 Markovkette. 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 Markovkette also stets gleich dem Anfangswert ist), sind sogar alle Verteilungen stationär. Es gibt aber eine grosse Klasse von interessanten Markovprozessen, für die es genau eine stationäre Verteilung gibt:

Eine irreduzible, aperiodische homogene Markow-Kette besitzt genau eine stationäre Verteilung $\pi ^{*}$ ; diese kann man auf zwei Arten beschreiben: Ist erstens $M$ die Übergangsmatrix, so konvergiert die Folge der Matrizen $M^{n}$ gegen die Matrix, welche in jeder Zeile die Verteilung $\pi ^{*}$ einbeschrieben hat. 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$ . Die erste Beziehung lässt sich auch noch anders formulieren: Für die Verteilungen von $X_{n}$ hat man : $\lim _{n}P(X_{n}=s_{i})=\lim _{n}(M^{n}\cdot \mu )(i)=\pi ^{*}(i)$ , die Verteilungen der Markovkette konvergieren also gegen die stationäre Verteilung.

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&1/2&1/2\\1/2&0&1/2\\1/2&1/2&0\end{pmatrix}}

Wir überlegen zunächst, was die durchschnittliche Wartezeit von einem Punkt zu einem von diesem 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 1/2 ist sie 1, mit Wahrscheinlichkeit 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}=1/2+1/2(\mu _{1,0}+1)

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}^{*}=1/3$ . Aus Symmetriegründen gilt dann auch $\pi _{1}^{*}=1/3=\pi _{2}^{*}$ . Hier ist also die Gleichverteilung $(1/3,1/3,1/3)$ stationär.

Oft hat man in Anwendungen eine Modellierung vorliegen, in welcher die Zustandsänderungen der Markovkette 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)

Bei dieser Disziplin werden zu Beginn eines Zeitschrittes die Bedienungen gestartet. Danach treffen neue Forderungen ein und erst am Ende eines Zeitschrittes treten die Bedienenden auf.

Der Vorteil dieser Disziplin ist, dass Forderungsankünfte immer vor einem möglichen Bedienende eintreffen und damit die BASTA Eigenschaft gilt. Mit Hilfe dieser Eigenschaft lassen sich für Ankünfte, die als Bernoulli-Prozess modeliert 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)

Im Fall von Departure First treffen zu Beginn eines Zeitschrittes Forderungen in das System ein. Darauf folgt der Start von Bedienzeiten und am Ende eines Zeitschrittes das Ende von Bedienzeiten.

Bei diesem Ansatz gilt die BASTA 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.

Kontinuierliche Zeit

Analog lässt sich die Markow-Kette auch für kontinuierliche Zeit bilden. Hierbei wird davon ausgegangen, dass es zu bestimmten Zeitpunkten zu sprunghaften Zustandsänderungen kommt.

Sei $(X(t))_{t\geq 0}$ ein stochastischer Prozess mit kontinuierlicher Zeit aber immer noch diskretem Zustandsraum. Dann gilt bei einer homogenen Markow-Kette $\forall n\in \mathbb {N}$ , $0<t_{1}<\ldots <t_{n}$ , $k>0$ , $i_{1},\ldots ,i_{n},j\in S$ :

P(X(t_{n}+k)=j|X(t_{n})=i_{n},\ldots ,X(t_{1})=i_{1})=

P(X(t_{n}+k)=j|X(t_{n})=i_{n})=

P(X(k)=j|X(0)=i_{n})=:p_{i,j}(k)

Auch hier lässt sich eine Übergangsmatrix bilden: $P(k):=[p_{i,j}(k)]$ , $k>0$ , $P(0):=I$ (Hierbei steht $I$ wie üblich für die Einheitsmatrix).

Offenbar existieren jedoch im stetigen Fall kontinuierlich viele Übergangsmatrizen, da diese von $k$ abhängen. Jedoch ist eine Stückelung möglich, sodass man nur sehr kleine $k_{i}$ kennen muss:

k=\sum _{i=1}^{n}k_{i}\Rightarrow P(k)=P(k_{1})\cdot P(k_{2})\cdot \cdot \cdot P(k_{n})

Eine elegantere Lösung bietet sich jedoch unter der Voraussetzung $\lim _{k\to 0,k>0}P(k)=I$ . Dann nämlich bietet sich ein infinitesimaler Ansatz über eine Intensitätsmatrix $Q$ an:

Q:=\lim _{k\to 0,k>0}{P(k)-I \over k}

.

Denn aus $Q$ lässt sich jedes $P(k)$ wieder ableiten, denn es gilt:

P(k)=\exp(k\cdot Q)

.

Auch lässt sich der stationäre Zustand als Lösung des folgenden Gleichungssystems bestimmen:

\pi ^{*}\cdot Q={\overrightarrow {0}}

.

Anwendungen in der Bioinformatik

Markow-Ketten werden in der Bioinformatik dazu verwendet, Sequenzabschnitte auf bestimmte Eigenschaften zu untersuchen. Hierzu zählt z. B. das Vorhandensein von CpG-Inseln, da in diesen die Übergangswahrscheinlichkeiten zwischen C-G und G-C erhöht sind.

Siehe auch

Literatur

Pierre Brémaud: Markov Chains. Springer Verlag, 1999, ISBN 0387985093
Ehrhard Behrends: Introduction to Markov Chains. Vieweg, 2000, ISBN 3-528-06986-4

Weblinks