Diskrete Markov-Ketten

Eine diskrete Markov-Kette ist eine Sequenz von Zufallszuständen, die sich in ganzzahliger Zeit entwickeln, sodass die Verteilung des nächsten Zustands nur vom aktuellen Zustand abhängt und nicht von der gesamten Vergangenheit.

Definition

Eine diskrete Markov-Kette ist ein stochastischer Prozess auf einem abzählbaren Zustandsraum, indiziert durch die nicht-negativen ganzen Zahlen, dessen bedingte Verteilung des nächsten Zustands, gegeben die gesamte Historie, nur vom gegenwärtigen Zustand abhängt, kodiert durch eine Ein-Schritt-Übergangswahrscheinlichkeitsmatrix.

Scope

Dieser Bereich umfasst die Markov-Eigenschaft und Übergangsmatrizen, die Klassifizierung von Zuständen nach Kommunikation, Rekurrenz, Transienz und Periodizität, die Existenz und Eindeutigkeit von stationären und Grenzverteilungen, Konvergenz- und Mischraten sowie die Hauptanwendungen, einschließlich Markov-Ketten-Monte-Carlo und versteckter Markov-Modelle.

Sub-topics

• Versteckte Markov-Modelle
• Klassifikation und Rekurrenz von Markow-Ketten
• Markov-Kette-Monte-Carlo
• Stationäre Verteilungen und Konvergenz

Core questions

• Was bedeutet die Markov-Eigenschaft und wie wird sie durch eine Übergangsmatrix erfasst?
• Wie werden Zustände in rekurrente, transiente und periodische Klassen eingeteilt?
• Wann besitzt eine Kette eine eindeutige stationäre Verteilung und konvergiert zu dieser?
• Wie schnell nähert sich eine Kette dem Gleichgewicht, und wie wird dies in der Simulation genutzt?

Key theories

Markov-Eigenschaft und Chapman-Kolmogorov-Gleichungen

Die Zukunft ist bedingt unabhängig von der Vergangenheit, gegeben die Gegenwart, sodass mehrstufige Übergangswahrscheinlichkeiten durch Multiplikation von Übergangsmatrizen erhalten werden, was das n-Schritt-Verhalten aus der Ein-Schritt-Matrix berechenbar macht.

Ergodensatz für Markov-Ketten

Eine irreduzible, aperiodische, positiv-rekurrente Kette besitzt eine eindeutige stationäre Verteilung, zu der die Randverteilung konvergiert und gegen die Zeitmittelwerte von Funktionen fast sicher konvergieren, wodurch langfristige Häufigkeiten mit dem stationären Gesetz verknüpft werden.

Clinical relevance

Diskrete Markov-Ketten modellieren Zufallswanderungen, Warteschlangen-Momentaufnahmen, Populationsgenetik, Ranking-Algorithmen wie PageRank und ökonomische Zustandsübergänge; ihre Konvergenztheorie untermauert Markov-Ketten-Monte-Carlo, die dominierende Berechnungsmethode zur Stichprobenziehung aus komplexen Wahrscheinlichkeitsverteilungen in Statistik, Physik und maschinellem Lernen.

History

Andrey Markov führte 1906 Ketten mit abhängigen, aber gedächtnislosen Übergängen ein, um das Gesetz der großen Zahlen über die Unabhängigkeit hinaus zu erweitern, und illustrierte sie mit Buchstabenfolgen in Puschkins Poesie. Kolmogorov und Doeblin legten in den 1930er Jahren die Konvergenztheorie auf rigorose maßtheoretische Grundlagen.

Key figures

• Andrey Markov
• Andrey Kolmogorov
• Wolfgang Doeblin

Seminal works

• norris1997

Frequently asked questions

Was macht einen Prozess zu einer Markov-Kette?

Die Markov-Eigenschaft: Gegeben den aktuellen Zustand, ist die zukünftige Entwicklung unabhängig davon, wie die Kette diesen Zustand erreicht hat, sodass die gesamte Dynamik durch Ein-Schritt-Übergangswahrscheinlichkeiten beschrieben wird.

Wann konvergiert eine Markov-Kette zu einer eindeutigen Langzeitverteilung?

Wenn sie irreduzibel, aperiodisch und positiv rekurrent ist; dann gibt es eine einzige stationäre Verteilung, zu der die Kette unabhängig von ihrem Startzustand konvergiert.