Ланцюг Маркова

Матриця ймовірностей переходу і граф переходів однорідного ланцюга Маркова з п'ятьма станами

Ланцюг Маркова в математиці це випадковий процес, що задовольняє властивість Маркова і який приймає скінченну чи зліченну кількість значень (станів). Існують ланцюги Маркова як з дискретним так і з неперервним часом. В даній статті розглядається дискретний випадок.

Визначення

Інтуїтивне визначення

Нехай $I$ — деяка скінченна чи зліченна множина елементи якої називаються станами. Нехай деякий процес в момент часу n (де n=0,1,2,3…) може перебувати в одному із цих станів, а в час n+1 перейти в деякий інший стан (чи залишитися в тому ж). Кожен такий перехід називається кроком. Кожен крок не є точно визначеним. З певними ймовірностями процес може перейти в один з кількох чи навіть усіх станів. Якщо імовірності переходу залежать лише від часу n і стану в якому перебуває процес в цей час і не залежать від станів в яких процес перебував у моменти 0, 1, … , n-1 то такий процес називається (дискретним) ланцюгом Маркова. Ланцюг Маркова повністю задається визначенням ймовірностей p_i перебування процесу в стані $i\in I$ в час n=0 і ймовірностей $p_{ij}(n)$ переходу зі стану $i\in I$ в стан$j\in I$ в час n. Якщо ймовірності переходу не залежать від часу (тобто $p_{ij}(n)$ однакові для всіх n) то такий ланцюг Маркова називається однорідним. Саме однорідні ланцюги Маркова є найважливішими на практиці і найкраще вивченими теоретично. Тому саме їм приділятиметься найбільша увага у цій статті.

Формальне визначення

Послідовність дискретних випадкових величин $\{X_{n}\}_{n\geqslant 0}$ називається ланцюгом Маркова (з дискретним часом), якщо

$\mathbb {P} (X_{n+1}=i_{n+1}\mid X_{n}=i_{n},X_{n-1}=i_{n-1},\ldots ,X_{0}=i_{0})=\mathbb {P} (X_{n+1}=i_{n+1}\mid X_{n}=i_{n})$.

Тобто майбутні значення послідовності залежать лише від теперішнього стану і не залежать від минулих.

Матриця $P{(n)}$, де

$P_{ij}{(n)}\equiv \mathbb {P} (X_{n+1}=j\mid X_{n}=i)$

називається ма́трицею ймовірностей переходу на $n$-му кроці, а вектор $\mathbf {p} =(p_{1},p_{2},\ldots )^{\top }$, де

$p_{i}\equiv \mathbb {P} (X_{0}=i)$ — початковим розподілом ланцюга Маркова.

Очевидно, матриця ймовірностей переходу є стохастичною, тобто

$\sum \limits _{j=1}^{\infty }P_{ij}(n)=1,\quad \forall n\in \mathbb {N}$.

Ланцюг Маркова називається однорідним якщо:

$P_{ij}{(n)}=P_{ij},\quad \forall n\in \mathbb {N}$,

або еквівалентно:

$\Pr(X_{n+1}=j|X_{n}=i)=\Pr(X_{n}=j|X_{n-1}=i)\,$

для всіх n.

Граф переходів ланцюга Маркова

Поширеним способом візуального задання ланцюга Маркова є граф переходів. Вершини цього графа ототожнюються зі станами ланцюга Маркова, а орієнтовне ребро проходить з вершини i у вершину j проходить лише у випадку коли імовірність переходу між відповідними станами нерівна нулю. Дана ймовірність переходу також позначається біля відповідного ребра.

Теорема про матрицю ймовірностей переходу за n кроків

Нехай маємо однорідний ланцюг Маркова з матрицею ймовірностей переходу P. Позначимо:

$p_{i,j}^{(k)}=\mathbb {P} \left(X_{n+k}=j\mid X_{n}=i\right),$

Оскільки ланцюг Маркова є однорідним то дане означення не залежить від n. Тоді виконується рівність

$(P^{k})_{(i,j)}=\left(p_{i,j}^{(k)}\right).$

де $(P^{k})_{(i,j)}$  — елемент i-го рядка і j-го стовпчика матриці P^k.

Доведення

Доведення здійснюватимемо методом математичної індукції. Для одного кроку це є наслідком однорідності і визначення матриці ймовірностей переходу:

$\mathbb {P} \left(X_{n+1}=j\mid X_{n}=i\right)=\mathbb {P} \left(X_{1}=j\mid X_{0}=i\right)=P_{ij}$

Для $\scriptstyle \ k\$ кроків одержуємо:

${\begin{aligned}\mathbb {P} \left(X_{n}=i\land X_{n+k}=j\right)&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell \land X_{n+k}=j\right)\\&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell \right)\ \mathbb {P} \left(X_{n+k}=j\mid X_{n}=i,\,X_{n+k-1}=\ell \right)\\&=\sum _{\ell \in E}\mathbb {P} \left(X_{n}=i,\,X_{n+k-1}=\ell \right)\ p_{\ell ,j}\\&=\mathbb {P} \left(X_{n}=i\right)\ \sum _{\ell \in E}P_{i,\ell }^{k-1}\ p_{\ell ,j}\\&=\mathbb {P} \left(X_{n}=i\right)\ P_{i,j}^{k},\end{aligned}}:$

