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

Из Википедије, слободне енциклопедије

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

Дакле, поред дате садашњости, будућност не зависи од прошлости. Ништа што се догодило у прошлости, не утиче, не даје прогнозу у погледу будућности, у будућности је све могуће. Основни пример је бацање новчића – ако први пут добијемо главу, други пут с подједнаким шансама можемо добити главу или писмо. Ако пак добијамо главу 100 пута заредом, и тада је вероватноћа да ћемо 101. пут добити главу иста као и да ћемо добити писмо – другим речима, прошлост не предвиђа будући резултат. Тренутно стање је да имамо новчић са главом и писмом на своје две стране. Претпостављајући правилна извођења експеримента, ништа друго не може утицати на будући исход.

Други пример може да буде случајна шетња по бројној оси, где се, при сваком кораку, позиција мења за 1 (у једном или другом смеру једнако вероватно). Са сваке позиције постоје два могућа прелаза: на следећи или на претходни цео број. Вероватноће прелаза тада зависе само од тренутног стања, а не од начина како се до њега дошло. На пример, ако је тренутна позиција -3, прелаз у -2 има вероватноћу 0,5, без обзира на претходне позиције.

У сваком тренутку систем, на основу дате расподеле случајне променљиве, може променити стање, или остати у истом. Промене стања називамо прелазима, а вероватноће, које се односе на различите промене стања, називамо вероватноћама прелаза.

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

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

\Pr(X_{n+1}=x|X_n=x_n, \ldots, X_1=x_1) = \Pr(X_{n+1}=x|X_n=x_n).\,

Могуће вредности Xi су из пребројивог скупа 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{align}
& {} \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{align}

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


Маргинална расподела Pr(Xn = x) је расподела над стањима у тренутку n. Почетна расподела је Pr(X0 = 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 елемената, од којих је највећи M0, а најмањи m0. Нека су M1 и m1 највећа и најмања компонента (респективно) вектора \mathbf{P}^n\mathbf{y}. Пошто је сваки елемент матрице \mathbf{P}^n\mathbf{y} математичко очекивање елемената из \mathbf{y}, највеће могуће очекивање се може добити ако сви (осим једног) елементи вектора \mathbf{y} имају вредност M0, а један има вредност m0, и он се множи са l, да би најмање доприносио. У том случају математичко очекивање износи

lm_0+(1-l)M_0 .

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

lM_0+(1-l)m_0 .

Тако,

M_1-m_1 \le(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 (јер се иначе своди на тривијално). Нека су Mn и mn, респективно, максимална и минимална компонента вектора \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 \ge M_1 \ge M_2... и m_0 \le m_1 \le m_2... . Оба ова низа су монотона и ограничена, m_0 \le m_n \le M_n \le M_0 . Према томе, оба низа ће имати граничну вредност кад n тежи бесконачности (низови су конвергентни). Нека је M гранична вредност од Mn, а m од mn. Знамо да је m \le M . Треба да докажемо да је M-m=0. Показали смо да важи M_n - m_n \le (1-2l)(M_{n-1} - m_{n-1}) . Из овога је очигледно M_n - m_n \le (1-2l)^n(M_0 - m_0) . Како је r \ge 2 , тако мора бити и l \le 1/2 , тј. 0 \le 1-2l \le 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 \le m , имамо да је и m > 0 , а ова вредност m је заправо ј-та компонента од p*, па су према томе све компоненте p* строго позитивне.

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