Klassifikation und Rekurrenz von Markow-Ketten

Die Klassifizierung der Zustände einer Markow-Kette zeigt, welche Zustände unendlich oft besucht werden und welche schließlich aufgegeben werden, wodurch der Zustandsraum in kommunizierende Klassen mit gemeinsamem Langzeitverhalten unterteilt wird.

Definition

Die Zustands-Klassifikation analysiert eine Markow-Kette, indem sie Zustände, die einander erreichen können, zu kommunizierenden Klassen gruppiert und jeden Zustand als rekurrent bezeichnet, wenn die Kette mit Wahrscheinlichkeit eins zu ihm zurückkehrt, oder als transient, wenn eine positive Wahrscheinlichkeit besteht, niemals zurückzukehren.

Scope

Dieses Thema behandelt die Erreichbarkeits- und Kommunikationsbeziehungen, die Zerlegung des Zustandsraums in kommunizierende Klassen, Irreduzibilität, die Rekurrenz-Transienz-Dichotomie und ihre Kriterien, positive versus Null-Rekurrenz, Periodizität und die Verwendung von Erstpassagen- und Trefferwahrscheinlichkeiten zur Bestimmung dieser Eigenschaften.

Core questions

• Wann kommunizieren zwei Zustände, und wie teilt dies den Zustandsraum auf?
• Was unterscheidet einen rekurrenten Zustand von einem transienten Zustand?
• Wie wird positive Rekurrenz von Null-Rekurrenz unterschieden?
• Welche Rolle spielt die Periodizität im Langzeitverhalten der Kette?

Key theories

Rekurrenz-Transienz-Dichotomie

Ein Zustand ist rekurrent genau dann, wenn die erwartete Anzahl der Rückkehren unendlich ist, äquivalent dazu, dass die Summe seiner Rückkehrwahrscheinlichkeiten divergiert; Rekurrenz und Transienz sind Klasseneigenschaften, die von allen Zuständen geteilt werden, die kommunizieren.

Positive versus Null-Rekurrenz

Ein rekurrenter Zustand ist positiv rekurrent, wenn die erwartete Rückkehrzeit endlich ist, und null-rekurrent, wenn sie unendlich ist; positive Rekurrenz ist notwendig für die Existenz einer stationären Wahrscheinlichkeitsverteilung.

Clinical relevance

Die Bestimmung der Rekurrenz klärt, ob ein Random Walk zu seinem Ursprung zurückkehrt, ob eine Warteschlange unendlich oft leer wird und ob ein Populationsprozess fortbesteht oder absorbiert wird; Polya's klassisches Ergebnis, dass der einfache symmetrische Random Walk in ein und zwei Dimensionen rekurrent, aber in drei oder mehr Dimensionen transient ist, ist eine kanonische Konsequenz.

History

Die Rekurrenzfrage wurde durch Polyas Analyse von Random Walks auf ganzzahligen Gittern im Jahr 1921 kristallisiert, und die systematische klassenbasierte Theorie der Rekurrenz und Transienz wurde Mitte des 20. Jahrhunderts von Chung, Feller und anderen in der Form entwickelt, die in modernen Lehrbüchern zu finden ist.

Key figures

• George Polya
• Andrey Markov
• Kai Lai Chung

Seminal works

• norris1997

Frequently asked questions

Was bedeutet es, wenn ein Zustand rekurrent ist?

Ausgehend von diesem Zustand kehrt die Kette mit Wahrscheinlichkeit eins zu ihm zurück und kehrt daher unendlich oft zurück; ein transienter Zustand ist einer, den die Kette mit positiver Wahrscheinlichkeit für immer verlassen kann.

Warum ist die Dimension für die Rekurrenz von Random Walks wichtig?

Der einfache symmetrische Random Walk ist in den Dimensionen eins und zwei rekurrent, aber in drei und höheren Dimensionen transient, weil die Wahrscheinlichkeit, zum Ursprung zurückzukehren, davon abhängt, wie schnell der Walk entweichen kann, was mit der Dimension zunimmt.