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

Нехай ${\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 проходить лише у випадку коли імовірність переходу між відповідними станами нерівна нулю. Дана ймовірність переходу також позначається біля відповідного ребра.

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

${\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 =\pi \mathbf {P} .\,}$

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

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

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

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