Übungsquiz zu Markov-Ketten & stochastischen Prozessen mit interaktiver Schritt-für-Schritt-Lektion
Nutze das Quiz weiter unten auf der Seite, um Markov-Ketten und stochastische Prozesse zu üben: die Markov-Eigenschaft, zeilenstochastische Übergangsmatrizen, Aktualisierungen von Verteilungen \(pP\), Potenzen \(P^n\), das Chapman-Kolmogorov-Gesetz, stationäre Verteilungen \(\pi P=\pi\), absorbierende Zustände und abgeschlossene Klassen, Irreduzibilität, Rekurrenz und Transienz, Periode und Aperiodizität, Konvergenz endlicher Ketten, Martingale, Submartingale, Supermartingale, Filtrationen und Stoppzeiten. Wenn du etwas auffrischen möchtest, öffne die Lektion. Dort findest du gut nachvollziehbare Beispiele und kurze Kontrollfragen.
Beantworte die Fragensammlung und prüfe deine Fehler am Ende.
So funktioniert diese Übung zu Markov-Ketten und stochastischen Prozessen
1. Bearbeite das Übungsset: Beantworte Fragen zu Übergangswahrscheinlichkeiten, stationären Verteilungen, Rekurrenz, Periodizität, Martingalen und Stoppzeiten.
2. Öffne die Lektion: Wiederhole zeilenstochastische Matrizen, Klassenstruktur, Langzeitverhalten, absorbierende Ketten und Werkzeuge für bedingte Erwartungen.
3. Erneut versuchen: Kehre zum Fragenset zurück und entscheide, ob du einen Matrixeintrag berechnest, \(\pi P=\pi\) löst, einen Zustand klassifizierst oder eine bedingte Erwartung prüfst.
Was du in der Lektion zu Markov-Ketten & stochastischen Prozessen lernst
Übergangsgesetze und Matrixpotenzen
Lies \(P_{ij}\) als die Wahrscheinlichkeit, in einem Schritt von Zustand \(i\) zu Zustand \(j\) zu wechseln.
Aktualisiere Verteilungen als Zeilenvektoren mit \(p_{n+1}=p_nP\) und \(p_n=p_0P^n\).
Nutze Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Stationäres und Langzeitverhalten
Löse \(\pi P=\pi\) zusammen mit \(\sum_i\pi_i=1\).
Erkenne \(\pi\) als linken Eigenvektor zum Eigenwert \(1\).
Erkenne die Gleichverteilung als stationäre Verteilung in doppelt stochastischen Ketten und die stationären Zeilen der Grenzmatrix bei endlichen irreduziblen aperiodischen Ketten.
Klassenstruktur endlicher Ketten
Klassifiziere kommunizierende Klassen, abgeschlossene Klassen und absorbierende Zustände.
Unterscheide rekurrente Zustände von transienten Zuständen in endlichen Ketten.
Berechne Perioden aus dem ggT möglicher Rückkehrzeiten.
Prozesse, Martingale und Stoppzeiten
Nutze Filtrationen \(\mathcal F_n\), um die zum Zeitpunkt \(n\) bekannte Information darzustellen.
Prüfe Martingale mit \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Erkenne, dass Stoppzeiten aus vergangenen und gegenwärtigen Informationen entschieden werden müssen, nicht aus ungesehenen zukünftigen Daten.
Lektion zu Markov-Ketten & stochastischen Prozessen
1 / 8
Modelliere zufällige Bewegung Schritt für Schritt
Ziel: Baue einen zuverlässigen Werkzeugkasten für endliche Markov-Ketten und nahe verwandte Ideen stochastischer Prozesse auf. Du liest Übergangsmatrizen, berechnest Mehrschritt-Wahrscheinlichkeiten, löst stationäre Verteilungen, klassifizierst Zustände, erkennst periodisches Verhalten und verbindest bedingte Erwartung mit Martingalen und Stoppzeiten.
Erfolgskriterien
Formuliere die Markov-Eigenschaft: Ist der aktuelle Zustand gegeben, braucht die Zukunft die frühere Vergangenheit nicht.
Prüfe, dass eine endliche Übergangsmatrix zeilenstochastisch ist: Einträge sind nichtnegativ und jede Zeile summiert sich zu \(1\).
Aktualisiere Verteilungen als Zeilenvektoren mit \(p_{n+1}=p_nP\) und lies \(P^n_{ij}\) als \(n\)-Schritt-Wahrscheinlichkeit.
Nutze Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Löse \(\pi P=\pi\) mit \(\sum_i\pi_i=1\) für stationäre Verteilungen, einschließlich der Gleichverteilung bei doppelt stochastischen Ketten.
Klassifiziere absorbierende Zustände, kommunizierende Klassen, Irreduzibilität, Rekurrenz und Transienz.
Finde Perioden aus Rückkehrzeiten und wisse, warum eine Selbstschleife Periode \(1\) erzwingt.
Formuliere das Konvergenzbild für endliche irreduzible aperiodische Ketten.
Erkenne Martingale, Submartingale, Supermartingale und Stoppzeiten mithilfe bedingter Erwartung und der bisher verfügbaren Information.
Wichtige Begriffe
Stochastischer Prozess: eine Folge von Zufallsvariablen wie \(X_0,X_1,X_2,\dots\).
Markov-Kette: ein stochastischer Prozess, dessen Gesetz für den nächsten Zustand vom aktuellen Zustand abhängt, nicht von der ganzen Vergangenheit.
Übergangsmatrix: \(P_{ij}=\Pr(X_{n+1}=j\mid X_n=i)\), wobei jede Zeile eine Wahrscheinlichkeitsverteilung ist.
Stationäre Verteilung: eine Verteilung \(\pi\) mit \(\pi P=\pi\).
Kommunizierende Klasse: Zustände, die einander erreichen können.
Periode: der ggT möglicher Rückkehrzeiten zu einem Zustand.
Martingal: ein Prozess mit \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Stoppzeit: eine zufällige Zeit, die mit der bis dahin verfügbaren Information entschieden wird.
Kurzer Vorabtest
Vorabcheck: Wovon hängt in einer Markov-Kette die Ein-Schritt-Zukunft ab, nachdem auf den aktuellen Zustand bedingt wurde?
Hinweis: Die Vergangenheit kann die Zukunft über den aktuellen Zustand beeinflussen, aber sobald der aktuelle Zustand bekannt ist, liefern frühere Zustände keine zusätzliche Information für das Ein-Schritt-Gesetz.
Zeilen codieren Einschritt-Wahrscheinlichkeiten
Lernziel: Lies eine endliche Übergangsmatrix und berechne Ein-Schritt- oder Mehrschritt-Verteilungen, ohne die Wahrscheinlichkeitskonvention zu verwechseln.
Kernidee
Mit der Zeilenvektor-Konvention wird eine aktuelle Verteilung \(p_n\) durch \(p_{n+1}=p_nP\) aktualisiert. Der Eintrag \(P_{ij}\) ist die Wahrscheinlichkeit, in einem Schritt von Zustand \(i\) zu Zustand \(j\) zu wechseln.
Matrixregeln
Jeder Eintrag erfüllt \(0\le P_{ij}\le1\).
Jede Zeile summiert sich zu \(1\), weil der nächste Zustand irgendwo liegen muss.
Ein deterministischer Schritt hat in einer Zeile einen Eintrag gleich \(1\) und die anderen \(0\).
Ein absorbierender Zustand \(i\) hat \(P_{ii}=1\).
Wenn \(p_0\) eine Verteilung ist, dann ist \(p_0P^n\) die Verteilung nach \(n\) Schritten.
Wenn alle Zeilen identisch sind, schickt ein Schritt jede Startverteilung auf diese gemeinsame Zeile.
Chapman-Kolmogorov
Mehrschritt-Übergänge werden zusammengesetzt: \[P^{m+n}=P^mP^n.\] Eintragsweise wird dabei über alle möglichen Zwischenzustände summiert.
Ausgearbeitetes Beispiel
Beispiel: Sei \(P=\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}\) und \(p_0=(1,0)\). Was ist \(p_1\)?
Multipliziere von rechts: \[p_1=p_0P=(1,0)\begin{pmatrix}1/2&1/2\\1/4&3/4\end{pmatrix}=(1/2,1/2).\] Wenn du in Zustand \(1\) startest, ist die nächste Verteilung einfach Zeile \(1\) von \(P\).
Aufgabe
Aufgabe: Wie sollte in einer Übergangsmatrix die Zeile \((1/4,3/4)\) klassifiziert werden?
Hinweis: Prüfe Nichtnegativität und Zeilensumme.
Eine stationäre Verteilung bleibt nach einem Schritt unverändert
Lernziel: Erkenne und löse stationäre Gleichungen für endliche Ketten.
Kernidee
Eine Zeilenverteilung \(\pi\) ist stationär, wenn \(\pi P=\pi\). In der Sprache der linearen Algebra ist \(\pi\) ein linker Eigenvektor von \(P\) zum Eigenwert \(1\), normiert so, dass seine Einträge nichtnegativ sind und sich zu \(1\) summieren.
Lösungs-Checkliste
Schreibe \(\pi=(\pi_1,\dots,\pi_k)\).
Löse \(\pi P=\pi\).
Füge die Normierung \(\pi_1+\cdots+\pi_k=1\) hinzu.
Prüfe, dass die Einträge nichtnegativ sind.
Eine endliche doppelt stochastische Matrix erhält die Gleichverteilung.
Für \(P=I\) ist jede Wahrscheinlichkeitsverteilung stationär.
In reduziblen Ketten können stationäre Verteilungen nicht eindeutig sein.
Schnellformel für zwei Zustände
Für \(P=\begin{pmatrix}1-a&a\\b&1-b\end{pmatrix}\) mit positivem \(a+b\) ist die stationäre Verteilung proportional zu \((b,a)\), also \(\pi=\left(\frac{b}{a+b},\frac{a}{a+b}\right)\).
Ausgearbeitetes Beispiel
Beispiel: Finde eine stationäre Verteilung für \(P=\begin{pmatrix}1/2&1/2\\1/2&1/2\end{pmatrix}\).
Beide Zeilen sind gleichverteilt. Das Multiplizieren jeder Verteilung mit \(P\) ergibt \((1/2,1/2)\), also ist \(\pi=(1/2,1/2)\) stationär. Das ist die Abkürzung über gemeinsame Zeilen: Identische Zeilen schicken jede aktuelle Verteilung auf diese Zeile.
Aufgabe
Aufgabe: Was bedeutet \(\pi P=\pi\)?
Hinweis: Ein Übergang lässt die Verteilung genau so, wie sie war.
Erreichbarkeit steuert die Struktur der Kette
Lernziel: Nutze Erreichbarkeit im Graphen, um Zustände und kommunizierende Klassen zu klassifizieren.
Kernidee
Man sagt, \(i\) erreicht \(j\), wenn \((P^n)_{ij}>0\) für ein \(n\ge0\) gilt. Zustände kommunizieren, wenn jeder den anderen erreicht. Eine irreduzible endliche Kette hat eine einzige kommunizierende Klasse.
Klassifikationssprache
Abgeschlossene Klasse: Sobald die Kette sie betritt, kann sie die Klasse nicht mehr verlassen.
Absorbierender Zustand: eine ein-elementige abgeschlossene Klasse, äquivalent zu \(P_{ii}=1\).
Rekurrenter Zustand: wird mit Wahrscheinlichkeit \(1\) wieder erreicht.
Transienter Zustand: wird mit Wahrscheinlichkeit \(1\) nur endlich oft besucht.
Irreduzible Kette: Jeder Zustand kommuniziert mit jedem anderen Zustand.
Fakten für endliche Ketten
In einer endlichen irreduziblen Kette ist jeder Zustand rekurrent. In einer endlichen reduziblen Kette sind Zustände außerhalb abgeschlossener Klassen oft transient, weil die Wahrscheinlichkeitsmasse schließlich in eine abgeschlossene Klasse wandert und dort bleibt.
Ausgearbeitetes Beispiel
Beispiel: Für \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\): Welcher Zustand ist absorbierend?
Zustand \(1\) ist absorbierend, weil Zeile \(1\) gleich \((1,0)\) ist, also \(P_{11}=1\). Zustand \(2\) kann zu Zustand \(1\) wechseln, aber Zustand \(1\) kann nicht zu Zustand \(2\) zurückwechseln; daher ist die Kette nicht irreduzibel.
Aufgabe
Aufgabe: Was bedeutet irreduzibel für eine endliche Markov-Kette?
Hinweis: Denke an den gerichteten Graphen mit einem Pfeil \(i\to j\), wenn ein Übergang positive Wahrscheinlichkeit hat.
Rückkehrzeit-Arithmetik entscheidet Aperiodizität
Lernziel: Berechne einfache Perioden und wisse, warum Aperiodizität für Konvergenz wichtig ist.
Kernidee
Die Periode eines Zustands \(i\) ist der ggT aller positiven \(n\), für die \((P^n)_{ii}>0\) gilt. Ein Zustand mit Periode \(1\) ist aperiodisch. In einer irreduziblen Kette haben alle Zustände dieselbe Periode.
Konvergenzbild
Wenn eine endliche Kette irreduzibel und aperiodisch ist, hat sie eine eindeutige stationäre Verteilung \(\pi\).
Für eine solche Kette konvergiert \(P^n\) gegen eine Matrix, deren Zeilen alle \(\pi\) sind.
Wenn die Kette periodisch ist, kann eine stationäre Verteilung existieren, während \(P^n\) trotzdem oszilliert.
Wenn die Kette reduzibel ist, hängt das Grenzverhalten von den erreichbaren abgeschlossenen Klassen ab.
Selbstschleifen
Eine Selbstschleife \(P_{ii}>0\) gibt eine mögliche Rückkehr in einem Schritt, also enthält der ggT der Rückkehrzeiten \(1\). Das erzwingt Periode \(1\).
Ausgearbeitetes Beispiel
Beispiel: Für \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\): Was passiert nach zwei Schritten?
Die Kette wechselt in jedem Schritt den Zustand. Daher ist \(P^2=I\), Rückkehr ist nur zu geraden Zeiten möglich, und jeder Zustand hat Periode \(2\).
Aufgabe
Aufgabe: Welche Periode hat die Kette mit \(P=\begin{pmatrix}0&1\\1&0\end{pmatrix}\)?
Hinweis: Starte in einem Zustand und zähle die Zeiten, zu denen Rückkehr möglich ist.
Abgeschlossene Zustände machen Wahrscheinlichkeitsfragen zu Gleichungen
Lernziel: Stelle einfache Gleichungen für Treffwahrscheinlichkeiten und erwartete Treffzeiten bei absorbierendem Verhalten auf.
Kernidee
Ein absorbierender Zustand hält die Kette fest, nachdem er betreten wurde. Allgemeiner kann eine abgeschlossene kommunizierende Klasse nicht verlassen werden. Trefffragen fragen, ob und wann der Prozess eine gewählte Menge betritt.
Treffgleichungen
Für eine Treffwahrscheinlichkeit \(h_i\) nutze Randwerte \(h_i=1\) auf dem Ziel und \(h_i=0\) auf unmöglichen abgeschlossenen Klassen.
Für andere Zustände nutze \(h_i=\sum_j P_{ij}h_j\).
Für eine erwartete Treffzeit \(t_i\) nutze \(t_i=0\) auf dem Ziel und sonst \(t_i=1+\sum_jP_{ij}t_j\).
Halte Gleichungen klein, indem du Symmetrie oder offensichtliche absorbierende Zustände nutzt.
Abgeschlossene Klassen
Eine absorbierende Klasse ist eine kommunizierende Klasse, die nicht verlassen werden kann. Ein einzelner absorbierender Zustand ist das kleinste Beispiel dieser Idee.
Ausgearbeitetes Beispiel
Beispiel: Für \(P=\begin{pmatrix}1&0\\1/2&1/2\end{pmatrix}\): Wenn man in Zustand \(2\) startet, wie groß ist die erwartete Zeit bis zum Treffen von Zustand \(1\)?
Setze \(t_1=0\). Von Zustand \(2\) aus gilt \[t_2=1+\frac12t_1+\frac12t_2=1+\frac12t_2.\] Also ist \(t_2=2\).
Aufgabe
Aufgabe: Wenn eine Markov-Kette in einem absorbierenden Zustand startet, wo ist sie nach einem Schritt?
Hinweis: Ein absorbierender Zustand hat \(P_{ii}=1\).
Bedingte Erwartung misst fairen Drift
Lernziel: Verbinde die Intuition von Markov-Ketten mit der allgemeineren Sprache stochastischer Prozesse, Filtrationen, Martingalen und Stoppzeiten.
Kernidee
Ein stochastischer Prozess ist jede indizierte Familie von Zufallsvariablen. Eine Filtration \((\mathcal F_n)\) zeichnet die bis zum Zeitpunkt \(n\) verfügbare Information auf. Martingal-Aussagen sind bedingte Erwartungen relativ zu dieser Information.
Übersicht zur bedingten Erwartung
Martingal: \(E[X_{n+1}\mid\mathcal F_n]=X_n\).
Submartingal: \(E[X_{n+1}\mid\mathcal F_n]\ge X_n\), also ist der bedingte Drift nichtnegativ.
Supermartingal: \(E[X_{n+1}\mid\mathcal F_n]\le X_n\), also ist der bedingte Drift nichtpositiv.
Das sind Aussagen über bedingte Erwartungswerte, nicht darüber, dass jeder Pfad steigt oder fällt.
Stoppzeiten
Eine Stoppzeit \(\tau\) muss aus der bis zum Zeitpunkt \(n\) verfügbaren Information entscheidbar sein, wenn geprüft wird, ob \(\tau\le n\). Zum Beispiel ist der erste Zeitpunkt, zu dem ein Prozess \(5\) trifft, eine Stoppzeit; der letzte Zeitpunkt vor morgen, zu dem er \(5\) trifft, hängt von zukünftiger Information ab.
Ausgearbeitetes Beispiel
Beispiel: Sei \(S_n\) eine faire einfache Irrfahrt mit unabhängigen Schritten \(+1\) oder \(-1\), jeweils mit Wahrscheinlichkeit \(1/2\). Warum ist \(S_n\) ein Martingal?
Bei gegebener aktueller Information hat der nächste Schritt bedingten Erwartungswert \(0\). Daher gilt \(E[S_{n+1}\mid\mathcal F_n]=S_n+0=S_n\).
Aufgabe
Aufgabe: Ein Martingal erfüllt \(E[X_{n+1}\mid\mathcal F_n]=\) was?
Hinweis: Ein Martingal hat ausgehend vom aktuellen Wert keinen bedingten Drift.
Die meisten Fehler verwechseln Konventionen oder ignorieren Voraussetzungen
Lernziel: Schließe ab, indem du Fakten zu Übergangsmatrizen, Langzeitfakten und Fakten zu bedingten Erwartungen trennst.
Häufige Fallen
Zeilen- versus Spaltenkonvention: Diese Lektion verwendet Zeilenverteilungen \(pP\). Bei Spaltenverteilungen werden die Formeln transponiert.
Ungültige Matrixzeilen: Wahrscheinlichkeiten müssen nichtnegativ sein und jede Zeile muss sich zu \(1\) summieren.
Stationär ist nicht absorbierend: \(\pi P=\pi\) beschreibt eine Verteilung, nicht unbedingt einen festen Zustand.
Reduzible Ketten können viele stationäre Verteilungen haben: Abgeschlossene Klassen können jeweils stationäre Masse tragen.
Periode kann Konvergenz blockieren: Der Zwei-Zustands-Wechsel hat eine stationäre Verteilung, aber \(P^n\) oszilliert.
Selbstschleifen-Abkürzung: \(P_{ii}>0\) gibt Periode \(1\) für diese rekurrente Klasse.
Transient ist letztlich gemeint: Ein transienter Zustand kann mehrmals besucht werden, aber mit Wahrscheinlichkeit \(1\) nur endlich oft.
Stoppzeiten nutzen verfügbare Information: Sie dürfen nicht von ungesehenen zukünftigen Ergebnissen abhängen.
Martingal bedeutet fairer bedingter Erwartungswert: Es bedeutet nicht, dass der Pfad konstant bleibt.
Ausgearbeitetes Beispiel
Beispiel: Ist die Zeile \((1/4,1/4)\) als vollständige Übergangszeile gültig?
Nein. Sie ist nichtnegativ, aber ihre Einträge summieren sich zu \(1/2\), nicht zu \(1\). Eine vollständige Übergangszeile muss Gesamtwahrscheinlichkeit \(1\) über alle nächsten Zustände zuweisen.
Aufgabe
Aufgabe: Wovon darf eine Stoppzeit nicht abhängen?
Hinweis: Zum Zeitpunkt \(n\) muss die Entscheidung auf Information beruhen, die bis zum Zeitpunkt \(n\) verfügbar ist.
Abschluss-Wiederholung
Markov-Eigenschaft: Das Gesetz des nächsten Zustands hängt vom aktuellen Zustand ab, sobald der aktuelle Zustand bekannt ist.
Eine Übergangsmatrix hat nichtnegative Einträge und Zeilen, die sich zu \(1\) summieren.
Mit Zeilenvektoren gilt \(p_n=p_0P^n\).
Chapman-Kolmogorov: \(P^{m+n}=P^mP^n\).
Stationäre Verteilungen lösen \(\pi P=\pi\) und \(\sum_i\pi_i=1\).
Identische Zeilen schicken jede aktuelle Verteilung auf die gemeinsame Zeile; doppelt stochastische endliche Ketten erhalten die Gleichverteilung; \(P=I\) erhält jede Verteilung.
Ein absorbierender Zustand hat \(P_{ii}=1\); eine abgeschlossene Klasse kann nicht verlassen werden.
Irreduzibel bedeutet, dass jeder Zustand jeden anderen erreichen kann.
Die Periode ist der ggT möglicher Rückkehrzeiten; eine Selbstschleife gibt Periode \(1\).
Endliche irreduzible aperiodische Ketten konvergieren gegen stationäre Zeilen.
Stoppzeiten werden aus vergangenen und gegenwärtigen Informationen entschieden, nicht aus ungesehenen zukünftigen Daten.
Nächster Schritt: Schließe diese Lektion und versuche das Quiz erneut. Entscheide bei jeder Frage zuerst, ob sie nach einem Schritt, vielen Schritten, einer stationären Verteilung, Zustandsklassifikation, Periode oder bedingter Erwartung fragt.
