Markovljev lanac

U matematici **lanac Markova** označava diskretni Markovljev slučajni proces. Ime je dobio po Markov Andreju, ruskom matematičaru, koji je glas stekao svojim istraživanjima u ovoj grani nauke. Imati svojstvo Markova znači, ukratko, da *pored datog trenutnog stanja*, buduće stanje sistema ne zavisi od prošlih. Drugim rečima, to znači, da opis sadašnjosti u potpunosti sadrži informaciju koja može uticati na buduće stanje procesa.

Dakle, pored date sadašnjosti, budućnost ne zavisi od prošlosti. Ništa što se dogodilo u prošlosti, ne utiče, ne daje prognozu u pogledu budućnosti, u budućnosti je sve moguće. Osnovni primer je bacanje novčića – ako prvi put dobijemo glavu, drugi put s podjednakim šansama možemo dobiti glavu ili pismo. Ako pak dobijamo glavu 100 puta zaredom, i tada je verovatnoća da ćemo 101. put dobiti glavu ista kao i da ćemo dobiti pismo – drugim rečima, prošlost ne predviđa budući rezultat. Trenutno stanje je da imamo novčić sa glavom i pismom na svoje dve strane. Pretpostavljajući pravilna izvođenja eksperimenta, ništa drugo ne može uticati na budući ishod.

Drugi primer može da bude slučajna šetnja po brojnoj osi, gde se, pri svakom koraku, pozicija menja za 1 (u jednom ili drugom smeru jednako verovatno). Sa svake pozicije postoje dva moguća prelaza: na sledeći ili na prethodni ceo broj. Verovatnoće prelaza tada zavise samo od trenutnog stanja, a ne od načina kako se do njega došlo. Na primer, ako je trenutna pozicija -3, prelaz u -2 ima verovatnoću 0,5, bez obzira na prethodne pozicije.

U svakom trenutku sistem, na osnovu date raspodele slučajne promenljive, može promeniti stanje, ili ostati u istom. Promene stanja nazivamo prelazima, a verovatnoće, koje se odnose na različite promene stanja, nazivamo verovatnoćama prelaza.

## Formalna definicija
**Lanci Markova** predstavljaju značajnu klasu zavisnih slučajnih promenljivih. Niz slučajnih promenljivih *X*1, *X*2, *X*3, … nazivamo lancem Markova, ako važi svojstvo Markova, tj.:

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

Moguće vrednosti *X**i* su iz prebrojivog skupa *S*. Ovaj skup naziva se **skup stanja**. Lance Markova možemo prikazati i usmerenim grafovima, gde su čvorovi pojedina stanja, a vrednosti napisane na granama predstavljaju verovatnoće prelaza (u odgovarajućem smeru).

### Tipovi
Govorimo o **lancu Markova sa stacionarnim verovatnoćama stanja** (homogenom lancu Markova), ako verovatnoće prelaza ne zavise od vremena, to jest:

:\Pr(X_{n+1}=j \mid X_n=i) = p_{ij}\,

nezavisno od *n*.

**Lanci Markova reda ''m'' **
(sa memorijom *m*) su oni za koje važi (za konačno *m*):

:\Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots , X_{1}=x_{1})
:  = \Pr(X_n=x_n|X_{n-1}=x_{n-1}, X_{n-2}=x_{n-2}, \dots, X_{n-m}=x_{n-m})
    
za svako *n*. Drugim rečima, buduće stanje zavisi od *m* pređašnjih. U slučaju *m*=1 radi se o prostom lancu Markova.

## Osobine lanaca Markova
Prvo je potrebno da uvedemo pojam verovatnoće prelaza za jedan korak:

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

i pojam verovatnoće prelaza za *n* koraka:

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

Prvo označava verovatnoću prelaza iz stanja *i* u stanje *j* iz jednog koraka, a potonje iz *n* koraka, pod pretpostavkom da je
Pr(X_0=i)>0.

Za homogene lance Markova:

:p_{ij} = \Pr(X_{k+1}=j \mid X_k=i). \,

i

:p_{ij}^{(n)} = \Pr(X_{n+k}=j \mid X_{k}=i) \,

