Markovkette

Eine Markovkette ist ein stochastischer Prozess mit diskreter Zeit und einem abzählbaren Zustandsraum. Die Markov-Eigenschaft besagt, dass die Verteilung des nächsten Zustands nur vom aktuellen Zustand abhängt und nicht von der Vergangenheit. Formal sei X_n der Zustand nach n Schritten mit X_n ∈ S. Dann gilt P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, ..., X_0=i_0) = P(X_{n+1}=j | X_n=i) = p_{ij}. Wenn die Wahrscheinlichkeiten p_{ij} zeitunabhängig sind, spricht man von einer homogener Markovkette; ansonsten von einer inhomogenen Kette.

Der Übergang zwischen Zuständen wird durch die Übergangsmatrix P beschrieben, deren Zeilen die Wahrscheinlichkeiten p_{i\cdot} enthalten. Die Summe der Wahrscheinlichkeiten in jeder Zeile ist 1. Für unendliche Zustandsräume gilt die gleiche Bedingung. Der Zustandsraum lässt sich in Kommunizierklassen gliedern; zwei Zustände kommunizieren, wenn es Pfade beider Richtungen gibt. Eine Kette ist irreduzibel, wenn alle Zustände miteinander kommunizieren. Zustände können recurrend oder transient sein; absorbierende Zustände sind solche, von denen aus kein Austritt möglich ist (P_{ii}=1).

Eine wichtige Größe ist die stationäre Verteilung π, die pi = pi P erfüllt und deren Einträge sich zu 1 summieren. Ist die Kette irreduzibel und aperiodisch, konvergieren die Einträge von P^n gegen π, unabhängig von der Anfangsverteilung. In praktischen Anwendungen werden Gleichungen der Art πP=π, Balancegleichungen und, bei absorbierenden Ketten, die Fundamentalmatrix benutzt.

Anwendungen finden sich in der Warteschlangentheorie, dem Web-Navigator-Modell (PageRank), Genetik, Sprache und Finanzmodellen. Markovketten dienen außerdem als Grundlagenkonzept für Monte-Carlo-Verfahren und statistische Modellierung diskreter Prozesse.