Материал: Методические указания к выполнению курсовой работы по дисциплине «Теория информации» для студентов специальности «Компьютерная безопасность». Поздышева О.В., Остапенко А.Г

Можно определить Марковский источник общего вида, состояния которого не связаны с наборами из фиксированного числа букв.

Марковский источник называется эргодическим , если вероятность перехода через произвольное (большее некоторого фиксированного числа т число шагов из каж-

дого состояния si в произвольное состояние sj больше нуля.

Если для некоторого эргодического Марковского источника с п состояниями известны только вероятности перехода из одного состояния в другое, то вероятности его

состояний можно получить из системы уравнений

n

∑ p(Si1) log p(Si1) = p(Si),

j=1

∑ ( ) = 1.

=1

ПустьS — Марковский источник первого порядка с алфавитом {a1, . . ., ak}, и вероятности p(ai/aj) появления буквы щ вслед за буквой ai записаны в матрице Q = {qi j }, гдеqi j =p(ai/aj). Тогда вероятности р (ai ) можно вычислить из уравнения Qp = р , где р = (р(аi), . . . ,р(аk)), учитывая, что ∑ p(ai)=1.

Марковский источник можно полностью задать набором его состояний s1, . . .,sn, матрицей вероятностей перехода из одного состояния в другое p(si / sj) и набором вероятностей порождения букв в каждом из состояний p(a1 / sj ), . . . ,p(ak / sj ), 1 < j < п . Если считать, что последовательности, порождаемые источником, бесконечны только в одну сторону, т. е. имеют начало, то для пол-

14

ного определения источника нужно задать еще начальное состояние.

Разделим бесконечную последовательность букв, порожденную Марковским источникомS с состояниями

на n подпоследовательностей, каждая из которых состоит из букв, порожденных в определенном состоянии sj. Поскольку вероятность появления очередной буквы зависит только от состояния источника, то буквы j-й последовательности появляются независимо друг от друга с вероятностями p(ai/aj). Имея в виду этот факт, говорят, что Марковский источник разделяется на п источников Бернулли, каждый из которых определяется набором условных вероятностей р (a1 /sj ), . . . ,p(ak /sj ), 1 ≤j≤ п, и

обладает энтропией

( ) = − ∑ ( ⁄ ) log ( ⁄ ).

=1

Таким образом, получаем формулу для энтропии

Марковского источника S с состояниями s1, . . .,sn:

( ) =

= − ∑ ( ) ∑ ( ⁄ ) log ( ⁄ ) = − ∑ ( ) ( ).

Таким образом, последовательность, порожденную Марковским источником, можно эффективно кодировать, разделяя ее по числу состояний на п подпоследовательностей и кодируя каждую из них отдельно любым из побуквенных кодов.

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

15

не зависят от выбора временной точки отсчета, т.е. вероятности переходов зависят от разности временных отсчетов.

Гомогенная цепь Маркова является регулярной, ес-

ли[1]:

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

.

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

2. Предельное распределение вероятностей состояний p∞ является единственным стационарным распределением вероятностей состояний любой регулярной цепи Маркова.

p∞ = p0.

3.Цепь Маркова везде будет регулярной, если существует некоторое натуральное значение шага n, при котором все компоненты некоторого столбца матрицы вероятностей перехода на этом шаге n, будет отлично от нуля. Другими словами, цепь Маркова является регулярной если, на некотором шаге n существует по меньшей мере одно состояние, которое может быть достигнуто из любого начального состояния. Если в Марковской цепи вероятность очередного символа оказывает влияние на rпредыдущих символов, то говорят, что память такого источника охватываетr последовательных символов, а сам источник

16

называют конечным дискретным Марковским источником с памятью r.

Заметим, что такой источник обладает свойством и эргодичности. Тогда конечный дискретный эргодический Марковский источник с памятью r полностью считается заданным (или определенным) следующими условиями:

1.Задано непустое множество состояний

{ 1, 2, … , },

причем каждое состояние Si содержит вектор длиной r .

2. Каждое состояние Si соответствует дискретному источнику без памяти с алфавитом Xi = {x1,, x2, … , xM} и вероятностями j-ых символов алфавита

( ) = ( ⁄ ).

3.Задано начальное распределение вероятностей состояний

p0 = (p0(1), p0(2), …, p0(N)).

4.Состояние S[n], образованное из r-1 последовательных символов, после добавления очередного символа X[n] переходит в состояние S[n+1].

Энтропия стационарного эргодического Марковского источника вычисляется исходя из того, что некоторое состояние источникаSi является как бы подисточником без памяти, обладающим в свою очередь соответствующей энтропией. Тогда энтропия первоначального источника равна математическому ожиданию энтропии подисточников. Таким образом, стационарный эргодический Марковский источник с алфавитом из М символов, имеющий n состояний,

17

т.е. N подисточников без памяти энтропия каждого из ко-

торых равна

M

H (X⁄Si) = − ∑ pSi(xm) log2 pSi(xm),

m=1

где pSi(Xm)– вероятность символа Xm при условии Si состояния, обладает энтропией, равной математическому

оживанию энтропии подисточника.

N

H∞(X) = ∑ p∞H(X⁄Si),

i=1

где p∞– предельное распределение вероятностей состояний.

Таким образом, при t→∞ в системе S устанавливается некоторый предельный стационарный режим: хотя система случайным образом и меняет свои состояния, но вероятность каждого из них не зависит от времени и каждое из состояний осуществляется с некоторой постоянной вероятностью, которая представляет собой среднее относительное время пребывания системы в данном состоянии. Это свойство позволяет обходиться при нахождении параметров системы на основе моделирования одной достаточно длинной реализацией.

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

18