9 Mehrstufige Experimente und Markovketten Flashcards
(D) stochastische Matrix
Eine stochastische Matrix P = (p_ij)ij∈I ist eine Matrix, deren Zeilen jeweils Verteilungen auf I sind. Das heißt, es gilt pij ≥ 0 für alle i,j∈I und ∑︁j p_ij =1 für alle i∈I.
(D) homogene Markovkette in diskreter Zeit
I Zustandsraum, v = (v(i))i∈I Verteilung auf I, P = (p_ij)i,j∈I stochastische Matrix auf I.
Ein I-wertiger stochastischer Prozess (Xn)n≥0 heißt zeitlich homogene Markovkette in diskreter Zeit mit Anfangsverteilung v und Übergangsmatrix P, falls für alle n∈N und alle i∈I gilt
P(X0 = i0) = v(i0) und
P(Xn+1 = in+1 | Xn = in, …, X0 = i0) = P(Xn+1 = in+1 | Xn = in) = p_inin+1 (Markoveigenschaft),
falls die Ereignisse, auf die bedingt wird, positive Wahrscheinlichkeit haben.
(D) Kopplung von Übergangszähldichten, Unabhängigkeit (2)
- f_k+1^k(𝜔1,··· ,𝜔k;𝜔k+1) Zähldichten. Dann heißt die Abbildung
𝑓 = 𝑓1^0 ⊗ · · · ⊗ 𝑓n^n-1 mit
𝑓((𝜔1,…,𝜔n)) = 𝑓1^0(𝜔1)···𝑓n^n-1(𝜔1,…,𝜔n-1;𝜔n)
die Kopplung der Übergangszähldichten f_k+1^k und es gilt 0 ≤ 𝑓 ≤ 1 und ∑ f(𝜔) = 1.
- Wir nennen eine Kopplung unabhängig, wenn es ein 𝑓k+1^k~ : Ωk+1 → [0, 1] gibt mit
𝑓k+1^k (𝜔1,…,𝜔k;𝜔k+1) =𝑓k+1^k~ (𝜔k+1),
für alle (𝜔1,…,𝜔𝑘)∈Ω1×···×Ω𝑘 und 𝜔𝑘+1 ∈ Ω𝑘+1 für 𝑘 = 0,1,…,𝑛−1.
(D) stochastischer Prozess
Ein stochastischer Prozess (𝑋𝑛 )𝑛 ≥0 ist eine Familie von 𝐼 -wertigen Zufallsvariablen, die auf dem gleichen Wahrscheinlichkeitsraum (Ω, A, P) definiert sind.
(D) Periode, Aperiodizität
Die Periode eines Zustandes 𝑖 ∈ 𝐼 ist die Zahl
𝑑𝑖 = ggT{ 𝑛≥1 : 𝑝ii^(𝑛) >0},
mit 𝑑𝑖 = ∞, falls 𝑝ii^(𝑛) = 0 für alle 𝑛 ≥ 1 ist. Der Zustand 𝑖 heißt aperiodisch, wenn 𝑑𝑖 = 1.
(D) Invariante Verteilung / Gleichgewichtsverteilung
Der Zeilenvektor (𝜋𝑖 )𝑖 ∈𝐼 heißt invariante Verteilung für die Markovkette mit Übergangsmatrix 𝑃, wenn gilt
𝜋𝑃 = 𝜋, 𝜋𝑖 ≥ 0 und ∑︁𝜋𝑖 = 1.
(D) abgeschlossen, absorbierend, irreduzibel (3)
- Eine Teilmenge 𝐶 ⊂ 𝐼 heißt abgeschlossen, falls aus 𝑖 ∈ 𝐶 und 𝑖 → 𝑗 folgt 𝑗 ∈ 𝐶.
- Ein Zustand 𝑖 heißt absorbierend, falls {𝑖} eine abgeschlossene Klasse ist.
- Eine Markovkette (und die zugehörige Übergangsmatrix) heißt irreduzibel, wenn 𝐼 aus einer einzigen kommunizierenden Klasse besteht, d.h. wenn alle Zustände miteinander kommunizieren.
Es gilt, dass sich der Zustandsraum einer Markovkette als eine disjunkte Vereinigung
𝐼 =𝑈 ∪ 𝐶0 ∪ 𝐶1 ∪ 𝐶2 ∪ ···
schreiben lässt, mit 𝑈 der Menge der unwesentlichen Zustände und abgeschlossenen kommunizierenden Klassen 𝐶0, 𝐶1, … .
(D) erreichbar, kommunizierende Zustände, (un)wesentlicher Zustand (3)
- Der Zustand 𝑗 ist vom Zustand 𝑖 aus erreichbar ist (𝑖 → 𝑗), wenn ein 𝑛 ≥ 0 existiert, sodass 𝑝ij^(𝑛) > 0.
- Wir sagen, dass 𝑖 und 𝑗 kommunizieren (𝑖 ↔ 𝑗), wenn gilt 𝑖 → 𝑗 und 𝑗 → 𝑖.
- Ein Zustand 𝑖 heißt unwesentlich, wenn ein 𝑗 exisitiert mit 𝑖 → 𝑗 und 𝑗 /→ 𝑖. Andernfalls heißt der Zustand wesentlich.
Für die asymptotische Entwicklung einer Markovkette sind nur die wesentlichen Zustände von Bedeutung.
(S) Charakterisierung einer Markovkette
Ein 𝐼-wertiger stochastischer Prozess 𝑋 = (𝑋𝑛)𝑛≥0 ist genau dann eine (𝜈,𝑃 )-Markovkette, wenn für alle 𝑛∈N und alle 𝑖∈𝐼 gilt
P(𝑋n = 𝑖n, 𝑋n-1 = 𝑖n-1, …, 𝑋0 = 𝑖0) = 𝜈(𝑖0)·𝑝i0i1·𝑝i1i2·…·𝑝in-1in.
(S) Perioden in einer irreduziblen Markovkette
Für eine irreduzible MK mit Zustandsraum 𝐼 gilt 𝑑𝑖 = 𝑑𝑗 für alle 𝑖, 𝑗 ∈ 𝐼.
Dh, in einer irreduziblen MK haben alle Zustände die gleiche Periode.
(S) 𝑛-Schritte Übergangswahrscheinlichkeiten
Ist (𝑋𝑛)𝑛≥0 eine (𝜈,𝑃 )-MK, dann gilt P(𝑋 = 𝑗) = (𝜈𝑃^𝑛)j. Insbesondere ist P(𝑋 = 𝑗) = 𝑝ij^(𝑛).
Dieser Satz besagt, dass 𝑃^𝑛 die 𝑛-Schritte Übergangsmatrix ist und dass, um die Verteilung der (𝜈,𝑃)-MK zu bestimmen, wir einfach 𝑃^𝑛 von links mit dem Vektor der Anfangsverteilung zu multiplizieren brauchen.
(S) Existenz, Eindeutigkeit, Konvergenz, Positivität invarianter Verteilung
Essei(𝑋𝑛)𝑛≥0 eine irreduzible und aperiodische Markovkette mit einem endlichen Zustandsraum 𝐼 und Über- gangsmatrix 𝑃. Dann gibt es eine eindeutige Invariante Verteilung 𝜋 mit 𝜋𝑗 > 0 für alle 𝑗 ∈ 𝐼 und es gilt
lim.n→∞ 𝑝ij^(𝑛) = 𝜋𝑗 für alle 𝑖,𝑗 ∈𝐼.
Die Gleichung besagt unter anderem, dass eine Markovkette, die die Bedingungen des Satzes erfüllt, die Anfangsverteilung “vergisst”. Ist nämlich 𝜈 = (𝜈𝑖 )𝑖 ∈𝐼 eine Verteilung auf 𝐼 , dann gilt
P𝜈(𝑋𝑛 = 𝑗) = ∑i∈𝐼 𝜈𝑖·𝑝𝑖𝑗^(n) → 𝜋𝑗 ∑i∈𝐼 𝜈𝑖 = 𝜋𝑗 (für n→∞).
Das erklärt den Begriff Gleichgewichtsverteilung.
