Markow-Kette

Eine Markov-Kette (nach Andrej Andrejewitsch Markow) ist ein diskreter Stochastischer Prozess der der folgenden Bedingung genügt:

$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})$

d.h. dass die Wahrscheinlichkeit für den Zustand zum Zeitpunkt t+1 nur von dem Zustand zum Zeitpunkt t abhängt. (Es gibt allerdings auch Markow-Ketten n-ter Ordnung, bei denen n vorausgegangene Zeitschritte berücksichtigt werden).

Die Übergangswahrscheinlichkeiten für m verschiedene Zustände

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

werden in einer Übergangsmatrix (auch Transitionsmatrix) zusammengefasst:

$p_{ij}=\mathbf {m} ={\begin{pmatrix}p_{11}&\dots &p_{1m}\\\vdots &\vdots &\vdots \\p_{m1}&\dots &p_{mm}\end{pmatrix}}$

Bei einer Markow-Kette erster Ordnung kann der Vektor der Zustandswahrscheinlichkeiten nach t Zeitschritten einfach durch Multiplikation des Anfangszustandsvektor mit der potenzierten Übergangsmatrix berechnet werden:

$\mathbf {p} _{t}=\mathbf {M} ^{t}\mathbf {p_{0}}$

Man nennt eine Markow-Kette "stationär", wenn die Übergangszustände für alle 'i' und 'j' unabhängig von 't' sind. Diese stationären Zustände werden teilweise erst asymptotisch erreicht.

See also:

• HMM

Links

• http://www.cl.uni-heidelberg.de/kurs/ss02/stat/html/page019.html