Материал: 1 ИССЛЕДОВАННИЕ ДИСКРЕТНЫХ ИСТОЧНИКОВ ИНФОРМАЦИИ

Таблица 1.1

Распределение вероятности букв в текстах

Помимо неравновероятности появления букв, буквы в тексте зависимы. Так, после гласных не может появиться "Ь", мала вероятность сочетания более трёх согласных подряд, вероятность последовательности, не образующей осмысленных слов (идеальный источник), практически равна нулю. Расчёты показывают, что для текстов русской художественной прозы энтропия оказывается менее 1,5 бит на букву. Еще меньше, около 1 бита на букву, энтропия поэтических произведений, так как в них имеются дополнительные вероятностные связи, обусловленные ритмом и рифмами. Слово, рифмуемое с окончанием предыдущей стихотворной строки, легко угадывается без произнесения или чтения его, и поэтому информации не несет (I(x_i) = 0). Энтропия телеграмм обычно не превышает 0,8 бит на букву, поскольку их тексты довольно однообразны (особенно поздравительных).

Условная энтропия

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

Рассмотрим ансамбли X = {x_i} и Y={y_j} и их произведение XY={(x_i,y_j), P(x_i,y_j)}. Для любого фиксированного y_jY можно построить условное распределение вероятностей P(x_i/y_j) на множестве X и для каждого x_iX подсчитать собственную информацию

,

которую называют условной собственной информацией сообщения x_i при фиксированном y_j.

Ранее мы назвали энтропией ансамбля X среднюю информацию сообщений x_iX. Аналогично, усреднив условную информацию I(x_i/y_j) по x_iX, получим величину

,

называемую условной энтропией X при фиксированном y_jY. Заметим, что в данном определении имеет место неопределенность в случае, когда P(x_i/y_j)=0. Следует отмечалось, что выражение вида z log z стремится к нулю при z 0 и на этом основании мы считаем слагаемые энтропии, соответствующие буквам x_i с вероятностью P(x_i/y_j)=0, равными нулю.

Вновь введенная энтропия H(X/y_j) – случайная величина, поскольку она зависит от случайной переменной y_j. Чтобы получить неслучайную информационную характеристику пары вероятностных ансамблей, нужно выполнить усреднение по всем значениям y_j. Величина

называется условной энтропией ансамбля X при фиксированном ансамбле Y . Отметим ряд свойств условной энтропии.

1. .

2. , причем равенство имеет место в том и только в том случае, когда ансамбли X и Y независимы.

3. .

4. .

5. причем равенство имеет место в том и только в том случае, когда ансамбли X и Y условно независимы при всех z Z.

Обсудим «физический смысл» сформулированных свойств условной энтропии. Свойство 2 устанавливает, что условная энтропия ансамбля не превышает его безусловной энтропии. Свойство 5 усиливает это утверждение. Из него следует, что условная энтропия не увеличивается с увеличением числа условий. Оба эти факта неудивительны, они отражают тот факт, что дополнительная информация об ансамбле X, содержащаяся в сообщениях других ансамблей, в среднем, уменьшает информативность (неопределенность) ансамбля X . Замечание «в среднем» здесь очень важно, поскольку неравенство H(X/y_j) ≤ H(X), вообще говоря, не верно.

Из свойств 1 – 5 следует неравенство

, (1.4)

в котором равенство возможно только в случае совместной независимости ансамблей X₁, …,  X_n.

Напомним, что вычисление энтропии – это вычисление затрат на передачу или хранение букв источника. Свойства условной энтропии подсказывают, что при передаче буквы X_n+1 следует использовать то обстоятельство, что предыдущие буквы X₁, …,  X_n уже известны на приемной стороне. Это позволит вместо H(X_n+1) бит потратить меньшее количество H(X_n+1/X₁,…,X_n) бит. В то же время неравенство (1.4) указывает другой подход к экономному кодированию. Из этого неравенства следует, что буквы перед кодированием нужно объединять в блоки и эти блоки рассматривать как буквы нового «расширенного» источника. Затраты будут меньше, чем при независимом кодировании букв. Какой из двух подходов эффективнее?

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

Дискретные случайные последовательности. Цепи Маркова

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

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

Случайный процесс x₁, x₂, … со значениями x_iX, i = 1, 2, … задан, если для любых n указан способ вычисления совместных распределений вероятностей P(x₁…x_n).

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

,

где P(x_i) – вероятность появления x_iX в момент времени i. Для описания такого процесса достаточно указать вероятности P(x_i) для всех x_iX (всего N - 1 вероятностей).

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

Процесс называется стационарным, если для любых n и m имеет место равенство

,

в котором подразумевается, что x_i=x_i+m, i=1, …, n.

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

Числовые характеристики, в частности, математическое ожидание стационарных процессов не зависят времени. Рассматривая стационарные процессы, мы сможем вычислять независящие от времени информационные характеристики случайных процессов.

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

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

Случайный процесс x₁, x₂, … называют цепью Маркова связности s , если для любых n и для любых справедливы соотношения

.

Иными словами, мы называем марковским процессом связности s такой процесс, для которого при n > s

P(x_n / x₁,…,x_n-1)= P(x_n / x_n-s,…,x_n-1),

то есть условная вероятность текущего значения при известных s предшествующих не зависит от всех других предшествующих значениях.

Описание марковского процесса задается начальным распределением вероятностей на последовательностях из первых s значений и условными вероятностями вида P(x_n | x_n-s,…,x_n-1) для всевозможных последовательностей (x_n-s,…,x_n). Если указанные условные вероятности не изменяются при сдвиге последовательностей (x_n-s,…,x_n) во времени, марковская цепь называется однородной.

Однородная марковская цепь связности s=1 называется простой цепью Маркова. Для описания простой цепи Маркова с множеством состояний X={1,2,…,N} достаточно указать начальное распределение вероятностей {P(x_i),x_iX} и условные вероятности

,

называемые переходными вероятностями цепи Маркова.

Переходные вероятности удобно записывать в виде квадратной матрицы размерности N×N:

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

Обозначим через стохастический вектор, компоненты которого – вероятности состояний цепи Маркова в момент времени m, то есть , где P_m(i) есть вероятность состояния i в момент времени m, i = 1, ..., N. Из формулы полной вероятности следует, что

или в матричной форме

. (1.5)

Отсюда для произвольного числа шагов n получаем

.

Значит, вероятности перехода за n шагов могут быть вычислены как элементы матрицы ⁿ.

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

. (1.6)

Положим = . Тогда, воспользовавшись (1.5), получим = и, в конечном итоге, = при всех m. Таким образом, однородная марковская цепь стационарна, если в качестве начального распределения выбрано решение уравнения (1.6).

Стохастический вектор , удовлетворяющий уравнению (1.6), называется стационарным распределением для цепи Маркова, задаваемой матрицей переходных вероятностей .

Финальным распределением вероятностей называют вектор

(1.7)

(если предел существует).

Из этого определения следует, что финальное распределение – распределение вероятностей в момент времени m бесконечно далекий от начального момента времени m = 1. Было бы естественно ожидать, что оно не зависит от начального распределения . Оно не зависит также и от времени. Таким образом, распределение тоже (как и), в некотором смысле, – стационарное распределение. Как же соотносятся между собой и ?