Markovljev lanac

Iz Wikipedije, slobodne enciklopedije

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[uredi - уреди | uredi izvor]

Lanci Markova predstavljaju značajnu klasu zavisnih slučajnih promenljivih. Niz slučajnih promenljivih X1, X2, X3, … nazivamo lancem Markova, ako važi svojstvo Markova, tj.:

Moguće vrednosti Xi 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[uredi - уреди | uredi izvor]

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

nezavisno od n.

Lanci Markova reda m (sa memorijom m) su oni za koje važi (za konačno 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[uredi - уреди | uredi izvor]

Prvo je potrebno da uvedemo pojam verovatnoće prelaza za jedan korak:

i pojam verovatnoće prelaza za n koraka:

Prvo označava verovatnoću prelaza iz stanja i u stanje j iz jednog koraka, a potonje iz n koraka, pod pretpostavkom da je .

Za homogene lance Markova:

i

pa prelazak iz n koraka zadovoljava jednačinu Čepman-Kolmogorova, da za svako k za koje važi 0 < k < n,

gde je S skup stanja lanca Markova.

Dokaz

Primenom svojstva Markova i uopštene formule totalne verovatnoće, važi sledeće:

što je trebalo dokazati.

Marginalna raspodela Pr(Xn = x) je raspodela nad stanjima u trenutku n. Početna raspodela je Pr(X0 = x).

Ergodičnost[uredi - уреди | uredi izvor]

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[uredi - уреди | uredi izvor]

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

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

Fundamentalna granična teorema za regularne lance Markova[uredi - уреди | uredi izvor]

Neka je P matrica prelaza za regularan lanac. Tada , 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 teže da budu jednaki (tj. da su sve vrste te matrice jednake). Napomenimo da j-ta kolona od je 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, teži konstantnom vektoru kad n teži beskonačnosti. Kako je svaka vrsta matrice P vektor verovatnoća, zamenjuje y sa matematičkim očekivanjima njegovih komponenti (vrši neku vrstu uprosečavanja). Komponente vektora 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 M0, a najmanji m0. Neka su M1 i m1 najveća i najmanja komponenta (respektivno) vektora . Pošto je svaki element matrice 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 M0, a jedan ima vrednost m0, i on se množi sa l, da bi najmanje doprinosio. U tom slučaju matematičko očekivanje iznosi

.

Slično, najmanje moguće očekivanje je jednako

.

Tako,

.

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 Mn i mn, respektivno, maksimalna i minimalna komponenta vektora . Vektor se dobija množenjem (sleva) vektora vektorom P. Prema tome, svaka komponenta vektora predstavlja srednju vrednost komponenti iz . Tako je i . Oba ova niza su monotona i ograničena, . 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 Mn, a m od mn. Znamo da je . Treba da dokažemo da je M-m=0. Pokazali smo da važi . Iz ovoga je očigledno . Kako je , tako mora biti i , tj. , a pošto se broj između 0 i 1 diže na eksponent koji teži beskonačnosti, jasno je da će razlika težiti tada nuli. Prema tome, svi elementi ć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 j-ta kolona od . Ponavljajući postupak za svako j dokazuje se da kolone teže konstantim vektorima kolonama. Može se reći da vrste matrice teže zajedničkom vektoru vrsti p*, tj. . 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 m1, pa je m1>0. Kako je , 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, nema nula. Dati dokaz pokazuje da MnN-mnN teži nuli kad n teži beskonačnosti. Ali, razlika MnN-mnN 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.