Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Подальша класифікація: зворотні і незворотні стани

Читайте также:
  1. Актерский тренинг по системе Станиславского. Настрой. Состояния. Партнер. Ситуации
  2. Ареал, место обитания и экологические особенности произрастания. Сырьевая база.
  3. Березневі парламентські вибори 1998 р. та подальша діяльність Верховної Ради України
  4. Бомбардировки мирных в Станице Луганской
  5. Булавинское восстание.
  6. В какой из последовательностей единицы измерения указаны в порядке возрастания
  7. Вивчення літературних джерел та оформлення списку використаних джерел
  8. Влияние войны на экономическую и политическую ситуацию в стране. Нарастание общенационального кризиса
  9. Внутренняя и внешняя политика СССР в 1964 - 1984 гг. Нарастание кризисных явлений.
  10. ВОЗРАСТАНИЕ АГРЕССИВНОСТИ СРЕДЫ

Позначимо для n ³ 1 через fіj ( n ) ймовірність того, що, потрапивши в момент часу t у стан i, однорідний МЛ вперше після цього опиниться у стані j в момент часу t + n (інакше кажучи, через n кроків). Тобто

fіj ( n ) = Р (x (t + n) = j, x (t + n – 1) ¹ j, …, x (t + 1) ¹ j | x (t) = і)). (3.1)

3.7. Зауваження. Внаслідок однорідності процесу, не має значення, в який саме момент часу трапилося попадання в i; наприклад, можна мати на увазі початковий момент, і тоді

fіj ( n ) = Р (x (n) = j, x (n – 1) ¹ j, …, x (1) ¹ j | x (0) = і)). (3.1)¢

3.8. Зауваження. Величини fіj ( n ) є зручним визначити і при n = 0. На відміну від величини pіj (0) (див. рівність (2.9)), величина fіj (0) завжди вважається рівною 0, тобто

fіj (0) = 0 " і, j Î X. (3.2)

Між ймовірностями fіj ( n ) і pіj ( n ) має місце зв’язок:

pіj ( n ) = fіj ( k ) pjj ( n k ), і, j Î X, n ³ 1. (3.3)

Якщо послідовно покладати в (3.3) n = 0,1,…, то одержимо систему рекурентних співвідношень, що дозволяють визначити fіj ( n ) за відомими pіj ( n ) або, навпаки, визначити перехідні ймовірності pіj ( n ) за відомими ймовірностями fіj ( n ):

pіj (1) = fіj (1), pіj (2) = fіj (1) pjj (1) + fіj (2), pіj (3) = fіj (1) pjj (2) + fіj (2) pjj (1) + fіj (3), …, (3.4)

Позначимо далі fіj = fіj ( n ). (3.5)

Неважко побачити, що величина fіj дорівнює ймовірності того, що система, попавши у стан і, коли-небудь після цього опиниться у стані j. Зокрема, при і = j одержуємо величину

fіі = fіі ( n ), (3.6)

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

3.9. Означення. Стан і називається зворотним, якщо fіі = 1 (3.7)

і незворотним, якщо fіі < 1 (3.8)

З’ясування питання про зворотність чи незворотність станів МЛ часто стає важливим при дослідження конкретних систем. Наступна теорема дає певну можливість відповіді на зазначене питання.

3.10. Теорема. Для того, щоб стан і був зворотним, необхідно і достатньо, щоб виконувалась рівність pіі ( n ) = + ¥. (3.9)

З теореми 3.10 можна одержати наступний наслідок

3.11. Наслідок. Якщо i Î X є незвор. станом, то " j Î X виконується pj i ( n ) < + ¥ (3.10)

Наступна теорема характеризує поняття зворотного стану з іншої точки зору порівняно з теоремою 3.10.

3.12. Теорема. Нехай Qіі є ймовірністю події {МЛ, виходячи із стану і, повертається в нього нескінченно часто}. Тоді стан і є зворотним чи незворотним в залежності від того, Qіі = 1 або Qіі = 0.

3.13. Наслідок. Кількість повернень МЛ у довільний зворотний стан з ймовірністю 1 є нескінченною. З іншого боку, з ймовірністю 1 кількість повернень МЛ у довільний незворотний стан є скінченною, інакше кажучи, з ймовірністю 1 система типу МЛ або ніколи не приходить у такий стан, або рано чи пізно опиняється у такому стані востаннє, і більше ніколи в нього не повертається.

3.14. Наслідок. Нехай і — зворотний стан, а j — довільний стан, що є досяжним з і. Тоді fj і = 1. Інакше кажучи, якщо система опиниться в стані, що є досяжним з деякого зворотного стану, то повернення з досягнутого стану в даний зворотний стан і трапиться з ймовірністю 1.

Для зворотного стану і покладемо mі = n fіі ( n ). (3.11)

Зрозуміло, що mі є математичним сподіваннямям (середнім значенням) часу першого повернення у стан і.

3.15. Означення. Зворотний і стан зветься додатним, якщо mі < + ¥

і нульовим, якщо mі = + ¥.

