Однородные цепи Маркова

Пусть в каждый момент времени система может находиться только в одном состоянии 5,, 5₂, 5₃,..., 5_т. С течением времени система пере­ходит из одного состояния в другое, причем переход совершается ров­но за единицу времени. Номер состояния системы в момент времени I = п - дискретная случайная величина, которая обозначается А „. По­следовательность случайных величин Л',, А'₂, А'₃,..., Л^,,... полностью

характеризует эволюцию системы.

Цепью Маркова называется последовательность А',, А'₂, А^Г₃,...,

Л',,,..., удовлетворяющая условию

для любых /, ^, п, -х₍₎, а,, х₂,..., х„_₂ • Вероятности

называются вероятностями перехода системы из состояния 5, - в состо­яние 5, - за один шаг в момент времени I = п- 1. Если матрица р_}) не за­висит от времени, то цепь Маркова называется однородной.

Свойства матрицы вероятностей перехода за один шаг Р = р₉ одно-

родной цепи Маркова:

1- А^О;

2. сумма элементов в каждой строке равна 1.

Матрица вероятностей перехода системы из состояния 5, в состоя­ние 5, за А- шагов обозначается ДА). Для однородных цепей Марко­ва выполняются равенства

- 2)

=._г= Р" " 0) =

Таким образом, можно найти вероятности перехода между состоя­ниями за любое число шагов, зная матрицу вероятностей перехода за один шаг:

Вектор-строка г, - = Р{Х₁₎ - 1}, / = 1, 2,.... т называется вектором на­чальных вероятностей. Распределение цепи Маркова по состояниям через а- шагов после начала процесса вычисляется по формуле

или в матричной форме р(А) = с- ДА) = с- /** ".

Если для некоторого А все элементы.матрицы /*(А) положительны, то существует предельное распределение цепи Маркова по состояни­ям, не зависящее от вектора начального распределения. Предельные вероятности и. = 11т /7: (А:) можно найти как единственное решение

/; ~> -х •

системы уравнений

12.1. Студент техникума с трехлетним сроком обучения может нахо­
диться в одном из следующих состояний: 5", - первокурсник, 5, - вто­
рокурсник, 5₃ - выпускник, 5₄ - окончил, 5₅ - отчислен. Вероятность
отчисления с первого курса 0, 05, со второго курса - 0, 01, с третьего
курса не отчисляют. Вероятность для отчисленного студента восстано­
виться на первый курс равна 0, 2, а на второй курс - 0, 1 (считаем, что
эти вероятности не зависят от того, с какого курса был отчислен сту­
дент). Построить граф состояний системы и найти матрицу вероятнос­
тей перехода цепи Маркова. Для каждого состояния проверить, явля­
ется ли оно поглощающим, существенным, несущественным, невоз­
вратным. Найти для первокурсника вероятность окончания техникума
через три года и через пять лет.

12.2. Матрица вероятностей перехода за один шаг цепи Маркова
имеет вид

1/3 1/3 1/3 О

1/2 0 1/4 1/4

О 1/2 0 1/2

1 о о о

Цепь Маркова, для которой существуют пределы и_>: , называется

эргодической.

При небольшом числе состояний системы для описания эволюции цепи Маркова удобно использовать представление системы в виде гра­фа. Вершины графа - это состояния системы, а ребра - возможные пе­реходы между состояниями. Около каждого ребра числами указывает­ся вероятность соответствующего перехода.

Состояние Зу называется достижимым из 5", -, если система за конеч­ное число шагов может перейти из 5", - в 5,. Состояния 5_; , из которых можно лишь вернуться обратно в 5_; , называются поглощающими. Для поглощающих состояний р^ -1. Состояние 5у называется сущест­венным, если оно достижимо из любого состояния, достижимого из 5_; . Состояние 5, называется несущественным, если оно недостижимо

хотя бы из одного состояния, достижимого из 5.-. Состояния, из кото­рых система может выйти, но в которые не может вернуться, называ­ются невозвратными.

Построить граф, соответствующий этой матрице, и выяснить свойства всех состояний системы.

12.3. Вероятности перехода за один шаг для цепи Маркова задаются матрицей

'1/2 1/20 О^л

О 1/2 1/2 О

О 0 1/2 1/2

1/2 О О 1/2

Построить граф, соответствующий этой матрице, и выяснить свойства всех состояний системы.

12.4. Матрица вероятностей перехода за один шаг цепи Маркова имеет вид

О 1 (Г О О 1

1 о а

Найти матрицы вероятностей перехода за 2, 3, 4,..., А шагов.

! 2.5. Доказать, что любая цепь Маркова с конечным числом со­стоянии имеет по крайней мере одно возвратное состояние.

12.6. Доказать, что если цепь Маркова имеет т состояний и у-е со­
стояние достижимо из / -го, то оно может быть достигнуто менее чем
за т шагов.

12.7. Доказать, что если цепь Маркова имеет ш состояний и вероят­
ность возвращения в / -е состояние положительна, то это возвращение
может произойти за т или менее шагов.

12.8. Существует ли цепь Маркова, для которой матрица вероятно­
стей перехода за два шага равна

1/2!

(1/2 1/20} (} 0 0^х е)| О 1/2 1/2. ж)! 1/2 0 1/2 1/2 0 1/2; и/3 1/3 1/3,

Найти предельные распределения вероятностен там, где они существу­ют.

1о, з

о,?

! 2.9. Определяется ли цепь Маркова начальным распределением и матрицей вероятностей перехода за два шага?

12.10. Определяется ли цепь Маркова начальным распределением и матрицей вероятностей перехода за три шага?

12.1 1. Матрица вероятностей перехода за один шаг цепи Маркова имеет вид

Р =

О 1/2 1/2 1/4 0 3/4 2/3 1/3 0.

Найти стационарное распределение цепи Маркова, т.е. распределе­ние, которое не меняется со временем.

12.12. Доказать, что для конечной цепи Маркова всегда существует
стационарное распределение.

12.13. Матрица вероятностен перехода за один шаг цепи Маркова
имеет вид

'0, 3 0, 5 0, 2" Р = 0, 4 О 0, 6, 0, 8 ОД 0