Intuitive Erklärung für die Periodizität in Markov-Ketten

16

Kann mir jemand intuitiv erklären, wie periodisch eine Markov-Kette ist?

Es ist wie folgt definiert:

Für alle Zustände insiS

dich = gcd{nN|pichich(n)>0}=1

Vielen Dank für Ihre Mühen!

Chris
quelle
1
Ich fand die Wikipedia-Beschreibung kurz und bündig. Erledigt es die Arbeit für Sie?
Cyan
2
Die Definition in OP heißt "aperioidisch".
Jack

Antworten:

27

Erstens ist Ihre Definition nicht ganz korrekt. Hier ist die korrekte Definition aus Wikipedia, wie von Cyan vorgeschlagen.


Periodizität (Quelle: Wikipedia )

Ein Zustand i hat die Periode k, wenn eine Rückkehr in den Zustand i in Vielfachen von k Zeitschritten erfolgen muss. Formal ist die Periode eines Staates definiert als

Gcd{n:Pr(Xn=ich|X0=ich)>0}

(wobei "gcd" der größte gemeinsame Teiler ist). Es ist zu beachten, dass es möglicherweise nicht möglich ist, den Zustand in k Schritten zu erreichen, obwohl ein Zustand die Periode k aufweist. Angenommen, es ist möglich, in {6, 8, 10, 12, ...} Zeitschritten zum Status zurückzukehren. k wäre 2, obwohl 2 in dieser Liste nicht vorkommt.

Wenn k = 1 ist, wird der Zustand als aperiodisch bezeichnet: Die Rückkehr in den Zustand i kann zu unregelmäßigen Zeiten erfolgen. Mit anderen Worten, ein Zustand i ist aperiodisch, wenn es n gibt, so dass für alle n '≥ n

Pr(Xn=ich|X0=ich)>0.

Andernfalls (k> 1) wird der Zustand als periodisch mit der Periode k bezeichnet. Eine Markov-Kette ist aperiodisch, wenn jeder Zustand aperiodisch ist.


Meine Erklärung

Der Begriff Periodizität beschreibt, ob etwas (ein Ereignis oder hier: der Besuch eines bestimmten Staates) in regelmäßigen Zeitabständen stattfindet. Hier wird die Zeit in der Anzahl der von Ihnen besuchten Staaten gemessen.

Erstes Beispiel:

Bildbeschreibung hier eingeben

Stellen Sie sich nun vor, dass die Uhr eine Markov-Kette darstellt und jede Stunde einen Zustand markiert. Wir haben also 12 Zustände. Jeder Zustand wird alle 12 Stunden (Zustände) mit der Wahrscheinlichkeit = 1 vom Stundenzeiger angezeigt, daher ist der größte gemeinsame Teiler auch 12.

Jeder (Stunden-) Zustand ist also periodisch mit Punkt 12.

Zweites Beispiel:

Stellen Sie sich einen Graphen vor, der eine Folge von Münzwürfen beschreibt, beginnend mit und und die das Ergebnis des letzten Münzwurfs darstellen.steinrtheeindsteinichls

Bildbeschreibung hier eingeben

Die Übergangswahrscheinlichkeit beträgt 0,5 für jedes Zustandspaar (i, j), mit Ausnahme von -> und -> bei 0.heeindssteinrtteinichlssteinrt

Stellen Sie sich vor, Sie sind in . Die Anzahl der Staaten, die Sie besuchen müssen, bevor Sie die erneut besuchen , könnte 1,2,3 usw. betragen. Es wird passieren, daher ist die Wahrscheinlichkeit größer als 0, aber es ist nicht genau vorhersehbar, wann. Der größte gemeinsame Teiler aller möglichen Besuche, die auftreten können, bevor Sie die erneut besuchen , ist also 1. Dies bedeutet, dass die aperiodisch sind.heeindsheeindsheeindsheeinds

Gleiches gilt für . Da es nicht für den , ist der gesamte Graph nicht aperiodisch. Wenn wir entfernen , wäre es.teinichlssteinrtsteinrt

steffen
quelle
0

n>0Pichichn=0Pichichich

>1gcdnPPichichn=0gcd

Dilawar
quelle
Sie verwechseln Periodizität mit Reduzierbarkeit. Wenn die Kette nicht reduzierbar ist, ist es möglich, von einem Zustand in einen anderen zu wechseln. Die Periodizität ist bei MCMC wichtig, da, obwohl möglicherweise jeder Zustand erreicht wird (Irreduzibilität), die Konvergenz (as) zur Zielverteilung von der zusätzlichen Eigenschaft der Aperiodizität abhängt. Siehe zum Beispiel "Asymptotische Varianz und Konvergenzraten von nahezu periodischen MCMC-Algorithmen" von Rosenthal (2001).
Anne van Rossum