Остаточно $p_{i,j}^{(k)}={\frac {\mathbb {P} \left(X_{n}=i\land X_{n+k}=j\right)}{\mathbb {P} \left(X_{n}=i\right)}}=P_{i,j}^{k}$

при доведенні

• першої і другої рівності використана формула повної ймовірності,
• третьої рівності використана властивість Маркова,
• четвертої рівності використано припущення індукції для $\scriptstyle \ k-1,$
• п'ятої рівності використано означення множення матриць.

Відповідно, якщо $\mathbf {p} =(p_{1},p_{2},\ldots )^{\top }$  — початковий розподіл ланцюга Маркова, то $\left((P^{T})^{n}\mathbf {p} \right)$ є вектором розподілу ймовірностей перебування в різних станах в час n.

Властивості ланцюгів Маркова

Нерозкладність

Стан $j$ називається досяжним із стану $i$, якщо існує $n=n(i,j)$ таке, що

$p_{ij}^{(n)}\equiv \mathbb {P} (X_{n}=j\mid X_{0}=i)>0$.

Для цього факту використовується позначення $i\rightarrow j$.

Якщо одночасно $i\rightarrow j$ та $j\rightarrow i$, то використовується позначення $i\leftrightarrow j$. Дане відношення є відношенням еквівалентності. Якщо вся множина станів належить до одного класу еквівалентності, то такий ланцюг Маркова називається нерозкладним. Простіше ланцюг Маркова називається нерозкладним, якщо з будь-якого його стану можна досягти будь-який інший стан за скінченну кількість кроків.

Якщо з стану, що належить деякому класу можна перейти лише в інший стан цього класу то такий клас називається замкнутим.

Періодичність

Стан i має період k якщо будь-яке повернення до стану i трапляється через кількість кроків, що ділиться на k. Формально період можна визначити за допомогою наступної формули:

$k=\operatorname {gcd} \{n:\Pr(X_{n}=i|X_{0}=i)>0\}$

(де «gcd» позначає найбільший спільний дільник).

Якщо $k=1$, тоді стан називається аперіодичним. В іншому випадку ($k>1$), стан називається періодичним з періодом $k$. Ланцюг Маркова є апериодичним, якщо кожен стан є апериодичним. Для доведення апериодичності нерозкладного ланцюга Маркова, достатньо знайти хоча б один апериодичний стан. Бо в кожному класі досяжності всі стани мають однаковий період.

Кожен стан двочасткового графу має парний період.

Рекурентність

Стан i називається перехідним якщо, існує ненульова ймовірність, що починаючи з i, ми ніколи не повернемося в стан i. Більш формально нехай випадкова змінна T_i є часом першого повернення в стан i:

$T_{i}=\inf\{n\geq 1:X_{n}=i|X_{0}=i\}.$

Тоді стан i є перехідним тоді й лише тоді, коли:

$\Pr(T_{i}={\infty })>0.$

Якщо стан не є перехідним, то він називається рекурентним. Неважко помітити, що якщо стан є перехідним, то імовірність повернення в цей стан нескінченну кількість разів рівна нулю. У випадку рекурентного стану ця імовірність рівна одиниці. Тобто, перехідний — це такий стан, який процес в певний момент часу покидає назавжди, а рекурентний — це такий стан до якого процес постійно повертається.

Визначимо також математичне сподівання часу повернення:

$M_{i}=E[T_{i}].\,$

Для перехідного стану ця величина очевидно рівна нескінченності. Для рекурентних станів $\{M_{i}\}$ може бути як скінченним, так і нескінченним. Стан i називається позитивно рекурентним, якщо M_i є скінченне; в іншому випадку i називається нуль-рекурентним. Стан i є рекурентним тоді й лише тоді коли:

$\sum _{n=0}^{\infty }p_{ii}^{(n)}=\infty .$

В одному класі досяжності або всі елементи є перехідними або всі елементи є рекурентними. Стан i називається поглинаючим якщо його неможливо покинути. Тобто:

$p_{ii}=1,\quad p_{ij}=0\quad i\not =j.$

Ергодичність

Стан ланцюга Маркова, що є позитивно рекурентним і аперіодичним називається ергодичним станом.

Граничний розподіл

Для однорідного ланцюга Маркова вектор $\pi$ називається стаціонарним розподілом, якщо сума його елементів $\pi _{j}$ дорівнює 1 і виконується рівність

$\pi _{j}=\sum _{i\in S}\pi _{i}p_{ij}.$

Нерозкладний ланцюг має стаціонарний розподіл тоді й лише тоді, коли всі його стани є позитивно рекурентними. В цьому випадку вектор $\pi$ є єдиним і виконується рівність:

$\pi _{j}={\frac {1}{M_{j}}}.\,$

