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

Из (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)до тех пор, пока вся память исходного источника не будет охвачена.Р и с .

5.6. Представление источника в виде цепи Маркова(первый шаг).Эти эвристические рассуждения обобщены в следующем определении.Определение 5.3.5. Конечный дискретный марковский источникс памятью г полностью определяется следующими условиями:1. Задано непустое множество состояний S = {S\,S2, • • • ,SN},причем, S содержит векторы длины г;2. Каждое состояние Sj соответствует дискретному источнику безпамяти с алфавитом Xi = {2:1,0:2,..

• ,хм} и вероятностями j ых символов алфавита p^'(j);5.3. Конечные цепи Маркова3. Состояние S[n] = (х[п — г], х[п — г + 1],..., х[п — 1]) из г — 1последовательных символов и очередной символ х[п] образуютновое состояние S[n + 1] = (х[п — г + 1], х[п — г + 2],..., х[п]);4. Задано начальное распределение состоянийРО = (РО(1).РО(2),...,РО(ЛО).Мы видим, что память г охватывает г последовательных символов, так как на вероятность очередного символа оказывает влияниев точности г предыдущих символов.

Поясним это более подробно напримере.Пример: Марковский источник с памятью г = 2.Рассмотрим двоичный источник с алфавитом X = {0,1}. Комбинации двух символов дают четыре состоянияS = {S, * (0,0),5 2 £ (1,1), S3 = (0,1),5 4 = (1,0)}.(5.55)Переходные вероятности между состояниями задаются величинамиP s , = ( 0 , l ) , p s 2 = (1/2,1/2),(5.56)Р5з = (2/3,1/3),р Л = (3/4,1/4).Если задать еще и начальное распределение состоянийРо = (РО(1),И>(2),РО(3),РО(4)),(5-57)то все требования из 5.3.5 выполнены и конечный марковский источник определен. Условия (5.55) и (5.56) являются достаточными дляпостроения графа состояний, который изображен на рис. 5.7.1:1/2Рис. 5.7. Граф состояний марковского источника с памятью г.Глава 5. Стационарные дискретные источники с памятьюПроанализируем матрицу переходных вероятностей и исследуемее на регулярность.

Матрица переходных.вероятностей строится пографу состояний рис. 5.7 и имеет вид/00П =0V 3/40 1 01/201/300 1/41/22/30(5.58)Регулярность проверяется с помощью предельной матрицы. Согласно определению 5.3.49 i1 12 12э г}1212(5.59)9 iS 12 129 {1 12 12Замечание. Предельная матрица была найдена с помощью программной системы MatLab (http://www.mathworks.com).Все строки предельной матрицы равны, следовательно она является регулярной.

Соответствующее предельное распределение имеетвид~(5.60)Принципы пошаговой аппроксимации источника с памятью обобщает следующее утверждение.Теорема 5.3.2. Стационарный марковский источник с памятью гможет быть аппроксимирован стационарным марковским источником с памятью I, где 0 < / < г.Если величина г заранее известна, то на нервом шаге аппроксимации рассматривается источник без памяти.Модель источника без памяти полностью описывается распределением вероятностей символов. Средняя вероятность символов - этовероятность, которую оценивает наблюдатель, не зная, в каком состоянии Находится источник, поэтому, она определяется стационарным распределением вероятностей состояний Роо и вероятностямисимволов а\,...,ам в состояниях S\,..., б1^,p(aM))=pa(5.61)\PsN(ai)pSN(a2)• • • PsN(aM)J5.3.

Конечные цепи Маркова61Пример: Марковский источник с памятью г = 2 (продолжение).• Источник без памяти (I = 0). В числовом примере для а\ = 0и П2 = 1 получаем/ 01(р(0),р(1)) = ^-(9,8,12,12) • 2/з J/V 3/4 1/4• Стационый марковский источник с памятью I = 1. В этом случае модель источника имеет два состояния. Соответствующийграф состояний изображен на рис.