Markov-keðja

Úr Wikipediu, frjálsa alfræðiritinu
Stökkva á: flakk, leita

Í stærðfræði er Markov-keðja[1] strjált slembiferli með Markov eiginleikann, nefnt eftir Andrey Markov.

Markov keðja lýsir stöðu kerfis á mismunandi tímum. Á mismunandi stundum kann kerfið að hafa breyst frá þeirri stöðu sem það var í stundinni áður yfir í aðra stöðu, eða verið áfram í sömu stöðu. Stöðubreytingarnar eru kallaðar færslur. Markov eiginleikinn er sá að skilyrta líkindadreifingin á stöðunni á morgun, gefið stöðuna í dag og stöðurnar í fortíðinni, eru einungis háðar stöðunni í dag, og ekki neinum fyrri stöðum. (Hér er dagur notuð sem tímaeining, en hvaða tímaeiningu sem er má nota).

Skilgreining[breyta]

Markov keðja er runa af slembibreytum X1, X2, X3... með Markov eiginleikann, sem er, gefið núverandi stöðu, séu stöður í framtíðinni og fortíðinni óháðar. Formlega:

\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1, X_0=x_0) = \Pr(X_{n+1}=x|X_n=x_n).\,

Hugsanleg gildi Xi eru teljanlegt mengi S, sem kallast ástandsrúm keðjunar. (Einnig eru til samfelld Markov ferli sem hafa teljanleg ástandsrúm en samfeldan vísi). Markov keðjum er oft lýst með örvaneti, þar sem að leggirnir eru merktir með líkindum færslunnar.

Endanleg stöðuvél er dæmi um Markov keðju. Ef að stöðuvél er í stöðunni y á tíma n, þá eru líkur þess að það fari yfir í stöðu x á tíma n + 1 eingöngu háð stöðunni x, en er óháð tímanum n.

Eiginleikar Markov keðja[breyta]

Hægt er að skrifa upp ástandsrúm Markov keðju með n stöður sem n×n ferningsfylki P. Þá er pij færslan frá stöðu i á stöðu j. Við ritum p_{ij}^{(n)} til þess að tákna stakið í i-tu línu og j-ta dálk á fylkinu P^n.

Líkurnar á færslu frá stöðu i yfir á stöðu j í n skrefum er

p_{ij}^{(n)} = \Pr(X_n=j\mid X_0=i) \,

og í einu skrefi eru líkurnar

p_{ij} = \Pr(X_1=j\mid X_0=i) \,

n-skrefa færsla fullnægir Chapman-Kolmogorov jöfnunni, um að fyrir 0<k<n gildi

p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}

Jaðardreifingin Pr(Xn = x) er dreifingin yfir stöður á tíma n. Upphafsdreifingin er Pr(X0 = x). Breyting keðjunnar á einu tímaskrefi er lýst sem

 \Pr(X_{n+1}=j) = \sum_{r \in S} p_{rj} Pr(X_n=r) = \sum_{r \in S} p_{rj}^{(n)} Pr(X_0=r)

Þættanleiki[breyta]

Staða j er sögð aðgengileg frá stöðu i (ritað ij) ef, gefið að við erum í stöðu i, eru líkurnar á að staðan verði j á einhverjum tímapunkti í framtíðinni meiri en núll. Það er að segja, til er n þannig að

 \Pr(X_{n}=j | X_0=i) > 0.\,

Staða i er sögð tengd við stöðu j (ritað ij) ef að hvorttveggja gildir að i er aðgengilegt frá j og að j er aðgengilegt frá i. Mengi staða er kallaður tengdur flokkur ef sérhvert par af stöðum í C er tengt. Hægt er að sýna að tengsl í þessum skilningi séu jafngildisvensl. Tengdur flokkur er lokaður ef að líkurnar á því að yfirgefa flokkinn eru núll, þ.e.a.s, ef að i \in C, j \notin C, þá er j ekki aðgengilegt frá i.

Markov keðja er sögð óþættanleg ef að ástandsrúmið er tengt; þ.e., að hægt sé að komast frá hvaða stöðu sem er að hvaða stöðu sem er.

Lotubinding[breyta]

Staða i hefur lotu k ef að staðan getur eingöngu verið heimsótt í margfeldi k skrefa. Til dæmis, ef að eingöngu er hægt að fara aftur á stöðu i eftir sléttan fjölda hreyfinga, þá er staðan i lotubundin með lotuna 2. Formlega er lota stöðu skilgreind sem

 k = \operatorname{ssd}\{ n: Pr(X_n = i | X_0 = i) > 0\}

(þar sem að "ssd" er stærsti samdeilir)

Ef k = 1 er staðan sögð vera ólotubundin; annars (k>1), er staðan sögð lotubundin með lotuna k.

Hægt er að sýna fram á það að allar stöður í tengdum flokki verða að hafa sömu lotu.

Óþættanleg Markov keðja er sögð vera ólotubundin ef að stöður hennar eru ólotubundnar.

Tilvísanir[breyta]

  1. Markov chain 1. Markov-keðja á Orðaskrá Íslenska stærðfræðafélagsins

Tengt efni[breyta]