pa prelazak iz *n* koraka zadovoljava **jednačinu Čepman-Kolmogorova**, da za svako *k* za koje važi 0&nbsp;p_{ij}^{(n)} = \sum_{r \in S} p_{ir}^{(k)} p_{rj}^{(n-k)}

gde je *S* skup stanja lanca Markova.

**Dokaz**

Primenom svojstva Markova i uopštene formule totalne verovatnoće, važi sledeće:
:
\begin{align}
& {} \quad p_{ij}^{(n)} = \Pr(X_{n}=j \mid X_{0}=i) = \sum_{r \in S} \Pr(X_{n}=j \mid X_{k}=r,X_{0}=i)\Pr(X_{k}=r \mid X_{0}=i)\\
& =\sum_{r \in S} \Pr(X_{n}=j \mid X_{k}=r)\Pr(X_{k}=r \mid X_{0}=i)=\sum_{r \in S} p_{ir}^{(k)}p_{rj}^{(n-k)}
\end{align}


što je trebalo dokazati.

Marginalna raspodela Pr(*X**n*&nbsp;=&nbsp;*x*) je raspodela nad stanjima u trenutku *n*. Početna raspodela je Pr(*X*0&nbsp;=&nbsp;*x*).

### Ergodičnost
Lanac Markova se naziva ergodičan ako je moguće preći iz bilo kog stanja u bilo koje stanje (ne obavezno u jednom koraku).

### Regularnost
Lanac Markova je regularan ako neki stepen matrice prelaza ima samo pozitivne elemente. Drugim rečima, za neko n, moguće je preći iz bilo kog stanja u bilo koje drugo stanje u tačno n koraka. Iz definicije se vidi da je svaki regularan lanac i ergodičan, obrnuto ne mora da važi.

Matrica prelaza je matrica čiji je (*i*, *j*)-ti element jednak

:p_{ij} = \Pr(X_{n+1}=j\mid X_n=i). \,

i ona pokazuje kako su raspoređene verovatnoće prelaza.

#### Fundamentalna granična teorema za regularne lance Markova
Neka je **P** matrica prelaza za regularan lanac. Tada
\lim_{n\rightarrow\infty}\mathbf{P}^n=\mathbf{P}^*,
gde je **P*** matrica čije su sve vrste jednake **p***. Sve komponente vektora **p*** su pozitivne, i zbir im je 1.

**Dokaz**

