Markow-Kette

Eine Markow-Kette (nach Andrei Andrejewitsch Markow) ist ein spezieller stochastischer Prozess. Man unterscheidet eine Markow-Kette im diskreten und eine im stetigen Fall. Das speziell Markow'sche an einer Markow-Kette ist folgende Eigenschaft: Kennt man erst einmal die Gegenwart des Prozesses, dann lassen sich Prognosen über die Zukunft des Prozesses nicht durch zusätzliche Kenntnisse seiner Vergangenheit verbessern. Das nennt man auch Gedächtnislosigkeit des Prozesses. Die mathematische Formulierung dieser Eigenschaft ist, vor allem bei kontinuierlichen Prozessen, recht aufwendig. Das Paradebeispiel für einen stetigen Markow-Prozess ist die Brown'sche Bewegung.

Diskreter Fall

Im diskreten Fall ist eine Markow-Kette n-ter Ordnung folgendermaßen definiert:

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

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

das heißt, dass die Wahrscheinlichkeit für den Zustand zum Zeitpunkt t+1 nur von den n vorhergehenden Zuständen abhängt. Dies bezeichnet man als Gedächtnislosigkeit oder auch Markow-Eigenschaft. Von besonderem Interesse sind Markow-Ketten erster Ordnung, also Ketten mit

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

=P(X_{t+1}=x_{t+1}\mid X_{t}=x_{t})

,

die auch im Folgenden betrachtet werden.

Eine solche besitzt immer eine Anfangsverteilung $\mu$ , auf Grund welcher man in den ersten Zustand gelangt, und des weiteren Übergangswahrscheinlichkeiten.

Ist der Zustandsraum endlich mit m Zuständen, werden die Übergangswahrscheinlichkeiten (engl. transition probability) für m verschiedene Zustände

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

,

i,j=1,\dots ,m

in einer Übergangsmatrix (auch Transitionsmatrix) zusammengefasst:

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

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.

Bei einer homogenen Markow-Kette erster Ordnung, 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)

Man nennt eine Markow-Kette stationär, wenn die Wahrscheinlichkeit, sich in einem Zustand zu befinden, unabhängig vom Zeitpunkt ist, formal

\pi _{j}^{*}:=\lim _{n\rightarrow \infty }\mu (i)p_{ij}(n)

.

Der stationäre Zustand stellt gewissermaßen sicher, dass sich das System eingependelt hat. Er exisitiert genau dann, wenn die Übergangsmatrix regulär ist. Die Kriterien hier für sind die Irreduzibilität, Aperiodizität und das die Markow-Kette rekurrent ist. Rekurrent d.h. die WS, dass man von einen Zustand nach n Schritten wider in diesen gelangt ist 1.

Diese stationären Zustände werden teilweise erst asymptotisch erreicht, oft jedoch auch gar nicht.

Das stochastische Verhalten einer homogenen Markow-Kette wird einerseits durch die Startwahrscheinlichkeit und andererseits durch die Übergangsmatrix festgelegt.

Fall mit kontinuierlicher 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 Porzeß mit kontinuierlicher Zeit aber immer noch diskretem Zustandsraum. Dann gilt bei einer homogenen Markow-Kette $\forall n\in \mathbb {N}$ , $0<t_{1}<...<t_{n}$ , $k>0$ , $i_{1},...,i_{n},j\in S$ :

P(X(t_{n}+k)=j|X(t_{n})=i_{n},...,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 infinitisimaler Ansatz über eine Intensitätsmatrix $Q$ an: