Intuicyjne wyjaśnienie okresowości w łańcuchach Markowa

17

Czy ktoś może mi wyjaśnić intuicyjnie, jaka jest częstotliwość łańcucha Markowa?

Jest on zdefiniowany w następujący sposób:

Dla wszystkich stanów i w S

di = gcd{nN|pii(n)>0}=1

Dziękuję za Twój wysiłek!

Chris
źródło
1
Znalazłem zwięzłe i jasne napisanie Wikipedii . Czy to działa dla ciebie?
Cyan
2
Definicja w OP nazywa się „aperioidyczna”.
Jack

Odpowiedzi:

28

Po pierwsze, twoja definicja nie jest całkowicie poprawna. Oto poprawna definicja z wikipedii, zgodnie z sugestią Cyana.


Okresowość (źródło: wikipedia )

Stan i ma okres k, jeśli jakikolwiek powrót do stanu i musi nastąpić w wielokrotności k kroków czasowych. Formalnie okres stanu określa się jako

k = gcd{n:Pr(Xn=i|X0=i)>0}

(gdzie „gcd” jest największym wspólnym dzielnikiem). Należy zauważyć, że chociaż stan ma okres k, osiągnięcie stanu w krokach może nie być możliwe. Załóżmy na przykład, że można powrócić do stanu w przedziałach czasowych {6, 8, 10, 12, ...}; k byłoby 2, mimo że 2 nie pojawia się na tej liście.

Jeśli k = 1, wówczas mówi się, że stan jest nieokresowy: powrót do stanu i może wystąpić w nieregularnych momentach. Innymi słowy, stan i jest nieokresowy, jeśli istnieje n takie, że dla wszystkich n '≥ n,

P.r(Xn=ja|X0=ja)>0.

W przeciwnym razie (k> 1), stan jest określany jako okresowy z okresem k. Łańcuch Markowa jest nieokresowy, jeśli każdy stan jest nieokresowy.


Moje wyjaśnienie

Termin okresowość opisuje, czy coś (zdarzenie lub tutaj: wizyta określonego stanu) dzieje się w regularnych odstępach czasu. Tutaj czas mierzony jest liczbą odwiedzonych stanów.

Pierwszy przykład:

wprowadź opis zdjęcia tutaj

Teraz wyobraź sobie, że zegar reprezentuje łańcuch markowa i co godzinę zaznacza stan, więc mamy 12 stanów. Każdy stan jest odwiedzany przez wskazówkę godzinową co 12 godzin (stanów) z prawdopodobieństwem = 1, więc największy wspólny dzielnik to również 12.

Tak więc każdy (godzinny) stan jest okresowy z okresem 12.

Drugi przykład:

Wyobrazić wykres opisujący kolejność rzutów monet, począwszy od stanu i stan H e d s i t i L y reprezentującą wynik ostatniego monetą.stzartheadstails

wprowadź opis zdjęcia tutaj

Prawdopodobieństwo przejścia wynosi 0,5 dla każdej pary stanów (i, j), z wyjątkiem -> s t a r t i t a i l s -> s t a r t, gdzie wynosi 0.headsstarttailsstart

headsheadsheadsheads

tailsstartstart

steffen
źródło
0

n>0Piin=0Piii

>1gcdnPPiin=0gcd

Dilawar
źródło
Mylisz okresowość ze zmniejszalnością. Jeśli łańcuch jest nieredukowalny, możliwe jest przejście z dowolnego stanu do dowolnego innego stanu. Okresowość jest ważna w MCMC, ponieważ chociaż każdy stan może zostać osiągnięty (nieredukowalność), zbieżność (as) z rozkładem docelowym zależy od dodatkowej właściwości aperiodiczności. Patrz na przykład „Asymptotyczne wariancje i zbieżność prawie okresowych algorytmów MCMC” autorstwa Rosenthal (2001).
Anne van Rossum