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

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

Р е ш е н и е . .Каждая из .12 монет, взятая наугад, мо­ жет оказаться фальшивой. Поэтому количество инфор­ мации от сообщения «взятая наугад монета фальшивая»

Л = — log log 12 = 3,58 (бит).

Так как произвольное взвешивание имеет три равноверо­ ятных исхода (перевесила правая чашка, перевесила ле­ вая чашка, чашки весов остались в равновесии), коли­ чество информации от такого взвешивания

Каким же образом «отнять» у фальшивой монеты .за­ пасенную в ней информацию о своем отличии от других монет? Очевидно, необходимо так организовать взвеши­

разбить ее на три подгруппы (1 + 14-2), снова сравнить веса первых двух подгрупп (по одной монете); если чаш­ ки весов остались в равновесии, взять оставшуюся под­ группу, содержащую 2 монеты, и сравнить их веса. Та­ ким образом, последнее, третье взвешивание однозначно

10

Так как числа І(х\) = 2,32; І(х2) = 1; І(х3) = 1,74 появ­ ляются с соответственными вероятностями 0,2; 0,5; 0,3, среднее количество информации

— 2,32*0,2+1 • 0,5+ 4,74 -0,3= 1,49 (бит).

После усреднения количество информации, несомое исхо­ дом X], стало равным 1,49 бит, исходом х2 1,49 бит, исхо­ дом Xz 1,49 бит. Иными словами, операцией усреднения мы уничтожили индивидуальное различие исходов по их информативности.

FP)

0,5-

Рис. 1

Задача 5. В условиях предыдущей задачи вычислить дисперсию случайной величины / = —Іоg P ( x i ) и по­ строить функцию распределения.

Р е ш е н и е : По определению дисперсии

