Графическое представление марковского процесса

Общий случай может быть описан следующим образом: существует конечное число возможных «состояний» системы: S₁,..., S_n. Кроме того, имеется совокупность условных вероятностей р_i(j), т. е. вероятностей того, что система, находящаяся в состоянии S_i, перейдет затем в состояние S_j,.

Чтобы использовать этот марковский процесс в качестве источника сообщений, нужно только предположить, что при каждом переходе из одного состояния в другое создается одна буква. Состояния будут соответствовать «остатку влияния» предшествовавших букв.

Это положение может быть графически проиллюстрировано, как показано на рис. 3, 4 и 5. «Состояниями» являются узловые точки схемы, а условные вероятности и создаваемые при этом буквы указаны около соответствующих линий.

Рис. 3. Граф, соответствующий источнику в примере Б

Рис. 3 соответствует примеру Б (выбираются независимо с вероятностями), где имеется только одно состояние, так как последовательные буквы независимы.

Рис. 4. Граф, соответствующий источнику в примере В

Рис. 4 соответствует примеру В (вероятности появления букв зависят от предыдущей буквы), где имеется столько же состояний, сколько букв. Если бы конструировался триграммный пример, то имелось бы самое большее n² состояний, соответствующих возможным парам букв, предшествующих выбираемой букве.

0,10 А	0,16 ВЕВЕ	0,11 CABED	0,04 DEB
0,04 ADEB	0,04 BED	0,05 CEED	0,15 DEED
0,05 ADEE	0,02 BEED	0,08 DAB	0,01 EAB
0,01 BADD	0,05 СА	0,04 DAD	0,05 ЕЕ

Рис.5. Граф, соответствующий источнику из примера Г

Рис. 5 представляет схему для случая структуры слов в примере Г (в языке пять букв и 16 «слов» с соответствующими вероятностями появления). Здесь S соответствует символу «пробел между словами».

1. Ергодичні і змішані джерела

Как уже было отмечено, дискретный источник в описанных ранее задачах может рассматриваться как марковский процесс. Среди всех возможных марковских процессов можно выделить группу со свойствами, важными для теории связи. В этот класс входят так называемые эргодические процессы, и мы будем называть соответствующие источники эргодическими.

Для эргодического процесса все сгенерированные последовательности обладают одинаковыми статистическими свойствами. К примеру, частоты встречаемости букв, диграмм и так далее, оцененные по отдельным последовательностям, сходятся с ростом длины выборок к определенным пределам, не зависящим от последовательности.

Другое определение эргодичности. Стационарный случайный процесс называют эргодическим, если при нахождении его моментных функций усреднение по статистическому ансамблю можно заменить усреднением по времени. Операция усреднения выполняется над единственной реализацией x(t), длительность Т, которой теоретически может быть сколь угодно велика.

На самом деле это верно не для всякой последовательности, однако множество последовательностей, для которых это не выполняется, имеет меру ноль (то есть обладает нулевой вероятностью). Грубо свойство эргодичности означает статистическую однородность.

Все вышеприведенные примеры искусственных языков являются эргодическими. Это связано со структурой соответствующих графов. Шеннон определил, что если граф обладает двумя следующими свойствами, соответствующий процесс будет эргодическим:

1. Граф не состоит из двух изолированных частей A и B, таких, что невозможно перейти с вершин одной части на вершины другой по линиям графа в разрешенном направлении, и с вершин второй - на вершины первой.

2. Назовем замкнутые серии ребер графа, которые можно обойти в разрешенном направлении, "циклом'. Длиной цикла назовем число ребер в нем. Тогда на рис. 5 серия ребер BEBES образует контур длины 5. Вторым требуемым свойством является равенство наибольшего общего делителя длин всех контуров на графе единице.

В математической литературе принято называть эргодическими процессы, обладающие свойством 1) и, быть может, не обладающие свойством 2).

Если первое условие удовлетворено, а второе нарушено тем, что общий делитель d > 1, то последовательности имеют некоторого рода периодическую структуру.

Различные последовательности распадаются на d различных классов, которые в статистическом отношении одинаковы, за исключением сдвига начала (т. е. выбора того, какую букву последовательности назвать первой). С помощью смещения на величину от 0 до d‑1 каждая последовательность может быть сделана статистически эквивалентной любой другой.

При d — 2 простым примером является следующий: имеются три возможные буквы а, b, с. За буквой а следует либо b, либо с с вероятностями 1/3 и 2/3 соответственно. За b и с всегда следует буква а.

Тогда типичная последовательность имеет вид:

abacacacabacababacac

Процессы такого типа не учитываются в контексте модели источника сообщений.

Если нарушено первое условие, то граф может быть разделен на некоторое число подграфов, каждый из которых удовлетворяет первому условию. Будем предполагать, что второе условие также выполняется для каждого подграфа. В этом случае имеет место то, что может быть названо «смешанным» источником, составленным из некоторого числа чистых компонент ‑ классов состояний. Эти классы состояний соответствуют различным подграфам. Если L₁, L₂, L₃...— источники, соответствующие этим классам, то можно записать

L = p₁L₁ + p₂L₂ + p₃L₃ + …

где p_i — вероятность класса L_i.

Физический смысл описанного состоит в следующем: имеется несколько различных источников L₁, L₂, L₃..., каждый из которых имеет однородную статистическую структуру (т.е. является эргодическим). Априори неизвестно, какой источник будет использован, но если последовательность начинается с состояния, принадлежащего данному классу состояния L_i, то она продолжается бесконечно в соответствии со статистической структурой этого класса.

В качестве примера можно взять два процесса из определенных выше и предположить, что p₁= 0,2 и р₂= 0,8. Последовательность из смешанного источника L = 0,2L₁ + 0,8L₂ могла бы быть получена следующим образом: сначала выбирается L₁ или L₂ с вероятностями 0,2 и 0,8, а затем выбранный источник создает последовательность. Если не оговорено противное, будем предполагать, что источник является эргодическим. Такое предположение позволяет отождествлять средние значения вдоль некоторой последовательности со средними значениями по ансамблю возможных последовательностей (причем вероятность расхождения равна нулю).

Например, относительная частота буквы в частной бесконечной последовательности будет с вероятностью единица равняться ее относительной частоте по ансамблю последовательностей.

Если p_i — вероятность состояния i, a р_i(j) — условная вероятность перехода в состояние j, то для того, чтобы процесс был стационарным, p_i должны, очевидно, удовлетворять условиям равновесия:

Можно показать, что в эргодическом случае при любых начальных условиях вероятности пребывания в состоянии j после N шагов P_j(N) при N®¥ стремятся к величинам, удовлетворяющим условиям равновесия.

Дата добавления: 2013-12-12