Марківський випадковий процес і ланцюги Маркова

Марківський процес − це випадковий процес, що базується на принципі Маркова. Згідно з цим принципом ймовірність значень випадкової величини у наступні моменти не залежать від того, які значення вона приймала у попередні моменти часу.

Нехай система знаходиться в одному із станів У певні фіксовані моменти часу система під впливом випадкових факторів може переходити із одного стану в інший, при цьому у будь-який момент часу ймовірність для системи з’явитись у наперед заданому стані цілком визначається тим станом, у якому вони знаходились безпосередньо перед стрибком і не залежить від усіх попередніх станів, у яких система знаходилась до моменту часу . Поведінка цієї системи описується простим ланцюгомМаркова. Отже, ланцюг Маркова є випадковим процесом з дискретним часом.

Імовірність переходу із стану (у момент ) до стану у момент зветься перехідною ймовірністю цього ланцюга і позначається таким чином:

,

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

за умовою, що та при будь-якому фіксованому , тобто сума елементів кожного рядка дорівнює одиниці. Загальний елемент цієї матриці має два індекси: перший визначає номер стану в даний момент, а другий – номер майбутнього стану , в який перейде система. Якщо , то це означає, що випадкова подія, яка полягає у безпосередньому переході системи із -го стану у -ий неможлива. Випадок відповідає твердженню, що із -го стану система після наступного випробування завжди переходить в -ий стан.

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

.

Кожне значення ймовірності задовольняє рівнянню Маркова:

; (9.4)

де може приймати будь-яке ціле значення на відрізку .

Безумовна ймовірність називається абсолютною ймовірністю системі з’явитись у момент у стані . Тоді . Так, при маємо:

для ;

для ;

………………………………………………………………………….

для m .

Приклад. Певна сукупність робочих сімей поділена на три групи: а) ті, що не мають комп’ютер та не намагаються його купити; б) те ж ті, що не мають комп’ютер, але збираються його придбати; в) ті, що мають комп’ютер. Статистичні обстеження дали можливість оцінити ймовірності переходу сім’ї із однієї групи в іншу на протязі року. Припустимо, що матриця перехідних ймовірностей має вигляд:

.

Обчислити ймовірність того, що а) сім’я, яка не має комп’ютера і не збирається його придбати, буде знаходитися в тієї ж ситуації через 2 роки; б) що сім’я, яка не має комп’ютер та має намір його придбати, буде мати комп’ютер через 2 роки.

Розв’язання. Аналіз деяких даних цієї матриці дає можливість навести такі тлумачення:

1) якщо сім’ї у попередньому році вже мали комп’ютер, то і у наступному за ним році вірогідно будуть його мати, тобто ;

2) сім’ї, в яких не було комп’ютеру в попередньому році, але які збирались його придбати, матимуть змогу здійснити свій намір у наступному році з ймовірністю;

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

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

Для обчислення шуканих ймовірностей і слід знайти матрицю:

.

Таким чином, ймовірність, що сім’я, яка не має комп’ютер і не збирається його придбати, буде знаходитися в тієї ж ситуації через 2 роки дорівнює 0,49, а ймовірність того, що сім’я, що не має комп’ютер та має намір його придбати, буде мати комп’ютер через 2 роки дорівнює 0,51.

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

; .

Фінальні ймовірності є розв’язком системи лінійних рівнянь

, (9.5)

Ланцюг Маркова, для якого існують границі називається ергодичним, або регулярним. Якщо ці фінальні ймовірності строго додатні, то ланцюг називається додатно - регулярним. У випадку, коли – неістотний стан, то (незалежно від ).

Нехай – одинична матриця порядку, який дорівнює порядку матриці (розглядаються ланцюги із скінченним числом станів), а – параметр. Тоді матриця

називається характеристичною матрицею даного ланцюга. Її визначник позначається через . Усі корні рівняння є характеристичними числами матриці, одне з яких завжди дорівнює , а інші по модулю не перевищують .

Якщо ланцюг Маркова є ергодичним, то всі інші характеристичні числа по модулю строго менше одиниці та головні мінори матриці будуть строго додатними при , тобто .

Приклад. Ланцюг Маркова керується матрицею переходу:

.

Перевірити, чи є цей ланцюг ергодичним.

Розв’язання. Знаходимо характеристичні числа матриці із рівняння . Підставимо дані задачі у це рівняння

.

Обидва розв’язки рівняння по модулю дорівнюють одиниці . Це не задовольняє умові ергодичності, оскільки за умовою ергодичності необхідно, щоб: . В нашому прикладі не виконується друга умова. Отже, цей ланцюг не ергодичний.

Фінальні ймовірності обчислюються за формулами

. (9.6)

Головним мінором є мінор, що відповідає елементу матриці .

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

, де , .

Скласти характеристичне рівняння і знайти характеристичні числа матриці та знайти фінальні ймовірності і .

Розв’язання. Складемо характеристичне рівняння за заданою матрицею переходу. Маємо:

.

Зробимо перетворення, за яким елементи першого та другого стовпчиків складаємо і записуємо замість першого, а другий стовпчик залишається без змін. Отже, маємо:

Звідси одержимо:

Отже, характеристичними числами є і .

Згідно з умовою задачі усі елементи матриці є додатними: , , та . Отже, ланцюг Маркова є додатно-регулярний.

Для знаходження фінальних (граничних) ймовірностей треба знайти головні мінори визначника :

; .

Обчислимо їх при : , .

Таким чином одержуємо:

, .

Стан системи називається неістотним, якщо існує стан та ціле число , такі, що із стану можливий перехід в стан через кроків, але не можливе повернення (поворот) із у ні за яку кількість кроків:

, , .

Усі інші стани називаються істотними.

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

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

,

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

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

.

Розв’язання. Побудуємо імовірнісний граф (рис. 9.1).

Рис. 9.1. Граф перехідної імовірнісної матриці

Аналіз побудованого графу свідчить про розклад системи станів на два класи: , що складається з трьох істотних станів , та , що складається з двох станів . Ці класи незалежні між собою та ізольовані. Згідно з цим аналізом робимо перетворення матриці Р, а саме, переставляємо одночасно між собою стовпці 3-й і 5-й, а також рядки 3-й та 5-й, як наслідок, отримуємо блочно-діагональну матрицю . Отже, матриця цілком розкладна.

.

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

Дата добавления: 2014-01-11