Ланци Маркова

У математици ланац Маркова означава дискретни Марковљев случајни процес. Име је добио по Марков Андреју, руском математичару, који је глас стекао својим истраживањима у овој грани науке. Имати својство Маркова значи, укратко, да поред датог тренутног стања, будуће стање система не зависи од прошлих. Другим речима, то значи, да опис садашњости у потпуности садржи информацију која може утицати на будуће стање процеса.

Дакле, поред дате садашњости, будућност не зависи од прошлости. Ништа што се догодило у прошлости, не утиче, не даје прогнозу у погледу будућности, у будућности је све могуће. Основни пример је бацање новчића – ако први пут добијемо главу, други пут с подједнаким шансама можемо добити главу или писмо. Ако пак добијамо главу 100 пута заредом, и тада је вероватноћа да ћемо 101. пут добити главу иста као и да ћемо добити писмо – другим речима, прошлост не предвиђа будући резултат. Тренутно стање је да имамо новчић са главом и писмом на своје две стране. Претпостављајући правилна извођења експеримента, ништа друго не може утицати на будући исход. Други пример може да буде случајна шетња по бројној оси, где се, при сваком кораку, позиција мења за 1 (у једном или другом смеру једнако вероватно). Са сваке позиције постоје два могућа прелаза: на следећи или на претходни цео број. Вероватноће прелаза тада зависе само од тренутног стања, а не од начина како се до њега дошло. На пример, ако је тренутна позиција −3, прелаз у −2 има вероватноћу 0,5, без обзира на претходне позиције. У сваком тренутку систем, на основу дате расподеле случајне променљиве, може променити стање, или остати у истом. Промене стања називамо прелазима, а вероватноће, које се односе на различите промене стања, називамо вероватноћама прелаза.

Ланци Маркова имају мноштво апликација као статистички модели процеса стварног света, као што је изучавање контролних система темпомата у моторним возилима, утврђивање трендова редова или линија путника који долазе на аеродром, варијација девизних курсева и популационе динамике животиња. Марковљеви процеси су основа за општи стохастички метод симулација, познат као Марковљев ланац Монте Карло, који се користи за симулацију узорковања из сложених дистрибуција вероватноће и који је нашао примену у Бајесовој статистици и вештачкој интелигенцији.

Формална дефиниција

Ланци Маркова представљају значајну класу зависних случајних променљивих. Низ случајних променљивих X₁, X₂, X₃, … називамо ланцем Маркова, ако важи својство Маркова, тј.:

$\Pr(X_{n+1}=x|X_{n}=x_{n},\ldots ,X_{1}=x_{1})=\Pr(X_{n+1}=x|X_{n}=x_{n}).\,$

Могуће вредности X_i су из пребројивог скупа S. Овај скуп назива се скуп стања. Ланце Маркова можемо приказати и усмереним графовима, где су чворови поједина стања, а вредности написане на гранама представљају вероватноће прелаза (у одговарајућем смеру).

Типови

Говоримо о ланцу Маркова са стационарним вероватноћама стања (хомогеном ланцу Маркова), ако вероватноће прелаза не зависе од времена, то јест:

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

независно од n.

Ланци Маркова реда m (са меморијом m) су они за које важи (за коначно 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})$

за свако n. Другим речима, будуће стање зависи од m пређашњих. У случају m=1 ради се о простом ланцу Маркова.

Особине ланаца Маркова

Прво је потребно да уведемо појам вероватноће прелаза за један корак:

$p_{ij}=\Pr(X_{1}=j\mid X_{0}=i).\,$

и појам вероватноће прелаза за n корака:

$p_{ij}^{(n)}=\Pr(X_{n}=j\mid X_{0}=i)\,$

Прво означава вероватноћу прелаза из стања i у стање j из једног корака, а потоње из n корака, под претпоставком да је $Pr(X_{0}=i)>0$.

За хомогене ланце Маркова:

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

и

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

па прелазак из n корака задовољава једначину Чепман-Колмогорова, да за свако k за које важи 0 < k < n,

