Markov-Keðja

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).

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

${\displaystyle \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 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.

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

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

${\displaystyle p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,}$ 

og í einu skrefi eru líkurnar

${\displaystyle 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

${\displaystyle p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}}$ 

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

${\displaystyle \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

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ð

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

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ð ${\displaystyle 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

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

${\displaystyle 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.

• Markov ákvarðanaferli