Procesi Markova sa diskretnim vremenom

  • Kod procesa Markova sa diskretnim vremenom, parametarski skup je prebrojiv.

  • Ako je skup stanja takođe konačan ili prebojiv pričamo o lancima Markova.

Slučajni niz {X n |n ≥ 0} je lanac Markova ako za svaki trenutak n ≥ 0 i za sva stanja i0, i1, ..., in - 1, i, j ∈ ℤ važi sledeća jednakost

P{X n + 1 = j|X n = i, X n − 1 = i n − 1 ,…, X 0 = i 0} = P{X n + 1 = j|X n = i}

Poslednju jednakost, koja zapravo predstavlja matematički zapisano svojstvo Markova, možemo formulisati i ovako: pri fiksiranom stanju i u momentu n dalje ponašanje procesa ne zavisi od toga na koji način je proces došao u stanje i i od toga kroz koja stanja je proces prolazio do trenutka n .

Uvodimo oznaku:

p i j (n) = P{X n + 1 = j|X n = i}

kojom označavamo verovatnoću prelaska sistema iz stanja i u stanje j.

Lanac Markova je homogen ukoliko za svako n i svaka dva stanja i i j važi da je p i j (n) = p i j , što znači da verovatnoća prelaska iz stanja i u stanje j ne zavisi od trenutka u kom se taj prelaz dešava.

Dalji sadržaj kursa se odnosi samo na homogene lance.

Za svaki homogen lanac {X n , n ≥ 0} važi da je matrica verovatnoća prelaskaP = [p i j ]|ℤ|x|ℤ| stohastička, tačnije da za nju važe svojstva:

1. p ij ≥ 0 za sve i,j ∈ ℤ

2. ∑ j p i j = 1 za svako i ∈ ℤ

Možemo da primetimo da jednačina Kolmogorov-Čepmena zapravo predstavlja raspisano matrično množenje. Iz toga slede sledeće formule:

P m + n = P m P n ,
P n = P n

Razmnožavanje graška (lanac Markova sa konačnim brojem stanja)

Navešćemo primer poznatog Mendelovog eksperimenta iz genetike. Gen koji odredjuje da li je seme graška glatko ili naborano se sastoji od 2 alela: A (dominantni alel) I a (recesivni alel). Kada dodje do ukrštanja dve biljke, biljka potomak će dobiti po jedan alel (izabran na slučajan način) od svake od njih. Novodobijena kombinacija alela predstavlja genotip potomka. Genotip potomka može biti- aa, aA i AA. Istim postupkom se ukrštanje nastavlja kroz generacije.
Neka je X n genotip potomka u n -toj generaciji.Tada je {X n | n ∈ ℕ0} lanac Markova sa skupom stanja {AA, Aa, aa}. Ovde važi svojstvo Markova zato što genotip potomka zavisi samo od genotipa roditelja, a ne od genotipa ranijih predaka.

Sada treba odrediti verovatnoću prelaska za ovaj lanac. Razmotrimo slučaj prelaska iz stanja Aa u sva ostala stanja. Verovatnoća da se dobije genotip aa jednaka je proizvodu verovatnoće da se od obe jedinke uzme recesivni alel a, što je 1/2*1/2=1/4. Verovatnoća da se dobije genotip AA je takodje, na isti način, 1/4.Verovatnoća da se dobije genotip Aa jednaka je verovatnoći da se od prve jedinke uzme A i od druge a ili da se od prve jedinke uzme a i od druge A, što je, 1/2*1/2+1/2*1/2=1/2. U slučaju stanja aa, verovatnoća prelaska u stanje aa je 1, a u sva ostala stanja je 0. Na isti način, u slučaju prelaska iz stanja AA u stanje AA, verovatnoća je 1, dok je za ostala stanja verovatnoća 0. Prikazaćemo prvo matricu prelaska:

Kad iskoristimo       , dobijamo sledeće matrice 

Ponavljajući postupak, posle n koraka dobijamo matricu:

Kada pustimo da n teži beskonačnosti, dobijamo matricu:

Iz ove matrice i reda koji smo uokvirili, možemo da zaključimo da će posle velikog broja generacija genotip Aa skoro sigurno nestati.

Najduži neprekidni niz kod bacanja novčića (lanac Markova sa beskonačno mnogo stanja)

Baca se fer novčić i registruje da li je palo pismo (P) ili glava (G). Neka je X n najduži neprekidan niz G u trenutku n.
Tada je {X n |n∈ ℕ} lanac Markova sa skupom stanja ℕ0 . Matrica verovatnoće prelaska bi izgledala ovako:

