Марковские источники

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

Значение марковских цепей в теории информации заключается в том, что реальные источники информации вырабатывают сообщения (слова) при наличии статистической зависимости между символами (событиями, буквами). В реальных источниках вероятность выбора какого-либо очередного символа зависит от всех предшествующих.

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

Дискретный по времени и состояниям марковский процесс называется марковской цепью. Его реализацией является последовательность состояний

 

Для описания цепи Маркова используют следующие понятия:

a) Множество состояний где N – конечное число состояний;

б) Начальные условия, т.е. распределение вероятностей состояний в начале наблюдения (нулевой момент времени n=0);

в) Стохастический вектор распределения вероятностей состояний в момент времени n.

,

где n=0,1,2,…- дискретное время (натуральный ряд чисел).

г) Смена состояний описывается переходными вероятностями

.

 

Пример: Случайные блуждания студента

 

д) Переходные вероятности на совокупности состояний в разные моменты времени образуют соответствующие матрицу переходных вероятностей.

Заметим, что это стохастическая матрица с суммой вероятностей строк равной 1. Вычисление матрицы П производится с использованием рекурсивной формулы (частный случай уравнения Колмогорова-Чепмена)

.

Применение цепей Маркова сильно упрощается, когда они гомогенны, стационарны и регулярны.

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

, где =0,1,2,...

В этом случае для ; рекурсивная формула примет вид: .

Это равенство может быть представлено в виде суммы компонентных произведений векторов-строк на векторы-столбцы. Записав переходные вероятности виде матрицы, получаем уравнение в матричной форме:

Таким образом, можно получить матрицу переходных вероятностей на любом шаге а, следовательно, многократно применяя такое матричное преобразование к исходному распределению состояний , мы можем получить распределение вероятностейна любом шаге (в любой момент времени

Таким образом, гомогенная цепь Маркова полностью описывается матрицей переходных вероятностей и исходным распределением состояний.

Графическое представление цепей Маркова.

 

π(j/i)

 

π(i/j)

 

Гомогенная цепь Маркова является стационарной, если распределение состояний постоянно во времени. В этом случае начальное распределение является собственным вектором матрицы переходных вероятностей.

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

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

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

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

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

Заметим, что такой источник обладает свойством эргодичности.

Конечный дискретный эргодический марковский источник с памятью r полностью определяется следующими условиями:

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

2. Каждое состояние соответствует дискретному источнику без памяти с алфавитом и вероятностями j- тых символов алфавита .

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

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

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

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

,

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

, где - предельное распределение вероятностей состояний.

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

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