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

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


Зміст

Визначення

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

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

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

Послідовність дискретних випадкових величин   називається ланцюгом Маркова (з дискретним часом), якщо

 .

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

Матриця  , де

 

називається ма́трицею ймовірностей переходу на  -му кроці, а вектор  , де

  — початковим розподілом ланцюга Маркова.

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

 .

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

 ,

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

 

для всіх n.

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

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

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

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

 

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

 

де    — елемент i-го рядка і j-го стовпчика матриці Pk.

Доведення

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

 

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

 

Остаточно  

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

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

Відповідно, якщо    — початковий розподіл ланцюга Маркова, то   є вектором розподілу ймовірностей перебування в різних станах в час n.

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

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

Стан   називається досяжним із стану  , якщо існує   таке, що

 .

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

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

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

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

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

 

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

Якщо k = 1, тоді стан називається аперіодичним . В іншому випадку (k > 1), стан називаєься періодичним з періодом k.

В кожному класі досяжності всі стани мають однаковий період.

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

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

 

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

 

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

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

 

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

 

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

 

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

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

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

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

 

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

 

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

 

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

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

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

 

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

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

 

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

Приклад

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

 

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

 

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

 

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

 

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

 
 

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

 

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

 

З умови  ,одержується єдиний результат :

 

Історія

Андрій Марков отримав перші результати для таких процесів суто теоретично в 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.