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

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

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

Визначення

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

Нехай $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⩾0}$ називається ланцюгом Маркова (з дискретним часом), якщо

$\mathbb{P}(X_{n+1}=i_{n+1}\mid X_n=i_n,X_{n-1}=i_{n-1},\dots ,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$-му кроці, а вектор $𝐩=(p_1,p_2,\dots {)}^{\mathrm{\top }}$, де

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

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

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

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

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

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

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

для всіх n.

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

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

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

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

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

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

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

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

Доведення

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

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

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

$\begin{array}{cc}\mathbb{P}(X_n=i\wedge X_{n+k}=j)& =\sum _{\ell \in E}\mathbb{P}(X_n=i,X_{n+k-1}=\ell \wedge X_{n+k}=j)\\ & =\sum _{\ell \in E}\mathbb{P}(X_n=i,X_{n+k-1}=\ell )\mathbb{P}(X_{n+k}=j\mid X_n=i,X_{n+k-1}=\ell )\\ & =\sum _{\ell \in E}\mathbb{P}(X_n=i,X_{n+k-1}=\ell )p_{\ell ,j}\\ & =\mathbb{P}(X_n=i)\sum _{\ell \in E}{P}_{i,\ell }^{k-1}{p}_{\ell ,j}\\ & =\mathbb{P}(X_n=i)P_{i,j}^k,\end{array}:$

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

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

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

Відповідно, якщо $𝐩=(p_1,p_2,\dots {)}^{\mathrm{\top }}$  — початковий розподіл ланцюга Маркова, то $((P^T{)}^n𝐩)$ є вектором розподілу ймовірностей перебування в різних станах в час n.

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

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

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

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

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

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

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

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

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

$k=\gcd \{n:\mathrm{Pr}(X_n=i|X_0=i)>0\}$

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

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

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

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

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

$T_i=\inf \{n\ge 1:X_n=i|X_0=i\}.$

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

$\mathrm{Pr}(T_i=\mathrm{\infty })>0.$

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

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

$M_i=E[T_i].$

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

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

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

$p_{ii}=1,p_{ij}=0i=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=\underset{n\to \mathrm{\infty }}{\lim }{p}_{ij}^{(n)}=\frac{1}{M_j}.$

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

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

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

$\pi =\pi 𝐏.$

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

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

$\underset{k\to \mathrm{\infty }}{\lim }{𝐏}^k=\mathrm{𝟏}\pi$

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

Приклад

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

$P=\left[\begin{array}{ccc}0,9& 0,05& 0,05\\ 0,7& 0& 0,3\\ 0,8& 0& 0,2\end{array}\right]$

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

${𝐩}^{(0)}=\left[\begin{array}{ccc}1& 0& 0\end{array}\right]$

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

${𝐩}^{(1)}={𝐩}^{(0)}P=\left[\begin{array}{ccc}1& 0& 0\end{array}\right]\left[\begin{array}{ccc}0,9& 0,05& 0,05\\ 0,7& 0& 0,3\\ 0,8& 0& 0,2\end{array}\right]=\left[\begin{array}{ccc}0,9& 0,05& 0,05\end{array}\right]$

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

${𝐩}^{(2)}={𝐩}^{(1)}P={𝐩}^{(0)}{P}^2=\left[\begin{array}{ccc}1& 0& 0\end{array}\right]{\left[\begin{array}{ccc}0,9& 0,05& 0,05\\ 0,7& 0& 0,3\\ 0,8& 0& 0,2\end{array}\right]}^2=\left[\begin{array}{ccc}0,885& 0,045& 0,07\end{array}\right]$

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

${𝐩}^{(n)}={𝐩}^{(n-1)}P$

${𝐩}^{(n)}={𝐩}^{(0)}{P}^n$

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

$\mathit{\pi }=\underset{n\to \mathrm{\infty }}{\lim }{𝐩}^{(n)}$

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

$\begin{array}{c}\\ \mathit{\pi }P& =\mathit{\pi }\text{(}\mathit{\pi }\text{ est la loi invariante par rapport a }P\text{.)}\\ & =\mathit{\pi }I\\ \mathit{\pi }(I-P)& =\mathrm{𝟎}\\ & =\mathit{\pi }(\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]-\left[\begin{array}{ccc}0,9& 0,05& 0,05\\ 0,7& 0& 0,3\\ 0,8& 0& 0,2\end{array}\right])\\ & =\mathit{\pi }\left[\begin{array}{ccc}0,1& -0,05& -0,05\\ -0,7& 1& -0,3\\ -0,8& 0& 0,8\end{array}\right]\\ & =\left[\begin{array}{ccc}{\pi }_1& {\pi }_2& {\pi }_3\end{array}\right]\left[\begin{array}{ccc}0,1& -0,05& -0,05\\ -0,7& 1& -0,3\\ -0,8& 0& 0,8\end{array}\right]\\ & =\left[\begin{array}{ccc}0& 0& 0\end{array}\right]\end{array}$

З умови ${\pi }_1+{\pi }_2+{\pi }_3=1$,одержується єдиний результат :

$\left[\begin{array}{ccc}{\pi }_1& {\pi }_2& {\pi }_3\end{array}\right]=\left[\begin{array}{ccc}0,884& 0,0442& 0,0718\end{array}\right]$

Історія

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

Див. також

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

Джерела

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