чина 1(х{) = — log Р(х-і) дискретна, ее распределением вероятностей является интегральная функция распреде­ ления F (I) (рис. 1).

Очевидно., что:

/7= 0 ,5 для 1</<Л ,74;

П

Задача 6. Пусть некоторый опыт имеет два возмож­ ных исхода Х\ и х2 с вероятностями появления Р(х\) —0Л II Р(х2) = 0,9. Производится большое число N независи­ мых опытов. Найти среднее количество информации,' при­ ходящееся на один исход опыта.

Р е ш е н и е. Обозначим конкретную последователь­ ность исходов, получаемую в результате N опытов, бук­ вой с. Тогда при достаточно большом N, согласно теоре­ ме Бернулли, вероятности исходов можно определить по формулам:

Р(XI) = «1 W, Р(Хг) = «2;N,

где п\ и по соответственно число исходов х\ и х2 в после­

Отсюда видно, что вероятность конкретной последова­ тельности не зависит от ее вида, а зависит только от ве­ роятности исходов х.\ и х2 и N. Поэтому всевозможные по­ следовательности с могут рассматриваться как равнове­ роятные и число их будет п = \/[Р(с)].

В этом случае для определения количества информа­ ции, несомого последовательностью с, можно воспользо­ ваться формулой (1.2):

Подставив сюда Р(х\) — 0,1 и Р(Хч)^ 0,9, получим

/ = —0,1 log 0,1—0,9 log 0,9 = 0,469 (бит)..

12

Задача 7. Показать, что при равной вероятности исхо­ дов опыта количество информации, определяемое форму­ лой (1.2), является неслучайной величиной.

Формула (1.2а) при равной вероятности исходов опы­ та примет вид

п

т. е. 1 не случайно, так как оно оказалось равным неслу­ чайной величине < / ( * / ) > .

В заключение заметим, что мера количества инфор­ мации в виде (1.2) была впервые предложена в 1928 г. американским инженером Р. Хартли. Ясно, что формула- p. Хартли относится к весьма частному случаю, когда по­ сле опыта неопределенности в исходе опыта нет и все ис­ ходы равновероятны. Однако заслуга Р. Хартли велика, ибо введенная им мера применима к информации любоговида и содержания и, что наиболее ценно, объективна и независима от психологических, факторов, так как опре­ деляется через объективно существующую статистику со­ бытий.

уже не выражает среднее количество информации, несо­ мое одним исходом опыта. Однако величина Н(Х) сохра­ няет за собой другой, фундаментальный для теории ин­ формации смысл (см. § 1), а именно: Н (X) выражает среднее количество неопределенности до опыта в наступ­ лении того или иного исхода и называется энтропией.

Рассмотрим основные свойства энтропии.

\.. Н(Х)'^> 0, причем знак равенства имеет место только в том случае, когда- у опыта имеется один-единст- венный исход с вероятностью «единица».

Положительность Н(Х) видна из (1.7): вероятности положительны и заключены между нулем и единицей, ло­ гарифмы таких чисел отрицательны, а равенство нулю

13;

возможно только для такого опыта, у которого один ис­ ход достоверен, а остальные равны нулю. Например:

О1 О о ...о

'§ I-

2.При заданном п энтропия максимальна и равна

log п, когда все исходы, составляющие опыт, равноверо­

/=1

а

при одном, очевидном, дополнительном условии

/=1

=1. Для этого * составим функцию

Подставляя в последнее равенство значение энтропии н выполняя дифференцирование, получаем

(ln Pi + 1) + X= 0,

* См. В. И. С м и р н о в. Курс высшей математики, т. 1. М., 1967г

14

■откуда P,- = exp(Xln2— 1). Чтобы найти неопределен­ ный множитель Лагранжа, подставим найденное зиаче--

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

3. Прежде чем сформулировать третье свойство, вве­ дем более сложный опыт, объединяющий два следующих опыта:

Будем рассматривать все возможные совместные ис­ ходы х£ и у/. Пары (х/, у/) с вероятностями их появле­ ния порождают некоторый новый опыт (X, Y), который схематично может быть записан в виде табл. 1:

15

Сравнивая эти равенства с (1.9), заключаем:

Н (X, У)4>Н ( X ) + H ( Y ) ,

- 2 2 р (Л'ь У]) lo g р (Уі*і) = Н(х ) + Н(У:Х), где мы

і м у - 1

ввели обозначение для величины

имеющей фундаментальное значение для теории инфор­

венство нулю возможно лишь тогда, когда события хі и

ход события y j . Другими словами, зная исход события Хі, мы не имеем неопределенности в исходе события yj .

18

Подставив (1.15) в (1.13), получим

информации о ijj, если х х и уу* независимы, т. е. средняя неопределенность в исходе у/ остается равной Н (Y), знаем ли мы об исходе л:/ или нет. Однако если события X/ и у j статистически зависимы, то, зная исход xt-, мы по­ лучаем некоторую информацию о том или ином возмож­ ном исходе события у/ и неопределенность Н (YIX)r уменьшается по сравнению с # (Т ). Последнее замеча­ ние сформулируем в виде свойства 9.

9. Если события Хі и у/ статистически зависимы, то всегда Н (Y/Х) < Н {Y).

Требуемое неравенство вытекает из свойства 5 при ис­ пользовании свойства 6.

Как мы видели, описанные свойства энтропии хорошо согласуются с интуитивными требованиями, которые можно предъявить к количественной мере неопределен­ ности. Это не случайно, ибо эти интуитивные представле­ ния были заложены нами в постулатах § 1.

Задача 1. Даны две дискретные случайные величины

зависит от значений, принимаемых случайными величи­ нами, а. зависит только от вероятностей их появления.

Задача 2. Располагая в виде табл. 2 совместные ве­ роятности сообщений х і опыта X и у/опыта У, рассчи­

тать точные и среднее количества неопределенности в совместном наступлении событий х£ и у/, а также точ­ ные и среднее количества неопределенности в у j при из­ вестном исходе х і .

Точные количества неопределенности в совместном наступлении событий х£ и у/ находятся по формуле

И (Х1. У і ) = — \ogP(xi, іи).

19