Вернер М. Основы кодирования (2004), страница 7

Одно из состояний в момент времени п всегда достигается прилюбом Si в момент п\г) = 1-(5.24)5.3. Конечные цепи Маркова512. Граничное распределение, т.е. вероятности j'-ro состояния вмомент времени п2N5Z я'па.щО'Л) = Pmti)-(5-25)3. Рекурсивная формула для переходных вероятностей (частныйслучай уравнения Колмогорова - Чэнмена.)Nтпз.шО'А) = X! 7r "3,n2070Tn 2 ,ni(/A)-(5.26)Дискретное равенство Колмогорова - Чэпмена получается трансформацией «правила цепочки» для вероятностейp{xi,x2)=p(x2/xi)p(xi),(5.27)р(х ь а;2,хз) = p(x3/xi,x 2 )p(x2/xi)p(xi).(5.28)Умножая обе части равенства на \/р(х{), получимр{х2,х3/х3)=р(хз/х1,х2)р(х2/х1).(5.29)Суммируя по всем х2, приходим к дискретной форме уравнения Колмогорова - Чэпменаp(x3/xi) = ^2P(X3'/XI,X2)P(X2/XI).х2(5.30)При преобразовании (5.30) в (5.26), мы предполагаемр(хз/хьх 2 ) =р(х 3 /хг).(5.31)Последнее равенство характеризует марковский процесс.Определение 5.3.1.

Марковским процессом называется процесс, вкотором прошлое не оказывает влияния на будущее, если настоящееизвестно.Замечание. В рассмотренном примере известное прошлое этостохастическая переменная Х\, известное настоящее - Х2, неизвестное будующее - Х3.Применение цепей Маркова сильно упрощается, когда они гомогенны, стационарны и регулярны. Рассмотрим эти три понятия.Глава 5. Стационарные дискретные источники с памятьюОпределение 5.3.2. Цепь Маркова гомогенна, если переходные ве- /роятности между состояниями не зависят от выбора временной точ-еки отсчета./Таким образом, переходные вероятности зависят только от раз(ности времен отсчетов I.Tr{j/i) = p(s[n] = Si U a[n + I] = Sj) n = 0,1,2,3,...

.(5.32)В этом случае для I = ri2 - n\ и т = пз — пг равенство Колмогорова - Чэпмена (5.26) можно записать в виде(5.33)n+m{Jli) =Это равенство может быть представлено в виде суммы покомпонентных произведений векторов-строк на векторы-столбцы. Записав переходные вероятности в виде матрицы, получим уравнение (5.33) вматричной форметг 1 + т (1/1)т+т{2/1)• • • TTl+m(N/l)7г(+т(1/2)тг,+т(2/2)•••n+m(2/N)•••\jrJ+ra(l/JV)7T,(2/1) • • • m(N/l) \JT,(2/2) • • • TrHiV/2)ym(l/N)m(2/N)\m+m(N/2)(5.34)7rl+m(N/N)JI 7T m (l/l) 7Tm(2/l)7r m (l/2) 7r m (2/2)• • • *i{N/N)J\nm(l/N)7rm(2/N)• • • itm(N/N)JЭТОТ процесс может быть начат с первого шага с помощью матрицы переходных вероятностей7T(2/1)п=тг(1/2)TT(2/2)тг(ЛГ/2)7r(l/iV)тг(2/ЛГ)••• 7r(iV/iV)(5.35)Заметим, что матрица П - стохастическая матрица с суммой вероятностей строк равной 1.Многократно применяя такое матричное преобразование к исходному распределению состояний ро, мы можем получить распределение вероятностей рп в любой момент времени прп = р0П".(5.36)5.3.

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

Каждому пути приписан вес, равный переходной вероятности. Таким образом, граф состояний дает полную информацию о матрице переходных вероятностей.ПереходнаявероятностьР и с . 5.3. Граф состояний гомогенной цепи Маркова.Пример: Случайные блуждания студента (продолжение).Случайные блуждания (см. рис. 5.2) представлены на рис. 5.4 ввиде графа состояний.Рис. 5.4. Граф состояний для случайных блужданий студента.1—1Графу состояний соответствует матрица переходных вероятностей01001/21/2 00(5.37)П =1/2 0 1/20000Из рис. 5.2 следует, что исходное распределение состоянийРо = (О, 0, 0, 1).(5.38)Глава 5. Стационарные дискретные источники с памятьюВероятность того, что в результате случайных блужданий студентна 7-ом временном шаге окажется у дверей общежития, определяется нервой компонентой вектора состояний на 7 шаге Pj.

Из (5.36)следуетР7=РоП7(5.39),Расчеты с помощью компьютера дают(О0,61900,3281 \0,335900,6641000,664100,3359 Г0,328100,67190/,_...( 5 Ж ) )Отсюдар 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, Рз, РА), тогда(0 1 0 01/20 1/2001/201/2001 0= (Рг/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) имеет два граничныхсостояния в зависимости от того, является ли число временных шагов п четным или нечетнымlimN-*oo/ 1/3 0 2/3 00 2/3 0 1/31/3 0 2/3 0V 0 2/3 0 1/3(5.48)Глава 5. Стационарные дискретные, источники с памятью(О2/301/31/30 2/3 ОО 2/3 01/31/30 2/3 Опоэтому, в данном случае цепь Маркова не является регулярной.С другой стороны, не выполняется и последнее условие из определения 5.3.4, так как на каждом шаге все четные состояния переходятв нечетные и наоборот (см. рис.

5.2).Замечание. Если мы выберем начальное распределение, напримерравное ро из (5-46), то на любом временном шаге любое из состояний достижимо.Пример: Марковская цепь с тремя состояниями.Пусть марковская цепь задана графом состояний (рис. 5.5)Рис. 5.5. Граф состояний.1.

Постройте матрицу переходных вероятностей.2. Покажите, что цепь Маркова стационарна. При этом исходитеиз равномерного начального распределения состояний.3. Покажите, что цепь Маркова регулярна.4. Постройте предельную переходную матрицу.Решение.1. Матрица переходных вероятностейП =/ 1/20\ 1/21/21/200 \1/2;1/2 /(5.50)5.3. Конечные цепи Маркова2. Стационарность.Так как начальное распределения состояний равномерно, тоР о = 1/3(1, 1, 1),(5.51)при этом выполняется условие (5.4)р о П = 1/3(1, 1,1)/1/2 1/2 0 \0 1/21/2 = 1/3(1, 1, 1)=ро;\1/2 0 1/2/(5-52)3. Цепь Маркова регулярна, так какП2=Ы0 1 10 1 1=1/41 1 2(5.53)Wи для П 2 выполняется последнее из условий определения 5.3.4;4.

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

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

Здесь символ а определяет один из четырех нодисточников. Событиям, происходящим за.символом а (путям на графе), приписываются веса, равные вероятностям, например р(а'(Ь) = р(Ь/а).Таким образом, каждый такой подисточник уже может рассматриваться как некоторый самостоятельный источник без памяти. Энтропия такого источника может быть вычислена известными методами.Исходный источник с памятью представляет собой стохастическуюсовокупность четырех нодисточников без памяти, а его энтропияопределяется средними значениеми энтропии этих нодисточников.Мы можем продолжить рассуждения, рассматривая все более длинные состояния подисточников (например, векторы а, а или а, Ъ, с, d)до тех пор, пока вся память исходного источника не будет охвачена.Р и с .