Kan noen forklare meg på en intuitiv måte hva periodisiteten til en Markov-kjede er?
Den er definert som følger:
For alle stater $ i $ i $ S $
$ d_i $ = gcd $ \ {n \ in \ mathbb {N} | p_ {ii} ^ {(n)} > 0 \} = 1 $
Takk for innsatsen!
Kan noen forklare meg på en intuitiv måte hva periodisiteten til en Markov-kjede er?
Den er definert som følger:
For alle stater $ i $ i $ S $
$ d_i $ = gcd $ \ {n \ in \ mathbb {N} | p_ {ii} ^ {(n)} > 0 \} = 1 $
Takk for innsatsen!
Først og fremst er definisjonen din ikke helt riktig. Her er den riktige definisjonen fra wikipedia, som foreslått av Cyan.
Periodisitet (kilde: wikipedia)
En tilstand i har periode k hvis noen tilbakevending til tilstand i må forekomme i flere k-trinn. Formelt er perioden for en tilstand definert som
k = $ gcd \ {n: \ Pr (X_n = i | X_0 = i) > 0 \} $
(hvor "gcd" er den største felles divisoren). Merk at selv om en tilstand har periode k, er det kanskje ikke mulig å nå tilstanden i k trinn. Anta for eksempel at det er mulig å gå tilbake til staten i {6, 8, 10, 12, ...} tidstrinn; k ville være 2, selv om 2 ikke vises i denne listen.
Hvis k = 1, sies staten å være aperiodisk: returnerer til tilstand i kan forekomme på uregelmessige tider. Med andre ord er en tilstand i aperiodisk hvis det eksisterer n slik at for alle n '≥ n,
$ Pr (X_ {n'} = i | X_0 = i) > 0. $
Ellers (k> 1), sies staten å være periodisk med periode k. En Markov-kjede er aperiodisk hvis hver tilstand er aperiodisk.
Min forklaring
Begrepet periodicitet beskriver om noe (en hendelse, eller her: besøket av en bestemt stat) skjer med jevne mellomrom. Her måles tiden i antall stater du besøker.
Første eksempel:
Tenk deg at klokken representerer en markovkjede og hver time markerer en tilstand, så vi fikk 12 stater. Hver tilstand blir sett på av timeviseren hver 12. time (stater) med sannsynlighet = 1, så den største fellesdeleren er også 12.
Så hver (time-) tilstand er periodisk med periode 12.
Andre eksempel:
Se for deg en graf som beskriver en sekvens med myntkast, startende ved stat $ start $ og stat $ heads $ og $ haler $ som representerer utfallet av det siste myntkastet.
Overgangssannsynligheten er 0,5 for hvert par stater (i, j), bortsett fra $ heads $ -> $ start $ og $ haler $ -> $ start $ der det er 0.
Tenk deg at du er i staten $ heads $. Antall stater du må besøke før du besøker $ heads $ igjen kan være 1,2,3 osv. Det vil skje, så sannsynligheten er større 0, men det er ikke akkurat forutsigbart når. Så den største vanlige avdelingen av alle mulige antall besøk som kan oppstå før du besøker $ heads $ igjen er 1. Dette betyr at $ heads $ er aperiodisk.
Det samme gjelder $ tails $. Siden det ikke gjelder $ start $, er ikke hele grafen aperiodisk. Hvis vi fjerner $ start $, vil det være det.
Mange ganger ønsker vi å vite om det ikke er noen sjanse for at vi vil bli sittende fast i en tilstand av kjeden min. Slike stater kalles 'aperiodiske' stater. De er enkle å tallfeste: hvis jeg ikke får $ P ^ n_ {ii} = 0 $ for noen $ n \ gt 0 $, hevder jeg at en slik tilstand er aperiodisk ($ P_ {ii} $ er sannsynligheten for bor i staten $ i $). En tilstand som ikke er aperiodisk er periodisk. Men terminologien er litt uheldig fordi vi med periode vanligvis mener en fast verdi hvoretter et system gjentar seg.
I Markov-kjeden har vi ikke luksus av "alltid en fast verdi" for perioden. Vi kan gå tilbake til en periodisk tilstand i et hvilket som helst $ > 1 $ antall trinn. Vi kjører kjeden og noterer tallene og tar gcd
av disse tallene. Sannsynligvis har denne definisjonen noen fordeler ved å bevise andre teorem; Jeg har ingen anelse om det. Hvis du ikke vil simulere kjeden, notatet ned tallet, kan du notere kraften $ n $ som overgangsmatrisen $ P $ blir hevet slik at $ P ^ n_ {ii} = 0 $ og ta