Kako je ova matrica beskonačne dimenzije, ne možemo primenjivati matrično množenje kao u prethodnom primeru.

I ovaj primer možemo prikazati grafički

Klasifikacija ​​stanja

Stanja se kod lanaca Markova mogu razlikovati i po tome koliko često (sa kolikom verovatnoćom) se lanac u njih vraća, tj. da li se to dešava skoro sigurno (sa verovatnoćom 1), ili sa nekom manjom verovatnoćom. Odgovor na to pitanje se zove klasifikacija stanja.

Neka je {X t |t ∈ ℕ0} lanac Markova.
Stanje i je povratno ako

P{X n = i za neko n ≥ 1|X 0 = i} = 1.

Stanje i je prolazno ako

P{X n = i za neko n ≥ 1|X 0 = i} < 1.

Jednostavnije rečeno:
Stanje i je povratno ako će se proces skoro sigurno vratiti u početno stanje, a ako je i prolazno verovatnoća da se lanac ikad u njega vrati je manja od jedan, tj. sa nekom pozitivnom verovatnoćom se to nikad neće desiti.

Takođe, često je bitno odrediti da li se iz jednog određenog stanja može stići u neko drugo (ili svako drugo), ili je neka od verovatnoća prelaska jednaka nuli.

Kažemo da i komunicira sa j ako

∃n ≥ 0 P{X n = j|X 0 = i} > 0

Za stanja i i j za koje postoji pozitivna verovatnoća prelaska u oba smera (iz i u j i iz j u i) kažemo međusobno komuniciraju. ​Može se pokazati da za svaka dva stanja koja međusobno komuniciraju važi da su ili oba povratna, ili oba prolazna.

Stanje i je apsorbujuće ako se nakon ulaska u to stanje, iz njega ne može izaći.

Neka je E podskup skupa svih stanja. Skup E je zatvoren ako je

∀i ∈ E , j ∉ E, p i j = 0 .

tj. ako se lanac nađe u nekom od stanja iz tog skupa, verovatnoća da napusti taj skup stanja je 0.
Skup je nerazloživ ako proizvoljna dva stanja iz tog skupa međusobno komuniciraju.

Društvo za životno osiguranje želi da sazna koliko treba da naplati svojim klijentima. Jasno, kompanija mora imati predstavu o tome koliko dugo će klijenti živeti. Predlaže se sledeći model koji sumira zdravstveno stanje pojedinca na mesečnom nivou:

H - zdrav, S - bolestan, D - mrtav

Dakle, postoji verovatnoća p H, S = 0.3 da će se osoba razboleti, a da je trenutno zdrav, itd.

Očigledno D je apsorbujući. H,S su prolazna stanja i čine nerazloživ skup koji nije zatvoren.

Stacionarna raspodela

(π i ), i ∈ ℤ je stacionarna raspodela akko

π j = ∑ i ∈ ℤ π i p i j , j ∈ ℤ.

Ovo daje praktičan način da se odredi stacionarna raspodela: rešavanjem matrične jednačine π = π • P

Ako nas zanima koliko često (koji deo ukupnog vremena) se lanac Markova nalazi u svakom od mogućih stanja (koliko puta je vrednost tog slučajnog niza jednaka i, za i iz skupa stanja), onda je potrebno da odredimo stacionarnu raspodelu

Stacionarna raspodela daje proporciju vremena koju sistem provodi u pojedinačnim stanjima do trenutka n, za veliko n.
Stacionarna raspodela ne mora da postoji ili da bude jedinstvena.

Sada ćemo se vratiti na prethodno objašnjeni primer iz genetike (razmnožavanje graška) i pokušati da odredimo da li postoji stacionarna raspodela i da je pronađemo.
Ovde je π = (π 1,π 2,π 3) . Jednakost π = π • P ima raspisani oblik

Odakle sledi

(π 1,π 2,π 3) = (π 1+π 2/4,π 2/2,π 2/4+π 3) .

Uz uslov π 1 + π 2 + π 3 = 1, dobija se da stacionarnih raspodela ima beskonačno mnogo i imaju oblik

(π 1,π 2,π 3) = (α,0,1−α) , α ∈ [0,1].

