Lanci Markova

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.

Lanci Markova imaju mnoštvo aplikacija kao statistički modeli procesa stvarnog sveta, kao što je izučavanje kontrolnih sistema tempomata u motornim vozilima, utvrđivanje trendova redova ili linija putnika koji dolaze na aerodrom, varijacija deviznih kurseva i populacione dinamike životinja. Markovljevi procesi su osnova za opšti stohastički metod simulacija, poznat kao Markovljev lanac Monte Karlo, koji se koristi za simulaciju uzorkovanja iz složenih distribucija verovatnoće i koji je našao primenu u Bajesovoj statistici i veštačkoj inteligenciji.

Formalna definicija

Lanci Markova predstavljaju značajnu klasu zavisnih slučajnih promenljivih. Niz slučajnih promenljivih X₁, X₂, X₃, … 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 < k < n,

$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{aligned}&{}\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{aligned}}$

što je trebalo dokazati.

Marginalna raspodela Pr(X_n = x) je raspodela nad stanjima u trenutku n. Početna raspodela je Pr(X₀ = 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 $\mathbf {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 $\mathbf {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 $\mathbf {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 $\mathbf {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 $\mathbf {y}$ vektor kolona sa r elemenata, od kojih je najveći M₀, a najmanji m₀. Neka su M₁ i m₁ 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 $\mathbf {y}$, najveće moguće očekivanje se može dobiti ako svi (osim jednog) elementi vektora $\mathbf {y}$ imaju vrednost M₀, a jedan ima vrednost m₀, 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}\leq (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 $\mathbf {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}\geq M_{1}\geq M_{2}...$ i $m_{0}\leq m_{1}\leq m_{2}...$. Oba ova niza su monotona i ograničena, $m_{0}\leq m_{n}\leq M_{n}\leq 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\leq M$. Treba da dokažemo da je M-m=0. Pokazali smo da važi $M_{n}-m_{n}\leq (1-2l)(M_{n-1}-m_{n-1})$. Iz ovoga je očigledno $M_{n}-m_{n}\leq (1-2l)^{n}(M_{0}-m_{0})$. Kako je $r\geq 2$, tako mora biti i $l\leq 1/2$, tj. $0\leq 1-2l\leq 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 $\mathbf {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 $\mathbf {y}$ (sa jednom jedinicom i svim nulama), $\mathbf {Py}$ je j-ta kolona od $\mathbf {P}$, a svi njeni elementi su pozitivni (po našoj početnoj pretpostavci). Najmanji element vektora $\mathbf {Py}$ je definisan kao $m_{1}$ , pa je $m_{1}>0$. Kako je $m_{1}\leq 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.

Literatura

• A. A. Markov (1906) "Rasprostranenie zakona bol'shih chisel na velichiny, zavisyaschie drug ot druga". Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp. 135–156.
• A. A. Markov. "Extension of the limit theorems of probability theory to a sum of variables connected in a chain". reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.
• Classical Text in Translation: Markov, A. A. (2006). Prevod: Link, David. „An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains”. Science in Context. 19 (4): 591—600. doi:10.1017/s0269889706001074. 
• Leo Breiman (1992) [1968] Probability. Original edition published by Addison-Wesley; reprinted by Society for Industrial and Applied Mathematics ISBN 0-89871-296-3. (See Chapter 7)
• J. L. Doob (1953) Stochastic Processes. New York: John Wiley and Sons ISBN 0-471-52369-0.
• S. P. Meyn and R. L. Tweedie (1993) Markov Chains and Stochastic Stability. London: Springer-Verlag ISBN 0-387-19832-6. online: MCSS . Second edition to appear, Cambridge University Press, 2009.
• S. P. Meyn. Control Techniques for Complex Networks. Cambridge University Press, 2007. ISBN 978-0-521-88441-9. Appendix contains abridged Meyn & Tweedie. online: Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st izd.). New York, NY: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.  Extensive, wide-ranging book meant for specialists, written for both theoretical computer scientists as well as electrical engineers. With detailed explanations of state minimization techniques, FSMs, Turing machines, Markov processes, and undecidability. Excellent treatment of Markov processes pp. 449ff. Discusses Z-transforms, D transforms in their context.
• Kemeny, John G.; Hazleton Mirkil; J. Laurie Snell; Gerald L. Thompson (1959). Finite Mathematical Structures (1st izd.). Englewood Cliffs, NJ: Prentice-Hall, Inc. Library of Congress Card Catalog Number 59-12841.  Classical text. cf Chapter 6 Finite Markov Chains pp. 384ff.
• John G. Kemeny & J. Laurie Snell (1960) Finite Markov Chains, D. van Nostrand Company ISBN 0-442-04328-7
• E. Nummelin. "General irreducible Markov chains and non-negative operators". Cambridge University Press, 1984, 2004. ISBN 0-521-60494-X
• Seneta, E. Non-negative matrices and Markov chains. 2nd rev. ed., 1981, XVI, 288 p., Softcover Springer Series in Statistics. (Originally published by Allen & Unwin Ltd., London, 1973) ISBN 978-0-387-29765-1
• Kishor S. Trivedi, Probability and Statistics with Reliability, Queueing, and Computer Science Applications, John Wiley & Sons, Inc. New York, 2002. ISBN 0-471-33341-7.
• K. S. Trivedi and R.A.Sahner, SHARPE at the age of twenty-two, vol. 36, no. 4, pp. 52–57, ACM SIGMETRICS Performance Evaluation Review, 2009.
• R. A. Sahner, K. S. Trivedi and A. Puliafito, Performance and reliability analysis of computer systems: an example-based approach using the SHARPE software package, Kluwer Academic Publishers, 1996. ISBN 0-7923-9650-2.
• G. Bolch, S. Greiner, H. de Meer and K. S. Trivedi, Queueing Networks and Markov Chains, John Wiley, 2nd edition, 2006. ISBN 978-0-7923-9650-5.

Spoljašnje veze

• Introduction to Markov Chains na sajtu YouTube
• Hazewinkel, Michiel, ur. (2001) [1994], „Markov chain”, Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• Techniques to Understand Computer Simulations: Markov Chain Analysis
• Markov Chains chapter in American Mathematical Society's introductory probability book Arhivirano na sajtu Wayback Machine (22. maj 2008)(pdf)
• A beautiful visual explanation of Markov Chains
• Making Sense and Nonsense of Markov Chains Arhivirano na sajtu Wayback Machine (4. februar 2020)
• Original paper by A.A Markov(1913): An Example of Statistical Investigation of the Text Eugene Onegin Concerning the Connection of Samples in Chains (translated from Russian)