Diskrete Markov-Ketten

Eine diskrete Markov-Kette bewegt sich zu ganzzahligen Zeitpunkten zwischen einer zählbaren Menge von Zuständen und wählt ihren nächsten Zustand basierend auf Wahrscheinlichkeiten, die nur vom aktuellen Zustand abhängen und kompakt in einer Übergangsmatrix kodiert sind.

Definition

Eine diskrete Markov-Kette ist eine Sequenz von Zufallszuständen in einer zählbaren Menge, sodass die Wahrscheinlichkeit des nächsten Zustands nur vom aktuellen Zustand abhängt, wobei diese Ein-Schritt-Wahrscheinlichkeiten in einer Übergangsmatrix gesammelt sind.

Scope

Das Thema umfasst Übergangsmatrizen und die Chapman-Kolmogorov-Gleichungen, die starke Markov-Eigenschaft, die Klassifizierung von Zuständen in kommunizierende Klassen sowie in transiente, null-rekurrente und positiv-rekurrente Zustände, Periodizität, Trefferwahrscheinlichkeiten und erwartete Trefferzeiten, berechnet durch Erstschrittanalyse, sowie die Rekurrenz-Dichotomie für Zufallspfade auf dem ganzzahligen Gitter.

Core questions

• Wie kodiert eine Übergangsmatrix die Dynamik einer Kette über viele Schritte?
• Wie werden Zustände nach ihrer Kommunikationsstruktur und ihrer Rekurrenz klassifiziert?
• Wie werden Trefferwahrscheinlichkeiten und erwartete Trefferzeiten berechnet?
• Welche Zufallspfade kehren mit Sicherheit zu ihrem Ausgangspunkt zurück und welche entweichen ins Unendliche?

Key concepts

• Übergangsmatrix
• Chapman-Kolmogorov-Gleichungen
• kommunizierende Klassen
• Rekurrenz und Transienz
• Trefferzeiten

Key theories

Starke Markov-Eigenschaft

Die Markov-Eigenschaft gilt weiterhin zu geeigneten Zufallszeitpunkten, den sogenannten Stoppzeiten, sodass eine Kette von ihrem Zustand zu einem solchen Zeitpunkt neu startet, was das Schlüsselwerkzeug zur Analyse von Rückkehr, Exkursionen und Trefferzeiten ist.

Rekurrenz-Dichotomie

Jeder Zustand ist entweder rekurrent, d.h. er wird mit Wahrscheinlichkeit eins unendlich oft besucht, oder transient, d.h. er wird nur endlich oft besucht; für den einfachen symmetrischen Zufallspfad hängt dies von der Dimension ab, mit Rekurrenz in ein- und zweidimensionalen Räumen und Transienz in drei und höheren Dimensionen.

Clinical relevance

Diskrete Markov-Ketten modellieren Brettspiele, Bestands- und Warteschlangensysteme, die Web-Navigation über die PageRank-Kette sowie genetische und ökologische Sukzession; ihre Trefferzeit- und Rekurrenztheorie beantwortet praktische Fragen, wie lange es dauert, bis ein System einen Zielzustand erreicht oder zu einem Referenzzustand zurückkehrt.

History

Markov führte diese Ketten 1906 ein und wandte sie auf die Abfolge von Vokalen und Konsonanten in einem Puschkin-Gedicht an, um zu zeigen, dass das Gesetz der großen Zahlen für abhängige Variablen gilt. Polya's Analyse von Zufallspfaden aus dem Jahr 1921 etablierte die dimensionsabhängige Rekurrenz-Dichotomie, die seinen Einfluss trägt.

Key figures

• Andrey Markov
• George Polya
• Joseph L. Doob

Seminal works

• norris1997

Frequently asked questions

Was ist der Unterschied zwischen einem rekurrenten und einem transienten Zustand?

Ein rekurrenter Zustand ist einer, zu dem die Kette mit Sicherheit zurückkehrt und den sie daher unendlich oft besucht, während ein transienter Zustand nur endlich oft besucht wird, bevor die Kette endgültig abwandert.

Warum ist der einfache Zufallspfad in niedrigen Dimensionen rekurrent, in hohen jedoch nicht?

In ein- und zweidimensionalen Räumen kehrt der Pfad mit Wahrscheinlichkeit eins zum Ursprung zurück, aber ab drei Dimensionen gibt es genügend Raum zum Entweichen, sodass der Pfad nur endlich oft zurückkehrt und transient ist; dies ist Polya's klassisches Ergebnis.