Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

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




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

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

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

,

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

 

 

 

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

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

 

.

 

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

 

; (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; Просмотров: 1410; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.158.250.39
Генерация страницы за: 0.105 сек.