Monte karlo metode I primene u bioinformatici master rad

2.3 Markovljevi lanci

Markovljevi lanci spadaju u relativno jednostavnu, ali i veoma interesantnu klasu slučajnih procesa. Oni opisuju slučajne pojave ili sisteme koji se menjaju tokom vremena, a njihova jednostavna struktura omogućava nam da saznamo mnogo toga o njihovom ponašanju u budućnosti. Ako uzmemo u obzir poznavanje nekih informacija o prošlim stanjima, uslovna raspodela budućih stanja sistema zavisi samo od onih najskorijih. Dakle možemo da kažemo da predviđanje budućnosti sistema zavisi samo od sadašnjeg stanja, a ne i od puta kojim je sistem došao do tog stanja.

Lanci Markova predstavljaju jedan od najprostijih matematičkih modela za opisivanje pojava u realnom zivotu. Pravilo da su najjednostavniji modeli često i najkorisniji za analizu praktičnih problema ne zaobilazi ni Markovljeve lance. Njima se mogu modelirati mnoge pojave, kao što su pojave u biologiji, psihologiji, sportu i dr [4].

Prilikom posmatranja određenih sistema, ponekad nam je važno da odredimo kako se stanje nekog sistema menja s vremenom. Ako stanje sistema predstavlja vrednost slučajne promenljive, sledi da nas zanima promena slučajne promenljive u zavisnosti od vremena. Ponašanje posmatranog sistema opisuje se stohastičkim procesom. Poseban oblik stohastičkog procesa je Markovljev proces odnosno Markovljev lanac.

Neka X_t predstavlja veličinu posmatranu u svakom trenutku t nekog vremenskog intervala T, koja nije unapred određena već se realizuje slučajno, a predstavlja stanje sistema u posmatranom trenutku t. Skup svih slučajnih veličina X_t posmatramo kao slučajnu promenljivu koja se menja u zavisnosti od vremena t.
Definicija: Stohastički proces { X_t : t T} je Markovljev proces prvog reda ako za proizvoljan izbor vremenskih trenutaka < < … < T i proizvoljne vrednosti , _{, ,} …, važi:

.
Predhodna relacija izražava tzv. Markovljevo svojstvo koje opisuje činjenicu da raspodela verovatnoće slučajne promenljive u trenutku t = zavisi samo od vrednosti sistema u trenutku, a ne zavisi od vrednosti sistema u ranijim trenucima. Radi jednostavnijeg zapisa, stanje sistema u trenutnku

emo označavati sa i govoriti o njemu kao o n-tom koraku sistema. U zavisnosti od toga da li je T diskretan ili neprekidan skup, razlikujemo procese Markova sa diskretnim i neprekidnim vremenom. Sve vrednosti koje može da uzme slučajna veličina X_t čine skup stanja ili prostor stanja koji označavamo sa S. Ako je skup S diskretan tj. konačan ili prebrojiv tada se proces Markova zove lanac Markova.

Definicija: Lanac Markova je slučajni proces { X_t : t T} koji ima svojstvo Markova tj. proces gde za svaki prirodni broj n > 2 i svaki izbor stanja , ,…, S važi:

.
Verovatnoća da se u trenutku posle jednog koraka pređe iz stanja u stanje označavamo sa:

, ,…,

ukoliko verovatnoća ne zavisi od trenutka , tada pišemo samo

Ovakvi lanci se nazivaju homogeni.

Za verovatnoću prelaska iz stanja u stanje posle koraka kosristimo oznaku . Sada možemo uvesti pojam matrice verovatnoće prelaska lanca Markova u -tom koraku.

Uočimo da za matricu važi za svako . Matrice sa ovakvim svojstvom nazivaju se stohastičkim matricama [7].

Da bismo Markovljev lanac u potpunosti opisali moramo, osim matrice verovatnoće prelaska, poznavati i vektor početnih vrednosti, koji predstavlja stanje Markovljevog lanca u početnom trenutku posmatranja, tj. vrednost slučajne promenljive X₀.

Vektor početnih vrednosti označimo sa:

gde je:

tj. verovatnoća da se sistem na početku nalazi stanju .

Na isti način definišemo vektor stanja u n-tom koraku (ili nakon n koraka):

pri čemu je:

.

Takođe, jasno je da i ovi vektori stanja moraju biti stohastički, tj. mora važiti:

i .

Ako nam je poznat vektor početnih stanja, onda se -ti element vektora stanja u -tom koraku računa:

Izraz na kraju gornje jednakosti predstavlja j-ti element umnoška vektora početnih vrednosti matricom . Iz toga sledi da je:

odnosno, ako želimo odrediti vektore stanja u svim koracima imamo

Objasnimo ukratko klasifikaciju stanja Markovljevog lanca kako bismo lakše formulisali naredne definicije [6]:

• 
  Za dva stanja i i j, putanja od i do j je niz prelaza koji počinju u i i završavaju u j, tako da je pri svakom prelazu u nizu verovatnoća pozitivna.
  
• 
  Stanje j je dostupno iz stanja i ako postoji putanja koja vodi od i do j.
  
• 
  Dva stanja su povezana ako je stanje j dostupno iz i, i ako je stanje i dostupno iz j
  
• 
  Skup stanja S u Markoljevom lancu je zatvoren skup ako ne postoji stanje izvan skupa S koje je dostupno iz nekog stanja iz S.
  
• 
  Stanje i je apsorbujuće ako je .
  
• 
  Stanje i je prelazno stanje ako postoji stanje j koje je dostupno iz i, ali stanje i nije dostupno iz stanja j. Prelazno stanje omogućuje da napustimo stanje i ali se više nikada u njega ne vraćamo.
  
• 
  Stanje koje nije prelazno, naziva se rekurentno stanje (povratno stanje).
  
• 
  Stanje i je periodično sa periodom k > 1 ako je k najmanji broj takav da sve putanje vode iz stanja i ponovo u stanje i, i koje imaju dužinu jednaku deliocu broja k. Ako rekurentno stanje nije periodično, ono je aperiodično.
  

Definicija: Za Markovljev lanac u kome su sva stanja međusobno rekurentna, aperiodična i povezana kaže se da je ergodičan (regularan).
Regularnom Markovljevom lancu pripada regularna matrica verovatnoće prelaza, odakle sledi da postoji , takav da je za sve To znači, da Markovljev lanac iz proizvoljnog stanja, nakon određenog broja koraka može preći u bilo koje drugo stanje. Na osnovu navedenog jasno je da apsorbujući Markovljev lanac ne može biti regularan.
Definicija: Stohastički vektor =() nazivamo vektorom stacionarnih vrednosti ako važi:


Ako je , onda je zbog gornje jednakosti , odakle sledi da je i . Regularni Markovljevi lanaci imaju jedinstven vektor stacionarnih vrednosti. Ako je P matrica verovatnoće prelaza regularnog Markovljevog lanca, onda je:

pa iz ove jednakosti sledi:

gde je ta koordinata vektora stacionarnih vrednosti. To znači da nakod određenog broja koraka više nije važno koje je početno stanje sistema već će se sistem bez obzira na to naći u stanju sa verovatnoćom [7].