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

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

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


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

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

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

Приклад[ред.ред. код]

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

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

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

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

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

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

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

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

Застосування Ланцюгів Маркова (en:Markov chain)[ред.ред. код]

Генетика[ред.ред. код]

Марковські

ланцюги були використані в генетиці населення для того, щоб описати зміни частот генів в малих популяціях, постраждалих від генетичного дрейфу , наприклад, в рівнянні дифузії методом, описаним Марнотратові Кімура . [ 28 ]

Математична біологія[ред.ред. код]

Ланцюги Маркова  мають багато додатків в біологічнному

моделюванні, зокрема процеси населення , які корисні в процесах моделювання, які (принаймні) аналогічно біологічних популяцій. Леслі-матриця є одним з таких прикладів, хоча деякі з його елементів не ймовірнісні (вони можуть бути більше, ніж 1). Іншим прикладом є моделювання форми клітин в розділових листів епітеліальних клітин . [ 26 ] Ще одним прикладом є стан іонних каналів в клітинних мембранах.

Ланцюги Маркова також використовуються при моделюванні функції мозку, такі як моделювання неокортексу ссавців. [ 27 ]

Статистика[ред.ред. код]

Методи

марківського ланцюга також стають дуже важливими для формування послідовності випадкових чисел, щоб точно відображати дуже складні імовірнісні розподіли, за допомогою процесу, званого ланцюгом Маркова Монте-Карло (MCMC). В останні роки це зробила революцію в доцільності виведення байесовских методів, що дозволяють широкий спектр розподілів задніх моделюватися і їх параметри знайдені чисельно.

Інформатика[ред.ред. код]

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

використовуються у всьому обробки інформації. Клод Шеннон створив поле теорії інформації , що відкривається з впровадження концепції ентропії через моделювання Маркова англійською мовою. Такі ідеалізовані моделі можуть захопити багато з статистичних закономірностей систем. Навіть без опису повну структуру системи ідеально, такі моделі сигналів може зробити можливим дуже ефективне стиснення даних за допомогою ентропійного кодування методів, таких як арифметичне кодування . Вони також дозволяють ефективно оцінити стан і розпізнавання . Ланцюги Маркова також відіграють важливу роль у навчанні з підкріпленням .

Ланцюги Маркова також основою для прихованих моделей Маркова , які є важливим інструментом у таких областях, як телефонних мереж (які використовують алгоритм Вітербо корекції помилок), розпізнавання мови і біоінформатики .

LZMA алгоритм стиснення даних без втрат поєднує в собі ланцюгів Маркова із стисненням Лемпеля-Зів, щоб досягти дуже високих ступенів стиснення.


Статистика Це незавершена стаття зі статистики.
Ви можете допомогти проекту, виправивши або дописавши її.

Див. також[ред.ред. код]

Література[ред.ред. код]

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