<< Предыдущая

стр. 9
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

7T,(2/1) • • • m(N/l) \ I 7T m (l/l) 7Tm(2/l)
JT,(2/2) • • • TrHiV/2) 7r m (l/2) 7r m (2/2)


ym(l/N)m(2/N) • • • *i{N/N)J \nm(l/N)7rm(2/N) • • • itm(N/N)J
ЭТОТ процесс может быть начат с первого шага с помощью мат-
рицы переходных вероятностей
7T(2/1)
тг(ЛГ/2)
тг(1/2) TT(2/2)
п= (5.35)

7r(l/iV) тг(2/ЛГ) • • 7r(iV/iV)

Заметим, что матрица П - стохастическая матрица с суммой веро-
ятностей строк равной 1.
Многократно применяя такое матричное преобразование к исход-
ному распределению состояний ро, мы можем получить распределе-
ние вероятностей рп в любой момент времени п

рп = р0П". (5.36)
5.3. Конечные цепи Маркова

Теорема 5.3.1. Гомогенная цепь Маркова полностью характеризу-
ется матрицей переходных вероятностей и исходным распределе-
нием состояний. -
Приведенные выше рассуждения можно наглядно обобщить при
помощи графа состояний (рис. 5.3). Здесь узлы соответствуют состо-
яниям, а пути между ними переходам между состояниями. Каждо-
му пути приписан вес, равный переходной вероятности. Таким обра-
зом, граф состояний дает полную информацию о матрице переход-
ных вероятностей.

Переходная
вероятность




Р и с . 5.3. Граф состояний гомогенной цепи Маркова.

Пример: Случайные блуждания студента (продолжение).
Случайные блуждания (см. рис. 5.2) представлены на рис. 5.4 в
виде графа состояний.




Рис. 5.4. Граф состояний для случайных блужданий сту-
дента.

Графу состояний соответствует матрица переходных вероятно-
стей
0 1 0 0
1/2 0
1/2 0
(5.37)
П=
1/2 0 1/2
0
0
0 0
1—1




Из рис. 5.2 следует, что исходное распределение состояний
(5.38)
Ро = (О, 0, 0, 1).
Глава 5. Стационарные дискретные источники с памятью

Вероятность того, что в результате случайных блужданий студент
на 7-ом временном шаге окажется у дверей общежития, определя-
ется нервой компонентой вектора состояний на 7 шаге Pj. Из (5.36)
следует
7
Р7=РоП (5.39),
Расчеты с помощью компьютера дают

О 0,619 0 0,3281 \

( 0,3359 0 0,6641 0 ,_...
(5Ж))
0 0,6641 0 0,3359 Г
0,3281 0 0,6719 0 /
Отсюда

р 7 = (0, 0, 0, 1 ) - П 7 = (0,3281, 0, 0,6719, 0) (5.41)

и искомая вероятность равна

р7(1) =0,3281. (5.42)
Важнейшим частным случаем марковской цепи является случай,
когда распределение состояний не зависит от времени наблюдения.
Определение 5.3.3. Гомогенная цепь Маркова стационарна , ес-
ли распределение состояний постоянно во времени. В этом случае
начальное распределение является собственным, вектором матрицы
переходных вероятностей , т.е
РоП = р 0 . (5.43)
Замечание. Если вектор распределения состояний является сто-
хастическим вектором с суммой компонентов, равной 1, то сумма
компонент собственного вектора также равна 1.
Для того, чтобы цепь Маркова была стационарной, должно вы-
полняться (5.43). Пусть ро = (pi, P2, Рз, РА), тогда

0100

( 1/2 0 1/2 0
0 1/2 0 1/2
0 0 10
= (Рг/2, P i + Р з А р 2 / 2 + р 4 , рз/2),

Pi + Р2 + Рз + Р4 = 1 • (5.45)
5.3. Конечные цепи Маркова

Используя условия (5.43) и (5.45), находим стационарное распреде-
ление состояний
Ро = (1/6, 1/3, 1/3, 1/6). (5.46)
Из рекурсивного соотношения (5.36) возникают следующие важней-
шие вопросы: Что происходит но «истечении долгого времени», т.е.
при п — со? Устанавливается ли стационарное распределение со-
>
стояний? Имеется ли нечто подобное стационарному распределению,
например, два устойчивых распределения состояний?

Определение 5.3.4. Гомогенная цепь Маркова называется регуляр-
ной, если:
• Предельная матрица
П т о = lim П п (5.47)
п—*ос
существует, причем, все N строк предельной матрицы пред-
ставляют собой предельное распределение Роо;
• Предельное распределение является единственным стационар-
ным распределением вероятностей состояний любой регулярной
цепи Маркова;
• Цепь Маркова всегда регулярна, если существует некоторое на-
туральное п, при котором все компоненты некоторого столбца
матрицы П п отличны от нуля.

Последнее из утверждений определения 5.3.4 равносильно следу-
ющему: цепь Маркова является регулярной, если на некотором шаге
7). существует но меньшей мере одно состояние, которое может быть
достигнуто из любого начального состояния.
Пример: Случайные блуждания (продолжение).
Рассмотрим пример случайных блужданий студента и выясним,
является ли соответствующая этим блужданиям цепь Маркова ре-
гулярной.
Матрица переходных вероятностей (5.37) имеет два граничных
состояния в зависимости от того, является ли число временных ша-
гов п четным или нечетным
/ 1/3 0 2/3 0
0 2/3 0 1/3 (5.48)
lim
1/3 0 2/3 0
N-*oo
V 0 2/3 0 1/3
Глава 5. Стационарные дискретные, источники с памятью