Є справедливим наступне твердження: стан і є (зворотним) нульовим станом тоді і тільки тоді, коли виконується рівність (3.9) і при цьому

pіі ( n ) ® 0 при n ® ¥. (3.12)

В цьому випадку для всіх j Î X pjі ( n ) ® 0 при n ® ¥. (3.13)

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

3.16. Теорема. В незвідному ланцюгу Маркова (означення 3.2) всі стани є однотипними.

Зокрема, теорема 3.16 означає, що всі стани незвідного ланцюга або всі зворотні, або всі незворотні, причому у випадку зворотності або всі вони додатні, або всі – нульові. Також є вірним, що всі стани такого МЛ або всі неперіодичні, або всі періодичні із спільним періодом.

3.17. Вправа. Встановити, що означає теорема 3.15 для станів незвідного МЛ, що класифіковані за пп. 1. — 4. даного розділу.

3.18. Наслідок. У однорідному МЛ ніякий незворотний стан не може бути досяжним ні з якого зворотного стану.

3.19. Означення. Враховуючи теорему 3.15, клас еквівалентності станів МЛ називають зворотним, якщо він складається лише із зворотних станів. Аналогічно визначаються додатні, нульові та періодичні класи станів.

Наступне твердження уточнює наведену вище теорему 3.1 про можливість розбиття множину станів МЛ на класи еквівалентних (сполучених) станів.

3.20. Теорема. Стани марківського ланцюга можуть бути єдиним чином розбиті на множини Y, C 1, C 2,…, що не перетинаються і є такими, що

1) Y складається з усіх незворотних станів;

2) Якщо і Î Cn, то fіj = 1 для всіх j Î Сn і fіj = 0 для всіх j Ï Сn.

3.21. Означення. Клас станів C зветься замкненим, якщо кожний стан зовні C є недосяжним для кожного стану з C.

Зауважимо: з формулювання теореми 3.20 випливає, що всі Сn, n = 1,2,… є замкненими незвідними класами, які складаються тільки із зворотних станів.

3.22. Означення. Якщо клас множин C 1, C 2,…, визначених у теоремі 3.20, не є пустим, і кожна з цих множин складається з одного-єдиного поглинального стану (див. п.2 з початкової класифікації станів у розділі 3), то такий МЛ зветься поглинальним.

У випадку скінченного МЛ теорему 3.20 можна доповнити наступним твердженням.

3.23. Теорема. Скінченний МЛ не може складатися лише з незворотних станів, і жодний його стан не може бути нульовим.

3.24. Наслідок. У скінченному незвідному МЛ всі стани є зворотними і додатними.

3.25. Вправа. Акуратно вивести наслідок 3.24 з теореми 3.23. Яке ще твердження з числа наведених вище знадобиться при цьому?

 

ІІ. ПРИКЛАДИ РОЗВ’ЯЗАННЯ ЗАДАЧ

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

P =

Зобразити граф ланцюга, виділити класи еквівалентності сполучених станів, визначити зворотні або незвор. стани, а також періодичні і неперіод. стани з вказівкою періоду d (i).

Розв’язання. Очевидно, даний МЛ має 4 стани. Позначимо їх S 1, S 2, S 3 і S 4. Граф марківського ланцюга буде мати вигляд:

 

Згідно з наслідком 3.24 всі стани даного МЛ є зворотними. З наведеного графу очевидно, що, наприклад, стан S 1 є періодичним з періодом d (1) = 4. Отже і всі інші стани є періодичними з тим самим періодом (теорема 3.16).

3.27. Матриця переходів марківського ланцюга має вигляд P = .

Позначимо через 1, 2, 3 стани цього МЛ. Знайти ймовірність того, що перше попадання у стан 1 після досягнення стану 2 трапиться за два кроки.

Розв’язання. Треба знайти величину f 21(2). Скористаємося системою рівнянь (3.3), покладаючи n = 1, 2. Маємо (див. (3.4)):

pіj (1) = fіj (1), pіj (2) = fіj (1) pjj (1) + fіj (2),

що при i = 2, j = 1 з урахуванням рівності pіj (1) = pіj дає

p 21 = f 21(1), p 21(2) = f 21(1) p 11 + f 21(2),

В нашому випадку маємо p 11 = 0, тому f 21(2) = p 21(2). Для знаходження p 21(2) досить знайти матрицю P (2). Маємо P (2) = P 2 = ,

Звідки f 21(2) = p 21(2) = 1 ¤ 4.

3.28. Розглядається випадкове блукання матеріальної частинки по цілочисловій решітці дійсної прямої, таке, що з кожного стану і за один крок відбувається перехід у стан і – 1 (вліво) з ймовірністю q або в і + 1 (вправо) з ймовірністю p, причому p + q = 1. Даний процес можна уявляти як МЛ, станами якого є цілі числа і = 0, ±1, ± 2,…, сукупність яких і утворює фазовий простір X. Знайти ймовірності повернень , і Î X, m = 0, 1, 2, …

Розв’язання. Очевидно, " і Î X повернутися в і за один крок неможливо за умовою задачі. Легко бачити, що так само неможливе повернення за довільну непарну кількість кроків. Отже всі ймовірності повернень за непарну кількість кроків дорівнюють 0. Повернутися з парну кількість кроків 2 n можливо тоді і тільки тоді, якщо в точності n кроків робиться вліво, а інша половина — вправо. Оголошуючи крок вліво «успіхом», бачимо, що ймовірність такого повернення можна обчислити як ймовірність n успіхів в схемі Бернуллі b (2 n, p). В результаті маємо " n, m = 0, 1, 2, …

= .

3.29. Довести, що при p = q = 0,5 всі стани МЛ попередньої задачі є зворотними.

Розв’язання. Згідно з теоремою 3.10 треба довести, що має місце рівність (3.9). Враховуючи розв’язок попередньої задачі, бачимо, що досить довести розбіжність ряду

. (3.14)

при p = q = 1 ¤ 2. Скористаємося відомою формулою Стірлінга, яка дає асимптотичне зображення виразу n! при n ® ¥: n! ~ , n ® ¥, де запис типу αn ~ βn, n ® ¥ означає, що відношення αn / βn прямує до 1 при n ® ¥. Підставляючи праву частину формули Стірлінга в останній ряд (3.14) і виконуючи належні спрощення, одержуємо, що вказаний ряд збігається тоді і тільки тоді, коли збігається ряд . (3.15)

При p = q = 0,5 загальний член останнього ряду є n - 0,5, тобто ряд (3.15) є розбіжним.

3.30. Матриця переходів МЛ має вигляд: P =

Зобразити граф ланцюга і виділити класи еквівалентності сполучених станів, виділити зворотні (незворотні) стани та дослідити їх на періодичність. Дати опис класу Y і класів C 1,… з теореми 3.20 для даного МЛ.

Розв’язання. Граф марківського ланцюга буде мати вигляд:

 
 

 

 


Розглядаючи стан S 5, бачимо, що з цього стану можна попасти у стан S6 і тоді стан S 1 вже ніколи не буде досягнутим. При цьому стан S 5 є досяжним з стану 1. Отже, стан 1 не є зворотним (наслідок 3.14). Тому всі стани S 1, S 2, S 3, S 4, S 5 є незворотними. Вони утворюють множину Y з теореми 3.20. Єдиним зворотним класом C 1 даного МЛ є множина, що складається з єдиного зворотного стану S 6. Очевидно, d (6) = 1. Звертаючись до класу Y, бачимо, що повернення у стан S 1 можливо за 3 кроки (S1 ® S3 ® S5 ® S1), за 4 кроки (S1 ® S3 ® S4 ® S5 ® S1; інші варіанти для повернення за 4 кроки знайдіть самостійно) або за 5 кроків (S1 ® S 2 ® S3 ® S4 ® S5 ® S1). Тому d (1) = 1. Обидва класи T і C 1 є неперіодичними.

 

ІІІ. ЗАДАЧІ ТА ВПРАВИ ДЛЯ САМОСТІЙНОГО РОЗВ’ЯЗАННЯ

3.31. Розглянути задачу 2.7 попереднього розділу. Виконати класифікацію станів МЛ цієї задачі згідно з п.п. 1. — 4. даного розділу. Виділити класи еквівалентних станів. Визначити зворотні і незворотні стани, дослідити даний МЛ на періодичність. Виконати розбиття фазового простору згідно з теоремою 3.20.

 

3.32. Виконати розбиття фазового простору згідно з теоремою 3.20 для випадкового блукання з поглинаючими екранами (задача 2.13 попереднього розділу).

3.33. МЛ з двома станами i, j має наступну перехідну матрицю:

Побудуємо новий МЛ, вважаючи станами нового ланцюга пари станів вихідного МЛ: (i, i), (i, j), (j, i), (j, j). Новий МЛ на n -му кроці знаходиться у стані (x, y), якщо старий МЛ знаходився в стані x на n -му кроці і перейшов у стан y на (n + 1)-му кроці (x та y приймають значення i або j). Скласти перехідну матрицю нового МЛ. Зробити класифікацію станів.

 

3.34. Вказати класи еквівалентності станів МЛ, перехідні матриці яких наведені нижче. Виконати розбиття фазових просторів даних МЛ в термінах теореми 3.20. Дослідити на періодичність. Які з цих МЛ є поглинальними?

a) P = ; b) P = ; c) P = ;

d) P = ; e) P = .

3.35. Дати повну класифікацію станів МЛ з наступною перехідною матрицею

P = .

3.36. Матриця переходу МЛ має вигляд P = .

Знайти ймовірність того, що перше досягнення стану s 3 після досягнення стану s 1 трапиться за 2 кроки.

 

3.37. Довести, що всі стани процесу з задачі 3.28 є незворотними при p ¹ q.

 

3.38. Матриця переходів МЛ має вигляд P = .

Виконати розбиття станів даного МЛ згідно з теоремою 3.20.




Дата добавления: 2014-12-20; просмотров: 38 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.017 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав