Mathematik Stochastik – Markov-Ketten

P(X_{n+1}=j | X_n=i, X_{n-1}=i_{n-1}, ...) = P(X_{n+1}=j | X_n=i) – bedingte Unabhängigkeit von der Vergangenheit gegeben der Gegenwart.

Quadratische Matrix mit Einträgen p_{ij} = P(X_{n+1}=j | X_n=i); Zeilen summieren sich zu 1, alle Einträge nicht-negativ.

Die n-Schritt-Matrix ist P^n – Matrixpotenz der Übergangsmatrix; Eintrag (i,j) gibt Wahrscheinlichkeit für Übergang i→j in n Schritten.

Wahrscheinlichkeitsvektor mit πP = π; bleibt unter Zeitentwicklung invariant und erfüllt Σ π_i = 1, π_i ≥ 0.

Wenn sie irreduzibel (alle Zustände kommunizieren), aperiodisch und positiv rekurrent ist – dann existiert eindeutige stationäre Verteilung und Grenzwahrscheinlichkeiten.

Rekurrent: Rückkehrwahrscheinlichkeit = 1 (sichere Rückkehr). Transient: Rückkehrwahrscheinlichkeit < 1 (positive Wahrscheinlichkeit, nie zurückzukehren).

Periode d = ggT{n ≥ 1 : p_{ii}^{(n)} > 0}; d=1 heißt aperiodisch, d>1 bedeutet zyklisches Rückkehrverhalten alle d Schritte.

Zustände mit p_{ii}=1 und p_{ij}=0 für j≠i; einmal erreicht, wird der Zustand nie wieder verlassen – Endzustände der Kette.

p_{ij}^{(m+n)} = Σ_k p_{ik}^{(m)} p_{kj}^{(n)} – n-Schritt-Wahrscheinlichkeiten lassen sich durch Multiplikation der Übergangsmatrizen berechnen.

Für zeitumkehrbare Ketten; hinreichende Bedingung für stationäre Verteilung – wenn erfüllt, ist π stationär und Kette reversibel.

Zerlege in kommunizierende Klassen; innerhalb einer Klasse haben alle Zustände gleiche Rekursivität und Periodizität – abgeschlossene Klassen sind rekurrent.

N = (I - Q)^{-1} mit Q Übergangsmatrix der transienten Zustände; Eintrag n_{ij} = erwartete Besuchsanzahl von j beim Start in i vor Absorption.

m_{ij} = 1 + Σ_{k≠j} p_{ik} m_{kj} für i≠j; m_{jj} = 0; löst lineares Gleichungssystem – erwartete Schritte bis erster Besuch von j.

PageRank-Algorithmus: Webseiten als Zustände, Links als Übergänge; stationäre Verteilung der Surfer-Kette gibt Wichtigkeit der Seiten an.