О 2/3 0 1/3

( 1/3 0 2/3 О
О 2/3 0 1/3
1/3 0 2/3 О
поэтому, в данном случае цепь Маркова не является регулярной.
С другой стороны, не выполняется и последнее условие из опреде-
ления 5.3.4, так как на каждом шаге все четные состояния переходят
в нечетные и наоборот (см. рис. 5.2).
Замечание. Если мы выберем начальное распределение, например
равное ро из (5-46), то на любом временном шаге любое из состоя-
ний достижимо.
Пример: Марковская цепь с тремя состояниями.
Пусть марковская цепь задана графом состояний (рис. 5.5)




Рис. 5.5. Граф состояний.

1. Постройте матрицу переходных вероятностей.

2. Покажите, что цепь Маркова стационарна. При этом исходите
из равномерного начального распределения состояний.

3. Покажите, что цепь Маркова регулярна.

4. Постройте предельную переходную матрицу.
Решение.
1. Матрица переходных вероятностей

/ 1/2 1/2 0\
П= 0 1/2 1/2; (5.50)
\ 1/2 0 1/2 /
5.3. Конечные цепи Маркова

2. Стационарность.
Так как начальное распределения состояний равномерно, то

Р о = 1/3(1, 1, 1), (5.51)

при этом выполняется условие (5.4)

/1/2 1/2 0 \
р о П = 1/3(1, 1,1) 0 1/21/2 = 1/3(1, 1, 1)=ро; (5-52)
\1/2 0 1/2/

3. Цепь Маркова регулярна, так как


2
П =Ы 011 011 =1/4 112 (5.53)
W




и для П 2 выполняется последнее из условий определения 5.3.4;
4. Предельная переходная матрица.
Так как цепь Маркова регулярна, воспользуемся определением
5.3.4, согласно которому р ^ = ро и из 5.51 имеем


= 1/3 111 . (5.54)



5.3.2. Конечные дискретные марковские
источники с памятью г
Марковские цепи можно с успехом использовать для моделирования
конечных дискретных источников с памятью. Предполагая, что сто-
хастические параметры источников с памятью могут быть подсчита-
ны как средние по времени величины (то есть источники обладают
свойством эргодичности), наметим пути дальнейших рассуждений.
Пусть задана произвольная последовательность {я[п]} = {а,Ь,а,
источника с алфавитом X = {a,6,c,d}.
r,b,b,a,d,a,d,b,b,a,c,...}
Мы уже ранее определили частоты событий, как оценки для вероят-
ностей событий р(а), р{Ь), р(с) и p(d) и нашли энтропию источника,
считая события независимыми. Если источник обладает памятью, то
его энтропия может быть только меньше, то есть ранее мы находили
оценку сверху.
Возникает вопрос, каким образом можно включить в анализ па-
мять источника.
Глава 5. Стационарные дискретные источники с памятью

Для этого необходимо учитывать зависимость между событиями.
Оценим условные вероятности р(а/а), p(b/a), p(c/a), p(d/a), p(a/b),
... и p(d/d) двух последовательных событий путем подсчета частот
парных событий. После этого источник может быть разложен на че-
тыре подисточника, соответствующих первым символам в парных
событиях.
На рис. 5.6 этот первый шаг рассуждений наглядно продемон-
стрирован. Здесь символ а определяет один из четырех нодисточни-
ков. Событиям, происходящим за.символом а (путям на графе), при-
писываются веса, равные вероятностям, например р(а'(Ь) = р(Ь/а).
Таким образом, каждый такой подисточник уже может рассматри-
ваться как некоторый самостоятельный источник без памяти. Энтро-
пия такого источника может быть вычислена известными методами.
Исходный источник с памятью представляет собой стохастическую
совокупность четырех нодисточников без памяти, а его энтропия
определяется средними значениеми энтропии этих нодисточников.
Мы можем продолжить рассуждения, рассматривая все более длин-
ные состояния подисточников (например, векторы а, а или а, Ъ, с, d)
до тех пор, пока вся память исходного источника не будет охвачена.




Р и с . 5.6. Представление источника в виде цепи Маркова

<< Предыдущая

стр. 9
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>