Miš se nalazi u lavirintu koji ima dve prostorije, označimo ih, redom, sa 1 i 2. U prostoriji 1 se nalazi svež sir, a u prostoriji 2 budjav. Posao naučnika je da u svakom minutu zabeleži položaj miša. Kada je miš u ćeliji 1 u trenutku n (minuta), tada je u trenutku n+1 ili još uvek u 1 ili je prešao u 2.  Statistička zapažanja navode naučnika da veruje da se miš kreće od prostorije 1 do prostorije 2 sa verovatnoćom ​α = 0,05; to čini, bez obzira na to gde je bio u ranijim trenucima. Slično, kreće se od 2 do 1 sa verovatnoćom ​β = 0,99.

Postavlja se pitanje koliko vremena miš provodi u kojoj ćeliji? Da bismo to odredili treba nam stacionarna raspodela tj. moramo da rešimo sistem jednačina.

0.95p 1 + 0, 99p 2 = p 1
 p 1 + p 2 = 1

I dobijamo da miš provodi p 1 = 0.952% vremena u ćeliji 1.

Slučajno lutanje

Do sada smo detaljnije analizirali primere lanaca Markova kod kojih je skup stanja konačan, što nam je omogućavalo da verovatnoće prelaska u jednom ili više koraka dobijamo množenjem ili stepenovanjem matrica. Sada ćemo videti kako se verovatnoće prelaska mogu odrediti za jedan beskonačan lanac. U pitanju je poznati matematički model - slučajno lutanje. Pojavljuje se kao stohastički model za kretanje objekta (čestice), koje se realizuje kroz niz koraka (skokova) u slučajno odabranim pravcima tj. smerovima. 

Neka je (X n ) n ∈ ℕ niz nezavisnih, jednako raspoređenih slučajnih veličina.

Neka je S 0 = 0 i za svako n ∈ ℕ s a S n označen parcijalni zbir S n = S 0 + ∑ j=1 n X j .

Slučajan niz (S n ) n ∈ ℕ naziva se jednodimenziono slučajno lutanje.

Ako je X n niz d-dimenzionih slučajnih vektora, onda je S n d-dimenziono slučajno lutanje.

Fokusiraćemo se na jednodimenziono slučajno lutanje​.

Kod jednodimenzionog slučajnog lutanja, slučajne veličine X k su takve da

P{X k = 1} = p , P{X k =  −1} = 1 − p , k ∈ ℕ

Verovatnoće prelaska su:

Verovatnoće prelaska u n koraka: Ako je napravljeno x koraka u pozitivnom i y u negativnom smeru: x + y = n , x − y = j − i
odakle se dobija x = (n + j − i) / 2 , y = (n − j + i) / 2
Kada iskoristimo činjenicu da broj koraka mora biti ceo, dobijamo:

Sve moguće vrednosti  u svakom koraku

Hajde da vidimo neka svojstva za simetrično slučajno lutanje tj. p = 0.5

Koliko je P{X n > 0} ?
Iz prethodnog znamo da je

Kako je (X n ) n ∈ ℕ0 simetrično slučajno lutanje, važi jednakost P{X n < 0} = P{X n > 0} .
Iz jednakosti P{X n < 0} + P{X n > 0} + P{X n = 0} = 1 , sledi da je P{X n > 0} = (1 − P{X n = 0}) / 2 .

Koliko je P{X 1 ≥ 0, X 2 ≥ 0, ..., X 2n − 1 ≥ 0|X 2n = 0} ?

Traženu verovatnoću ćemo odrediti kombinatorno.
Ukupan broj realizacija (opisanih putanja) takvih da je X 2n = 0 je

Odredimo broj realizacija koji ne odgovara glavnom događaju, tj. broj realizacija takvih da je bar za neko i (i = 1, 2, ..., 2n−1) narušeno

X i ≥ 0|X 2n = 0 tj. važi X i < 0|X 2n = 0 .

Ako takvo i postoji, realizacija će u trenutku i spustila na nivo −1 (X i = −1) .

Kod slučajnog lutanja važi princip refleksije i on nam kaže da postoji isti broj realizacija od tačke (0,0) koje završavaju u (n,y) i koje završavaju u (n,−y) .

Znači od tačke (i,−1) isto nam je da li posmatramo realizacije koje završavaju u (2n,0) ili (2n,−2) .

Odatle broj realizacija koje nam ne odgovaraju (narušavaju svojstvo X i ≥ 0) dobijamo iz jednakosti:

y = x + 2, x + y = 2n ⇒ y = n + 1, x = n − 1 .

Tražena verovatnoća je jednaka:

Website Templates

created with

Website Builder Software .