Treba, u suštini, dokazati da elementi svake kolone matrice \mathbf{P}^n teže da budu jednaki (tj. da su sve vrste te matrice jednake). Napomenimo da j-ta kolona od \mathbf{P}^n je \mathbf{P}^n\mathbf{y} gde je **y** vektor kolona sa jedinicom na j-tom mestu, i nulama na ostalim mestima. Prema tome, praktično treba dokazati da za svaki vektor kolonu y, \mathbf{P}^n\mathbf{y} teži konstantnom vektoru kad *n* teži beskonačnosti. Kako je svaka vrsta matrice **P** vektor verovatnoća, \mathbf{P}^n\mathbf{y} zamenjuje **y** sa matematičkim očekivanjima njegovih komponenti 
(vrši neku vrstu uprosečavanja). Komponente vektora \mathbf{P}^n\mathbf{y} su bliže jedna drugoj nego komponente vektora **y**. Pokazaćemo da razlika između maksimalne i minimalne komponente teži nuli kad *n* teži beskonačnosti. To u suštini znači da verovatnoća da će se sistem naći u nekom stanju posle velikog broja koraka ne zavisi od početnog stanja.
Neka je **P** matrica prelaza dimenzija *r*×*r*, bez nultih elemenata. Uzmimo da je *l* najmanja vrednost u toj matrici. Neka je **y** vektor kolona sa *r* elemenata, od kojih je najveći *M*0, a najmanji *m*0. Neka su *M*1 i *m*1 najveća i najmanja komponenta (respektivno) vektora \mathbf{P}^n\mathbf{y}. 
Pošto je svaki element matrice \mathbf{P}^n\mathbf{y} matematičko očekivanje elemenata iz **y**, najveće moguće očekivanje se može dobiti ako svi (osim jednog) elementi vektora **y** imaju vrednost *M*0, a jedan ima vrednost *m*0, i on se množi sa *l*, da bi najmanje doprinosio. U tom slučaju matematičko očekivanje iznosi 
:lm_0+(1-l)M_0 .
Slično, najmanje moguće očekivanje je jednako
:lM_0+(1-l)m_0 .
Tako,
:M_1-m_1 \le(lm_0+(1-l)M_0)-(lM_0+(1-l)m_0)=(1-2l)(M_0-m_0) .
Ovo će nam pomoći u dokazu fundamentalne granične teoreme za regularne lance Markova.
Dokazaćemo teoremu za specijalan slučaj da je **P** bez elemenata koji su jednaki nuli, a posle ćemo uopštiti. Neka je **y** vektor kolona sa *r* elemenata, gde je *r* broj stanja u lancu. Pretpostavićemo da je *r*>1 (jer se inače svodi na trivijalno). Neka su *M*n i *m*n, respektivno, maksimalna i minimalna komponenta vektora \mathbf{P}^n\mathbf{y}. Vektor \mathbf{P}^n\mathbf{y} se dobija množenjem (sleva) vektora \mathbf{P}^{n-1}\mathbf{y} vektorom **P**.
Prema tome, svaka komponenta vektora \mathbf{P}^n\mathbf{y} predstavlja srednju vrednost komponenti iz \mathbf{P}^{n-1}\mathbf{y}. Tako je M_0 \ge M_1 \ge M_2...  i
m_0 \le m_1 \le m_2... .
Oba ova niza su monotona i ograničena, m_0 \le m_n \le M_n \le M_0 . Prema tome, oba niza će imati graničnu vrednost kad *n* teži beskonačnosti (nizovi su konvergentni). Neka je *M* granična vrednost od *M*n, a *m* od *m*n. Znamo da je m \le M . Treba da dokažemo da je *M*-*m*=0. Pokazali smo da važi M_n - m_n \le (1-2l)(M_{n-1} - m_{n-1}) . Iz ovoga je očigledno M_n - m_n \le (1-2l)^n(M_0 - m_0) .
Kako je r \ge 2 , tako mora biti i l \le 1/2 , tj. 0 \le 1-2l \le 1 , a pošto se broj između 0 i 1 diže na eksponent koji teži beskonačnosti, jasno je da će razlika M_n - m_n  težiti tada nuli. Prema tome, svi elementi \mathbf{P}^n\mathbf{y} će težiti nekom broju *u*. Neka je sada **y** vektor čija je j-ta komponenta jednaka 1, a sve ostale su jednake nuli. Tada je \mathbf{P}^n\mathbf{y} j-ta kolona od \mathbf{P}^n.
Ponavljajući postupak za svako j dokazuje se da kolone \mathbf{P}^n teže konstantim vektorima kolonama. Može se reći da vrste matrice \mathbf{P}^n teže zajedničkom vektoru vrsti **p***, tj. \lim_{n\rightarrow\infty}\mathbf{P}^n=\mathbf{P}^*.
Ostalo je da se dokaže da su svi elementi matrice **P*** strogo pozitivni. Ako uzmemo isti vektor kolonu **y** (sa jednom jedinicom i svim nulama), **Py** je j-ta kolona od **P**, a svi njeni elementi su pozitivni (po našoj početnoj pretpostavci). Najmanji element vektora **Py** je definisan kao *m*1, pa je *m*1>0. Kako je m_1 \le m , imamo da je i *m*>0, a ova vrednost *m* je zapravo *j*-ta komponenta od **p***, pa su prema tome sve komponente **p*** strogo pozitivne.

Ovaj dokaz se, međutim, odnosio na slučaj da **P** nema nultih elemenata (nismo pretpostavili da je **P** regularna). Pretpostavimo da je **P** regularna. Tada, za neko *N*, \mathbf{P}^N\mathbf{y} nema nula. Dati dokaz pokazuje da *M**nN*-*m**nN* teži nuli kad *n* teži beskonačnosti. Ali, razlika *M**nN*-*m**nN* se ne može povećavati (kad je *l*=0, u najgorem slučaju razlika može ostati ista). Ako znamo da razlike koje se dobiju posmatranjem svakih *N* puta teže nuli, tada i ceo niz mora težiti nuli. Time je dokaz završen.