Якщо ланцюг окрім того є ще й аперіодичним, тоді для всіх i та j виконується:

$\pi _{j}=\lim _{n\rightarrow \infty }p_{ij}^{(n)}={\frac {1}{M_{j}}}.$

Такий вектор $\pi$ називається розподілом рівноваги.

Граничний розподіл для ланцюга Маркова зі скінченною множиною станів

У випадку скінченної множини станів $\pi$ є вектор-рядком, що задовольняє рівність:

$\pi =\pi \mathbf {P} .\,$

Тобто $\pi$ є власним вектором матриці ймовірностей переходу, що відповідає власному значенню 1 і сума елементів якого дорівнює одиниці.

Якщо ланцюг Маркова є нерозкладним і аперіодичним, тоді існує єдиний стаціонарний вектор і, крім того, виконується рівність:

$\lim _{k\rightarrow \infty }\mathbf {P} ^{k}=\mathbf {1} \pi$

де 1 вектор-стовпець всі елементи якого рівні 1.

Приклад

Розглянемо основні дії з ланцюгами Маркова на наступному прикладі:

$P={\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}$

Візьмемо початковий розподіл

$\mathbf {p} ^{(0)}={\begin{bmatrix}1&0&0\end{bmatrix}}$

Після першого кроку одержимо розподіл:

$\mathbf {p} ^{(1)}=\mathbf {p} ^{(0)}P={\begin{bmatrix}1&0&0\end{bmatrix}}{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}={\begin{bmatrix}0,9&0,05&0,05\end{bmatrix}}$

Після двох кроків отримаємо наступний розподіл:

$\mathbf {p} ^{(2)}=\mathbf {p} ^{(1)}P=\mathbf {p} ^{(0)}P^{2}={\begin{bmatrix}1&0&0\end{bmatrix}}{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}^{2}={\begin{bmatrix}0,885&0,045&0,07\end{bmatrix}}$

Далі можна продовжити за формулами:

$\mathbf {p} ^{(n)}=\mathbf {p} ^{(n-1)}P$

$\mathbf {p} ^{(n)}=\mathbf {p} ^{(0)}P^{n}$

Оскільки даний ланцюг Маркова є нерозкладний і аперіодичний існує єдиний граничний розподіл $\pi$ :

$\mathbf {\pi } =\lim _{n\to \infty }\mathbf {p} ^{(n)}$

Його можна знайти за такими формулами:

${\begin{aligned}\\\mathbf {\pi } P&=\mathbf {\pi } \qquad {\mbox{(}}\mathbf {\pi } {\mbox{ est la loi invariante par rapport a }}P{\mbox{.)}}\\&=\mathbf {\pi } I\\\mathbf {\pi } (I-P)&=\mathbf {0} \\&=\mathbf {\pi } \left({\begin{bmatrix}1&0&0\\0&1&0\\0&0&1\\\end{bmatrix}}-{\begin{bmatrix}0,9&0,05&0,05\\0,7&0&0,3\\0,8&0&0,2\\\end{bmatrix}}\right)\\&=\mathbf {\pi } {\begin{bmatrix}0,1&-0,05&-0,05\\-0,7&1&-0,3\\-0,8&0&0,8\\\end{bmatrix}}\\&={\begin{bmatrix}\pi _{1}&\pi _{2}&\pi _{3}\end{bmatrix}}{\begin{bmatrix}0,1&-0,05&-0,05\\-0,7&1&-0,3\\-0,8&0&0,8\\\end{bmatrix}}\\&={\begin{bmatrix}0&0&0\end{bmatrix}}\end{aligned}}$

З умови $q_{1}+q_{2}+q_{3}=1$,одержується єдиний результат :

${\begin{bmatrix}\pi _{1}&\pi _{2}&\pi _{3}\end{bmatrix}}={\begin{bmatrix}0,884&0,0442&0,0718\end{bmatrix}}$

Історія

Андрій Марков отримав перші результати для таких процесів суто теоретично в 1906.

Див. також

• Ланцюги Маркова з неперервним часом
• Марківський процес
• Циклічний підклас

Джерела

• Карташов М. В. Імовірність, процеси, статистика. — Київ : ВПЦ Київський університет, 2007. — 504 с.
• Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 2-я серия. — Том 15. (1906) — С. 135—156.
• Чжун Кай-лай, Однородные цепи Маркова. Перев. с англ. — М.: Мир, 1964. — 425 с.
• Нуммелин Э., Общие неприводимые цепи Маркова и неотрицательные операторы. — М.: Мир, 1989. — 207 с.
• Kemeny J. G., Snell J. L., Finite Markov chains. — The University Series in Undergraduate Mathematics. — Princeton: Van Nostrand, 1960 (Кемени Дж. Дж., Снелл Дж. Л. Конечные цепи Маркова. — М.: Наука. 1970. — 272 с.)
• S. P. Meyn and R. L. Tweedie. Markov Chains and Stochastic Stability. London: Springer-Verlag, 1993. ISBN 0-387-19832-6.