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

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

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

Визначення

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

Нехай 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^{(k)}_{i,j}=\mathbb{P}\left(X_{n+k}=j\mid X_n=i\right),$

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

$(P^k)_{(i,j)}=\left(p^{(k)}_{i,j}\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{align}\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^{k-1}_{i,\ell}\ p_{\ell,j} \\ &= \mathbb{P}\left(X_n=i\right)\ P^{k}_{i,j}, \end{align}:$

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

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

• першої і другої рівності використана формула повної ймовірності,
• третьої рівності використана властивість Маркова,
• четвертої рівності використано припущення індукції для $\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\ge1: 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.$

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

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

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

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

$\pi_j = \sum_{i \in S} \pi_i p_{ij}.$

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

$\pi_j = \frac{1}{M_j}.\,$

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

$\pi_j =\lim_{n \rarr \infty} p_{ij}^{(n)} = \frac{1}{M_j}.$

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

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

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

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

Тобто π є власним вектором матриці ймовірностей переходу, що відповідає власному значенню 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{align} \\ \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{align}$

З умови $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}$

Див. також

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

Література

• Марков А. А., Распространение закона больших чисел на величины, зависящие друг от друга. — Известия физико-математического общества при Казанском университете. — 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.