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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Матриця ймовірностей переходу і граф переходів однорідного ланцюга Маркова з п'ятьма станами

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


Визначення[ред.ред. код]

Інтуїтивне визначення[ред.ред. код]

Нехай I  -деяка скінченна чи зліченна множина елементи якої називаються станами. Нехай деякий процес в момент часу n (де n=0,1,2,3…) може перебувати в одному із цих станів, а в час n+1 перейти в деякий інший стан(чи залишитися в тому ж). Кожен такий перехід називається кроком. Кожен крок не є точно визначеним. З певними ймовірностями процес може перейти в один з кількох чи навіть усіх станів. Якщо імовірності переходу залежать лише від часу n і стану в якому перебуває процес в цей час і не залежать від станів в яких процес перебував у моменти 0, 1, … , n-1 то такий процес називається (дискретним) ланцюгом Маркова. Ланцюг Маркова повністю задається визначенням ймовірностей pi перебування процесу в стані 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-го стовпчика матриці Pk.

Доведення[ред.ред. код]

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

\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. Більш формально нехай випадкова змінна Ti є часом першого повернення в стан 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 називається позитивно рекурентним, якщо Mi є скінченне; в іншому випадку 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 \rarr \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{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.