Markov-keðja

Í stærðfræði er Markov-keðja 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.

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:

Hugsanleg gildi "X"i 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.

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 formula_2 til þess að tákna stakið í "i"-tu línu og "j"-ta dálk á fylkinu formula_3.

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

og í einu skrefi eru líkurnar

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

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

Þættanleiki.

Staða "j" er sögð aðgengileg frá stöðu "i" (ritað "i" → "j") 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ð

Staða "i" er sögð tengd við stöðu "j" (ritað "i" ↔ "j") 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ð formula_9, þá 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.

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

Ef "k" = 1 er staðan sögð vera ólotubundin; annars (k&gt;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.