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

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

${\displaystyle \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. Овај скуп назива се скуп стања. Ланце Маркова можемо приказати и усмереним графовима, где су чворови поједина стања, а вредности написане на гранама представљају вероватноће прелаза (у одговарајућем смеру).

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

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

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

Ланци Маркова реда m (са меморијом m) су они за које важи (за коначно m):

${\displaystyle \Pr(X_{n}=x_{n}|X_{n-1}=x_{n-1},X_{n-2}=x_{n-2},\dots ,X_{1}=x_{1})}$

${\displaystyle =\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 ради се о простом ланцу Маркова.

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

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

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

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

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

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

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

и

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

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

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

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

Доказ

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

${\displaystyle {\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)-ти елемент једнак

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

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

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

Доказ

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

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

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

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

Тако,

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

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

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