книги из ГПНТБ / Бовбель, Е. И. Элементы теории информации

и

что и требовалось доказать.

Результат этой задачи показывает, что в отличие от относительной энтропии количество информации, содер­ жащееся в одной случайной величине X о другой У, но­

_ у> — коэффициент корреляции случай

У <х2> < у 2>

пых величии X и У.

От в е т : 1{Х, Y)' — — log \/і — у .

§ 5. Определение плотности вероятности, доставляющей максимум относительной энтропии

Найдем вид функции w(x), обеспечивающей макси­ мум функционалу

Н (X) — — I w (х) logw(x)dx

__со

при заданной дисперсии случайной величины X, т. е.

40

тей. Другими словами, при заданном среднеквадратиче­ ском разбросе та из случайных величин «ведет себя наи­

Уместно здесь же сформулировать еще одну важную задачу, которая является частным случаем решенной. Предположим, что' имеется множество случайных вели­ чин со всевозможными законами распределения вероят­

* См. Л. Э. Э л ь с г о л ь ц . Дифференциальные уравнения и ва­ риационное исчисление. М., 1969.

41

ностей и с различными среднеквадратическими разбро­ сами относительно среднего, равного нулю. Какое рас­ пределение вероятностей обладает в этом случае наибольшей неопределенностью (наименьшей предска­ зуемостью) ?.

В точной постановке задача гласит: найти такую функцию w(x), которая доставляет максимум энтропии Н г (Х) при одном дополнительном условии (1.32), огра­ ничивающем возможный выбор функций w(x).

Итак, если дисперсия случайной величины X не ограниче­ на, ее наблюдаемые значения обладают наибольшей ин­ формативностью, когда она им'еет равномерное распреде­ ление вероятностей (1.34).

Задача 1. Определить энтропию случайной величины, распределенной по экспоненциальному закону:

(с > 0).

= — löge + loge = log

Задача 2. Показать, что при заданной энтропии гаус*

совское распределение вероятностей w(x) = —J=—-expf-—А-Л

имеет наименьшую из всех одномерных распределений дисперсию.

Р е ш е н и е . Чтобы найти функцию w(x), доставля­ ющую мимммум дисперсии

о2 — Г x 2w{x) dx

t/

_эо

при заданной энтропии

42

/

Наконец, подставим (й.38) и (1.39) в (1.37):

&у(а) = \/ exp (2 //с In 2 — 1) ехр [— тс ехр (2Н. In 2 — 1) а2] =

7 1 Т 7 Г е х р (_ 2«®

где

X • Y 2тс ехр (2Н In 2—1)

Задача 3. Среди всех законов распределения непре­ рывной случайной величины X с плотностью вероятности, равной нулю для л'<0, найти при заданном математи­ ческом ожидании тх закон распределения с максималь­ ной энтропией.

Задача 4. Вычислить относительную энтропию случай­ ной величины X, распределенной по гауссовскому за­ кону.

43

Р е ш е н и е . Подставим (1.31) в (1.26). Получим

со

dx -|-

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

Задача 5. Имеется два источника флюктуирующего напряжения с одинаковой энтропией, но разными зако­ нами распределения вероятностей: первый — гауссовским законом, второй— равновероятным. Сравнить их мощ­ ности.

Р е ш е н и е . Как мы знаем, энтропия источника с га­ уссовским законом распределения вероятностей

/-/Е(Л') = log \/2пеаГі

(Ь—а )— ширина интервала возможных напряжений вто­ рого источника.

По условию задачи, источники обладают одинаковой информативностью, т. е.

\/2тс 6 ог b’— а.

По определению, дисперсия для равновероятного распре­ деления

°і = (’ (* — < * » 2 w(x) dx =

00

44

Г Л А В А 2

ИСТОЧНИКИ ДИСКРЕТНЫХ СООБЩЕНИЙ

§ 1. Эргодические источники и их энтропия

Объект, состояние которого определяется физическим процессом, протекающем во времени по заранее не из­ вестному закону, назовем источником сообщений. Будем считать, что число возможных сообщений, вырабатывае­ мых источником, конечно, и обозначать их символами Х\, Х о , ..., хп. Чтобы определить среднее количество инфор­

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

Таким образом, в эргодическом источнике /*-го порядка распределение вероятностей выбора символов p(xt) не остается постоянным, а зависит от того, какими были по­ следние г символов сообщения. Эти последние г симво­ лов определяют некоторое состояние Sk источника (k = = 1, 2, ..., m). Число »всевозможных состояний источника /'-го порядка, имеющего п различных символов, очевидно, определится выражением т = п г.

46

ч

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

Соотношение

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

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

Обозначим через P(Si) вероятность того, что источ­ ник находится в состоянии 5/, причем

какого состояния Sk источник, выработав некоторый сим­ вол, перешел в состояние 5 t. Так как вероятность состоя­ ния St зависит только от предыдущего состояния Sk и не зависит от того, в каких состояниях находился источник ранее (по определению состояния), неопределенность ис­ точника в состоянии S k можно найти по формуле, анало­ гичной (2.1):

H(Sk) = - 2 /> С З Д ) log Р (S/АЗД. .

1\к

47

Величина H (S k) случайно меняется в зависимости от состояния источника, поэтому только среднее значение li(Sfi) может характеризовать энтропию источника:

ч

т

где значок l/k у суммы означает, что производится сум­ мирование по всем переходам из состояния Sk b S^.

Задача 1. Сколько различных последовательностей, со­ держащих по 5 символов, можно составить из алфавита, содержащего два различных символа?

волов Х\ и ,ѵ2, вырабатывает последовательность хь х2>х% Хи Хо, хь Х2>Л'і ... Вероятностныесвязи в данной последова­

стояний источника равно 23= 8 . Выпишем их, нумеруя со­ стояния соответствующими индексами:

Чтобы установить, в каком состоянии находится источ ник, необходимо подождать, пока он выработает три сим вола. Поэтому в последовательности Х\Х2Х2Х\Х2Хі*2*і...

первым состоянием является <Si22. Затем источник после появления символа х\ переходит в состояние S22i и таг далее. Получается следующая последовательность состоя ний, проходимая источником:

48

Задача 3. Показать, что при отсутствии вероятностной связи между символами из формулы (2.3) следует фор­ мула (2.1).

Р е ш е н и е. Когда символы источника независимы, как следует из равенства

PiXj/xW, ..., *<'>) = P{Xj),

у источника имеется лишь одно состояние So, вероятность которого, на основании (2.2),

Поэтому при появлении символа хс источник вновь воз­ вращается в состояние So, при этом

Подставляя (2.4) и (2.5) в (2.2), получаем

# ( * ) = ■ - 2 Р (хі) log Р(хД *= ■

£=1 /=1

ъ в

= - 2 P(Xi) log P(Xi)„

1=1

так как число различных переходов из So в S0 равно чис­ лу различных символов источника.

Задача 4. Получить из (2.3) формулы для энтропии эргодического источника, когда вероятностные связи име­ ют место между: а) двумя ^символами; б) тремя; в) че­

а вероятность перехода из состояния S k в St