Ниже используется следующий алфавит русского текста

Обозначая через p(b/a)=p(ab)/p(a), bÎ B условные вероятности сообщений схемы B при условии сообщения a, можно рассмотреть ряд «условных» вероятностных схем

B/a= .

Для каждой из этих схем согласно (1) можно определить энтропию

H(B/a)= .

ОПРЕДЕЛЕНИЕ. Среднее значение

H(B/A)= = – (2)

называется условной энтропией схемы В при условии схемы А.

Взаимная информация между вероятностными схемами. Исходя из установленного выше понятия энтропии как меры неопределенности случайного сообщения, введем меру количества информации о сообщении «a», содержащемся в сообщении «b», как разность между количеством неопределенности (априорной) в сообщении «a» и количеством неопределенности в сообщении «a» при известном сообщении «b».

ОПРЕДЕЛЕНИЕ.Количеством информации о сообщении «a», содержащемся в сообщении «b», называется величина

i(ab)=h(a)-h(a/b)=log₂p(a/b)/p(a).

ОПРЕДЕЛЕНИЕ.Среднее значение

I(AB)= = .

называется взаимной информацией между A и B.

Введем в рассмотрение вероятностную схему B с вероятностями исходов

q(b)= .

Тогда величину I(AB) можно выразить через энтропийные характеристики следующим образом:

I(AB)=H(A)-H(A/B)=H(B)-H(B/A).

Свойства энтропии.

1. H(B/A)= H(AB) – H(A). (3)

Действительно,

H(B/A)= = +

+ =H(AB) – H(A).

2. H(B/A)£H(B), (4)

Нетрудно показать, что выполняется неравенство lnx-x+1£0. Действительно, для функции f(x)=lnx-x первая производная обращается в 0 в точке x=1, причем f(1)=0, а для всех x>0. Следовательно, f(x) имеет единственную точку максимума при x=1. Для двоичного логарифма имеем:

log₂x=lnx/ln2=(x-1)log₂e.

Тогда

H(B/A) – H(B)= + = + =

= £

3. Пусть на алфавите A вероятностной схемы A задано отображение j(.) в множество C. Это отображение определяет вероятностную схему C с алфавитом С, для которой p(с)= . Тогда выполняется неравенство H(C)£H(A), и знак равенства имеет место в том случае, когда отображение j(.) обратимо.

Легко видеть, что условное распределение p(c/a)=1, если j(a)=c и p(c/a)=0 в противном случае. Следовательно, H(C/A)=0. Далее, нетрудно проверить, что

H(C)–H(C/A)=H(A)–H(A/C)

и, следовательно,

H(C)+H(A/C)=H(A)+H(C/A).

Тогда,

H(C)£ H(C)+H(A/C)=H(A)+H(C/A)= H(A)

и равенство имеет место в том случае, когда отображение j(.) обратимо и H(A/C)=0, H(C)=H(A).

4. H(AB)£H(A)+H(B), причем равенство достигается в том и только в том случае, когда A и B независимы. Это свойство непосредственно следует из свойств 2 и 3.

5. Энтропии трех вероятностных схем A, B и W.

Энтропия вероятностных схем A и B при W:

H(A,B/W)= – p(a,b,w)log₂p(a,b/w)

Энтропия A, B, и W:

H(A,B,W)= - p(a,b,w)log₂p(a,b,w)

Ниже представлен список информационных тождеств и отношений,

H(A, B, W) = H(A/B, W) + H(B, W)= H(A, B/W) + H(W)

H (A/B, W) +H(B/W) =H(B/A, W) +H(A/W)

6. Если мы имеем A^(L)= – m независимых объединений схемы А, то

H()=

= LH(A)

и в этом случае

.

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

Теоремы Шеннона. Обозначим через A_L последовательность , полученную с помощью независимых испытаний из конечной вероятностной схемы

А= ,

P(A_L)= – вероятность последовательности A_L. Оказывается, что при больших L все последовательности (за исключением сколь угодно малой их доли) имеют приблизительно одинаковую вероятность, величина которой зависит от энтропии H(A). Качественное объяснение этого факта достаточно простое. Так как символы в последовательности A_L независимы, то энтропия на символ текста равна H(A)= – . Предположим, что рассматривается длинное сообщение, то есть L велико. Тогда последовательность A_L будет, так сказать, «с большой вероятностью содержать р(а)L раз» символ аÎ . Вероятность конкретной последовательности A_L есть

,

где n_a – частота буквы «a» в последовательности A_L. Заменяя n_a на р(а)L, получаем «приближенное равенство»

Р(A_L)@ ,

а log₂ Р(A_L) @L =-LH(A), откуда

Н(A)@ .

Это приближенное равенство остается верным и для любого стационарного источника (стационарной последовательности). Распространение указанного утверждения на цепь Маркова осуществил Хинчин А.Я., а на произвольный стационарный источник – Макмиллан. Пусть, как и прежде, А={1,2,…a,…n} – конечное множество исходов, соответствующее вероятностной схеме

А=

Первая теорема Шеннона. Для любых существует L₀ такое, что при любом множество А^L всех последовательностей длины L алфавита А разбиваются на группы (A^L)^* и (A^L)^** такие, что

1) для любой A_LÎ(A^L)^*

;

2) .

ДОКАЗАТЕЛЬСТВО.Нетрудно видеть, что

,

где n_a – частота буквы «a» в последовательности A_L. Отнесем к первой группе (A^L)^* те и только те последовательности A_L, в которых

для некоторой d>0. Ко второй группе отнесем все остальные последовательности.

Покажем, что при достаточно большом L₀ это разбиение удовлетворяет обоим условиям теоремы. Действительно, для

.

Отсюда нетрудно показать, что

.

Следовательно,

.

Полагая

,

получаем первое утверждение теоремы.

Рассмотрим вторую группу (A^L)^**. Нетрудно видеть, что вероятность

По неравенству Чебышева

откуда следует, что

Полагая L₀=n/d²e, получаем второе утверждение теоремы.

СЛЕДСТВИЕ.Если L³L₀, то для любой A_LÎ(A^L)^* выполняется неравенство

.

Таким образом, при достаточно больших L вероятность каждой последовательности из (A^L)^* (за исключением последовательностей весьма маловероятного класса) заключена между 2^-L(H+h) и 2^-L(H-h).

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

Занумеруем все последовательности A_L в порядке убывания их вероятностей:

.

Выберем l, 0<l<1. Пусть N_L(l) – число последовательностей, определяемых из неравенства

.

В это число войдет некоторое число последовательностей А_L второй группы, у которых Р(А_L)>2L(Н(А)-h), но в основном оно определяется последовательностями первой группы.

Вторая теорема Шеннона. Для любого фиксированного значения l, 0<l<1 справедливо соотношение

.

ИМЕННО В ЭТОМ СМЫСЛЕ ПИШУТ, что N_L(l)=2^LН(А). Как следует из формулы, этот предел не зависит от l и поэтому можно полагать l сколь угодно близким к 1, l=1-D и тогда n^L– N_L(1–D) есть число последовательностей, вероятность появления которых в результате реализации нашего случайного процесса получения последовательностей пренебрежимо мала, то есть практически невозможных последовательностей.

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

Таким образом, в первой и второй теоремах Шеннона устанавливается замечательное свойство «равнораспределенности» длинных сообщений, порождаемых независимыми испытаниями схемы А.

Это свойство устанавливает, грубо говоря, тот факт, что всего таких сообщений

N_L»2^LH(A) и все они приблизительно равновероятны.

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

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

Глава 11.