Марковський ланцюг

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

для всіх n.

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

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

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

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

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

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

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

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

Доведення

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

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

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

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

Остаточно ${\displaystyle 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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклад

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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. .