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 *X<sub>1</sub>*, *X<sub>2</sub>*, *X<sub>3</sub>*... 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 *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*&nbsp;+&nbsp;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 *p<sub>ij</sub>* 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 0p_{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*0 = *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
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ð 

:  \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ð 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

:  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


## Tengt efni
* Markov ákvarðanaferli