Direkt zum Inhalt

Lexikon der Mathematik: Markow-Kette

auf einem Wahrscheinlichkeitsraum \(({\rm{\Omega }},{\mathfrak{A}},P)\) definierter Markow-Prozeß (Xt)tI mit endlichem oder abzählbar unendlichem Zustandsraum S.

Dabei ist I zumeist die Menge ℕ0 oder \({{\mathbb{R}}}_{0}^{+}\). Im ersten Fall spricht man von einer Markow-Kette mit diskreter, im zweiten Fall von einer MarkowKette mit stetiger Zeit. Ist S endlich, so nennt man auch die Markow-Kette endlich. Die (elementare) Markow-Eigenschaft wird bei einer Markow-Kette mit diskreter Zeit in der Regel in der Form \begin{eqnarray}\begin{array}{ll}P({X}_{n+1}={i}_{n+1}|{X}_{0}={i}_{0},\ldots, {X}_{n}={i}_{n})\\ \quad \quad =P({X}_{n+1}={i}_{n+1}|{X}_{n}={i}_{n})\end{array}\end{eqnarray} für alle n ∈ ℕ0 und alle i0,...,in+1S mit P(X0 = i0,...,Xn = in) > 0 angegeben. Die Verteilung von X0 heißt die Start- oder Anfangsverteilung der Markow-Kette. Für i, jS und s, tI mit st werden die bedingten Wahrscheinlichkeiten \begin{eqnarray}{p}_{ij}(s,t):=P({X}_{t}=j|{X}_{s}=i)\end{eqnarray} vom Zustand i zum Zeitpunkt s in den Zustand j zum Zeitpunkt t überzugehen, als Übergangswahrscheinlichkeiten bezeichnet und zur sogenannten Matrix der Übergangswahrscheinlichkeiten P(s,t) ≔ (pij(s, t))i,jS zusammengefaßt. Die Matrix P(s,t) ist eine stochastische Matrix. Streng genommen ist pij(s, t) nur für P(Xs = i) > 0 definiert. Hier wie im folgenden kann man die mittels bedingter Wahrscheinlichkeiten definierten Größen aber beliebig konsistent festsetzen, falls die Wahrscheinlichkeit der Bedingung verschwindet. Es gelten die Chapman-Kolmogorow-Gleichungen, die in Matrixform als \begin{eqnarray}{P}_{(s,t)}={P}_{(s,r)}{P}_{(r,t)}\end{eqnarray} für alle srt geschrieben werden können. Gilt für alle s, t, u, vI mit st, uv und ts = vu für beliebige i, jS die Beziehung pij(s, t) = pij(u, v), so heißt die Markow-Kette stationär oder zeitlich homogen. Anschaulich bedeutet diese Eigenschaft, daß die bedingte Wahrscheinlichkeit für den Übergang vom Zustand i zum Zeitpunkt s in den Zustand j zum Zeitpunkt t nur von der Differenz ts, nicht aber von den konkreten Zeitpunkten abhängt.

Im folgenden beschränken wir uns auf zeitlich homogene Markow-Ketten \({({X}_{t})}_{t\in {{\mathbb{N}}}_{0}}\) mit diskreter Zeit. Die zeitliche Homogenität ist hier zu der Eigenschaft äquivalent, daß für alle i, jS eine Zahl pij mit P(Xn+1 = j|Xn = i) = pij für alle n ∈ ℕ0 existiert. Die durch P ≔ (pij)i,jS = P(0,1) definierte Matrix P heißt die Übergangsmatrix von \({({X}_{t})}_{t\in {{\mathbb{N}}}_{0}}\). Zusammen mit der Startverteilung bestimmt sie \({({X}_{t})}_{t\in {{\mathbb{N}}}_{0}}\) bis auf Äquivalenz eindeutig. Identifiziert man für jedes n ∈ ℕ0 die Verteilung von Xn mit dem Zeilenvektor \({\pi }^{(n)}={({\pi }_{i}^{(n)})}_{i\in S}\), dessen Komponenten durch \({\pi }_{i}^{(n)}:=P({X}_{n}=i)\) definiert sind, so gilt \({\pi }^{(n)}={\pi }^{(0)}{\text{P}}^{n}\), wobei Pn das n-fache Produkt von P mit sich selbst bezeichnet. Diese Gleichung bleibt insbesondere für n = 0 richtig, wenn man P0 als die Einheitsmatrix auffaßt. Weiter gilt \({\text{P}}^{n}={({p}_{i,j}^{(n)})}_{i,j\in S}\), wobei die Übergangswahrscheinlichkeit für n Schritte \({p}_{i,j}^{(n)}\) durch \({p}_{i,j}^{(n)}:={p}_{ij}(0,n)\) definiert ist.

Ein Zustand j heißt von i erreichbar, in Zeichen ij, falls ein n ≥ 0 mit \({p}_{i,j}^{(n)}\gt 0\) existiert. Gilt sowohl ij als auch ji, so bezeichnet man i und j als verbundene oder kommunizierende Zustände und schreibt ij. Die Relation ij ist eine Äquivalenzrelation. Ein Zustand i heißt wesentlich, wenn für jeden Zustand j mit ij auch ji gilt. Eine Menge CS heißt abgeschlossen, falls pij = 0 für alle iC und jC gilt. Besteht eine abgeschlossene Menge C aus nur einem Zustand i, so nennt man i einen absorbierenden Zustand. \({({X}_{t})}_{t\in {{\mathbb{N}}}_{0}}\) heißt irreduzibel, falls S die einzige nicht-leere abgeschlossene Menge ist und reduzibel andernfalls. Die Kette ist genau dann irreduzibel, wenn alle Zustände aus S untereinander verbunden sind. Die Periode di eines Zustands i mit ii ist durch \(\text{ggT}\{n:{p}_{i,i}^{(n)}\gt 0\}\) definiert. Zustände mit Periode di = 1 heißen aperiodisch, solche mit di ≥ 2 periodisch. Man nennt die Kette aperiodisch, wenn jeder Zustand aperiodisch ist, und periodisch mit Periode d ≥ 2, wenn jeder Zustand iS periodisch mit Periode di = d ist. Weiterhin spielen beim Studium zeitlich homogener Markow-Ketten die Begriffe der Rekurrenz und Transienz eine wichtige Rolle.

Als Beispiel betrachten wir eine zeitlich homogene Markow-Kette \({({X}_{t})}_{t\in {{\mathbb{N}}}_{0}}\) mit Zustandsraum S = {1, 2, 3, 4} und Übergangsmatrix \begin{eqnarray}\text{P}=\left(\begin{array}{cccc}0 & 1 & 0 & 0\\ \frac{1}{2} & 0 & \frac{1}{2} & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\end{array}\right).\end{eqnarray}

Da die Menge {3, 4} abgeschlossen ist, handelt es sich hierbei um eine reduzible Kette. Jeder Zustand besitzt die Periode 2. Die Beziehungen zwischen den Zuständen lassen sich mit Hilfe gerichteter Graphen veranschaulichen. Die Abbildung zeigt den der Matrix P entsprechenden Graphen.

Abbildung 1 zum Lexikonartikel Markow-Kette
© Springer-Verlag GmbH Deutschland 2017
 Bild vergrößern

Gerichteter Graph zur Übergangsmatrix P

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte