Марковские цепи

Сентябрь 13, 2022

Главная
Математика
Марковские цепи

Содержание

2. Однородные ЦМ: Цепи Маркова Определение и способы задания ЦМ 1) t = 0, 1, 2, …
3. Цепи Маркова Пример 1 (задача о погоде) Всем хороша Земля Оз, но только не своей погодой.
4. Многошаговый переход в ЦМ Какова вероятность за m шагов перейти из состояния в состояние ? Гипотеза
5. Многошаговый переход в ЦМ Теорема Уравнение Колмогорова-Чепмена Следствие
6. Классификация состояний ЦМ Состояние достижимо из состояния Если состояния взаимодостижимы, то они принадлежат одной сильной компоненте
7. Классификация состояний ЦМ Состояние поглощающее, если Множество состояний D эргодическое, если оно замкнуто, но никакое его
8. Если конденсация орграфа ЦМ слабосвязна, то независимо от начального состояния вероятность перейти за t шагов в
9. Переход в эргодическое состояние Теорема (о переходе в эргодическое состояние) 1) Пусть число шагов t 2)
10. Поглощающие цепи Маркова Определение. ЦМ – поглощающая, если имеет хотя бы одно поглощающее состояние и для
11. Поглощающие цепи Маркова Канонический вид матрицы перехода поглощающие состояния ЦМ: Матрица перехода ЦМ непоглощающие состояния
12. Поглощающие цепи Маркова Пример 3 Некий игрок, имея не более трех тугриков, начинает игру в наперстки
13. Поглощающие цепи Маркова Теорема 1. Для поглощающей ЦМ с матрицей Р справедливо б) существует матрица, обратная
14. Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в состоянии . Тогда элемент фундаментальной
15. Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в состоянии . Тогда элемент фундаментальной
16. Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в состоянии . Тогда элемент фундаментальной
17. Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в состоянии . Тогда элемент фундаментальной
18. Поглощающие цепи Маркова Пример 3 (игра в «наперстки»)
19. Поглощающие цепи Маркова Теорема 3. В поглощающей ЦМ с матрицей перехода (*) вероятность перехода в заданное
20. Поглощающие цепи Маркова Теорема 3. В поглощающей ЦМ с матрицей перехода (*) вероятность перехода в заданное
21. Поглощающие цепи Маркова Пример 3 (игра в «наперстки»)
22. Эргодические цепи Маркова Эргодическая ЦМ: нет поглощающих состояний и из любого состояния можно попасть в любое
23. Эргодические цепи Маркова Теорема Если ЦМ с матрицей перехода Р регулярна, то , где все строки
24. Эргодические цепи Маркова Пример 1 (задача о погоде)
26. Скачать презентацию

Слайд 2

Однородные ЦМ:
Цепи Маркова
Определение и способы задания ЦМ

1)

t = 0, 1, 2, …

Матрица перехода ЦМ

Слайд 3

Цепи Маркова

Пример 1 (задача о погоде) Всем

хороша Земля Оз, но только не своей погодой. Здесь никогда не бывает двух ясных дней подряд. Если сегодня ясно, то завтра с одинаковой вероятностью пойдет дождь или снег. Если сегодня дождь или снег, то с вероятностью 0,5 погода не изменится. Если все же она изменится, то в половине случаев снег заменится дождем или наоборот, и лишь в половине случаев на следующий день будет ясная погода.

Орграф ЦМ

Слайд 4

Многошаговый переход в ЦМ

Какова вероятность за m

шагов перейти из состояния в состояние ?

Гипотеза Нk: через s шагов (s

- уравнение Колмогорова-Чепмена

Слайд 5

Многошаговый переход в ЦМ

Теорема
Уравнение Колмогорова-Чепмена
Следствие

Слайд 6

Классификация состояний ЦМ

Состояние достижимо из состояния
Если состояния

взаимодостижимы, то они принадлежат одной сильной компоненте орграфа.

Множество состояний С замкнуто, если

Слайд 7

Классификация состояний ЦМ

Состояние поглощающее, если
Множество состояний D

эргодическое, если оно замкнуто, но никакое его собственное подмножество не является замкнутым.

Состояние транзитное, если

В примере 2:

- поглощающее, , , - транзитные,

Множество - замкнутое, эргодическое

Слайд 8

Если конденсация орграфа ЦМ слабосвязна, то независимо от начального состояния вероятность

перейти за t шагов в эргодическое состояние стремится к 1 при

Переход в эргодическое состояние

Теорема (о переходе в эргодическое состояние)

В конденсации орграфа эргодическому множеству соответствует сильная компонента без исходящих дуг

Слайд 9

Переход в эргодическое состояние

Теорема (о переходе в

эргодическое состояние)

1) Пусть число шагов t

2) Вторая серия из числа шагов t

… …
k) k серия из числа шагов t

Изучение ЦМ: I этап: до перехода в эргодическое множество; II этап: поведение внутри эргодического множества

Слайд 10

Поглощающие цепи Маркова
Определение. ЦМ – поглощающая, если имеет хотя бы одно

поглощающее состояние и для любого непоглощающего состояния

Пример 3

Некий игрок, имея не более трех тугриков, начинает игру в наперстки (при угадывании получает тугрик, при ошибке – отдает). Заранее он решает, что прекращает игру, как только его капитал составит три тугрика.

Слайд 11

Поглощающие цепи Маркова

Канонический вид матрицы перехода
поглощающие состояния

ЦМ:

Матрица перехода ЦМ

непоглощающие состояния

Слайд 12

Поглощающие цепи Маркова

Пример 3
Некий игрок, имея не

более трех тугриков, начинает игру в наперстки (при угадывании он получает тугрик, при ошибке – отдает). Заранее он решает, что прекращает игру, как только его капитал составит 3 тугрика.

Матрица перехода

Канонический вид

Слайд 13

Поглощающие цепи Маркова
Теорема 1. Для поглощающей ЦМ с матрицей Р справедливо

б) существует матрица, обратная к матрице Е-Q, и ее можно найти по формуле

Теорема о переходе в эргодическое состояние

- фундаментальная матрица ЦМ

Слайд 14

Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в

состоянии . Тогда элемент фундаментальной матрицы N равен среднему времени нахождения ЦМ в непоглощающем состоянии до момента поглощения.

Поглощающие цепи Маркова

Рассмотрим СВ

Слайд 15

Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в

Поглощающие цепи Маркова

Рассмотрим СВ

Слайд 16

Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в

Поглощающие цепи Маркова

т.к.

Слайд 17

Теорема 2. Пусть в начальный момент времени поглощающая ЦМ находилась в

Поглощающие цепи Маркова

Следствие. Пусть в начальный момент времени поглощающая ЦМ находилась в состоянии . Среднее число шагов до поглощения равно сумме элементов i-ой строки матрицы N.

Слайд 18