$p_{ij}^{(n)}=\sum _{r\in S}p_{ir}^{(k)}p_{rj}^{(n-k)}$

где је S скуп стања ланца Маркова.

Доказ

Применом својства Маркова и уопштене формуле тоталне вероватноће, важи следеће:

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

што је требало доказати.

Маргинална расподела Pr(X_n = x) је расподела над стањима у тренутку n. Почетна расподела је Pr(X₀ = x).

Ергодичност

Ланац Маркова се назива ергодичан ако је могуће прећи из било ког стања у било које стање (не обавезно у једном кораку).

Регуларност

Ланац Маркова је регуларан ако неки степен матрице прелаза има само позитивне елементе. Другим речима, за неко n, могуће је прећи из било ког стања у било које друго стање у тачно n корака. Из дефиниције се види да је сваки регуларан ланац и ергодичан, обрнуто не мора да важи.

Матрица прелаза је матрица чији је (i, j)-ти елемент једнак

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

и она показује како су распоређене вероватноће прелаза.

Фундаментална гранична теорема за регуларне ланце Маркова

Нека је P матрица прелаза за регуларан ланац. Тада $\lim _{n\rightarrow \infty }\mathbf {P} ^{n}=\mathbf {P} ^{*}$, где је P* матрица чије су све врсте једнаке p*. Све компоненте вектора p* су позитивне, и збир им је 1.

Доказ

Треба, у суштини, доказати да елементи сваке колоне матрице $\mathbf {P} ^{n}$ теже да буду једнаки (тј. да су све врсте те матрице једнаке). Напоменимо да ј-та колона од $\mathbf {P} ^{n}$ је $\mathbf {P} ^{n}\mathbf {y}$ где је $\mathbf {y}$ вектор колона са јединицом на ј-том месту, и нулама на осталим местима. Према томе, практично треба доказати да за сваки вектор колону $\mathbf {y}$, $\mathbf {P} ^{n}\mathbf {y}$ тежи константном вектору кад n тежи бесконачности. Како је свака врста матрице P вектор вероватноћа, $\mathbf {P} ^{n}\mathbf {y}$ замењује $\mathbf {y}$ са математичким очекивањима његових компоненти (врши неку врсту упросечавања). Компоненте вектора $\mathbf {P} ^{n}\mathbf {y}$ су ближе једна другој него компоненте вектора $\mathbf {y}$. Показаћемо да разлика између максималне и минималне компоненте тежи нули кад n тежи бесконачности. То у суштини значи да вероватноћа да ће се систем наћи у неком стању после великог броја корака не зависи од почетног стања. Нека је P матрица прелаза димензија r×r, без нултих елемената. Узмимо да је l најмања вредност у тој матрици. Нека је $\mathbf {y}$ вектор колона са r елемената, од којих је највећи M₀, а најмањи m₀. Нека су M₁ и m₁ највећа и најмања компонента (респективно) вектора $\mathbf {P} ^{n}\mathbf {y}$. Пошто је сваки елемент матрице $\mathbf {P} ^{n}\mathbf {y}$ математичко очекивање елемената из $\mathbf {y}$, највеће могуће очекивање се може добити ако сви (осим једног) елементи вектора $\mathbf {y}$ имају вредност M₀, а један има вредност m₀, и он се множи са l, да би најмање доприносио. У том случају математичко очекивање износи

$lm_{0}+(1-l)M_{0}$.

Слично, најмање могуће очекивање је једнако

$lM_{0}+(1-l)m_{0}$.

Тако,

$M_{1}-m_{1}\leq (lm_{0}+(1-l)M_{0})-(lM_{0}+(1-l)m_{0})=(1-2l)(M_{0}-m_{0})$.

Ово ће нам помоћи у доказу фундаменталне граничне теореме за регуларне ланце Маркова. Доказаћемо теорему за специјалан случај да је P без елемената који су једнаки нули, а после ћемо уопштити. Нека је $\mathbf {y}$ вектор колона са r елемената, где је r број стања у ланцу. Претпоставићемо да је r>1 (јер се иначе своди на тривијално). Нека су M_n и m_n, максимална и минимална компонента вектора $\mathbf {P} ^{n}\mathbf {y}$. Вектор $\mathbf {P} ^{n}\mathbf {y}$ се добија множењем (слева) вектора $\mathbf {P} ^{n-1}\mathbf {y}$ вектором P. Према томе, свака компонента вектора $\mathbf {P} ^{n}\mathbf {y}$ представља средњу вредност компоненти из $\mathbf {P} ^{n-1}\mathbf {y}$. Тако је $M_{0}\geq M_{1}\geq M_{2}...$ и $m_{0}\leq m_{1}\leq m_{2}...$. Оба ова низа су монотона и ограничена, $m_{0}\leq m_{n}\leq M_{n}\leq M_{0}$. Према томе, оба низа ће имати граничну вредност кад n тежи бесконачности (низови су конвергентни). Нека је M гранична вредност од M_n, а m од m_n. Знамо да је $m\leq M$. Треба да докажемо да је M-m=0. Показали смо да важи $M_{n}-m_{n}\leq (1-2l)(M_{n-1}-m_{n-1})$. Из овога је очигледно $M_{n}-m_{n}\leq (1-2l)^{n}(M_{0}-m_{0})$. Како је $r\geq 2$, тако мора бити и $l\leq 1/2$, тј. $0\leq 1-2l\leq 1$, а пошто се број између 0 и 1 диже на експонент који тежи бесконачности, јасно је да ће разлика $M_{n}-m_{n}$ тежити тада нули. Према томе, сви елементи $\mathbf {P} ^{n}\mathbf {y}$ ће тежити неком броју u. Нека је сада $\mathbf {y}$ вектор чија је ј-та компонента једнака 1, а све остале су једнаке нули. Тада је $\mathbf {P} ^{n}\mathbf {y}$ ј-та колона од $\mathbf {P} ^{n}$. Понављајући поступак за свако ј доказује се да колоне $\mathbf {P} ^{n}$ теже константим векторима колонама. Може се рећи да врсте матрице $\mathbf {P} ^{n}$ теже заједничком вектору врсти p*, tj. $\lim _{n\rightarrow \infty }\mathbf {P} ^{n}=\mathbf {P} ^{*}$. Остало је да се докаже да су сви елементи матрице P* строго позитивни. Ако узмемо исти вектор колону $\mathbf {y}$ (са једном јединицом и свим нулама), $\mathbf {Py}$ је ј-та колона од $\mathbf {P}$, а сви њени елементи су позитивни (по нашој почетној претпоставци). Најмањи елемент вектора $\mathbf {Py}$ је дефинисан као $m_{1}$ , па је $m_{1}>0$. Како је $m_{1}\leq m$, имамо да је и $m>0$, а ова вредност m је заправо ј-та компонента од p*, па су према томе све компоненте p* строго позитивне.

Овај доказ се, међутим, односио на случај да P нема нултих елемената (нисмо претпоставили да је P регуларна). Претпоставимо да је P регуларна. Тада, за неко N, $\mathbf {P} ^{N}\mathbf {y}$ нема нула. Дати доказ показује да M_nN-m_nN тежи нули кад n тежи бесконачности. Али, разлика M_nN-m_nN се не може повећавати (кад је l=0, у најгорем случају разлика може остати иста). Ако знамо да разлике које се добију посматрањем сваких N пута теже нули, тада и цео низ мора тежити нули. Тиме је доказ завршен.

Литература

• 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). Превод: 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 изд.). 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 изд.). 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.

Спољашње везе

• Introduction to Markov Chains на сајту YouTube
• Hazewinkel, Michiel, ур. (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 Архивирано на сајту Wayback Machine (22. мај 2008)(pdf)
• A beautiful visual explanation of Markov Chains
• Making Sense and Nonsense of Markov Chains Архивирано на сајту Wayback Machine (4. фебруар 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)