1.3. Условная энтропия. Свойство иерархической аддитивности

Обобщим формулы (1.2.1), (1.2.3) на случай условных вероятностей. Пусть имеются случайные величины описываемые совместным распределением . Условной вероятности

сопоставляем случайную условную энтропию

Введем особое обозначение для результата усреднения ее по

также для результата полного усреднения:

Рис. 1.1.

Этапы разбиения и «дерево выборов» в общем случае.

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

Прежде чем перейти к формулировке основного иерархического тождества (1.3.4), покажем, как можно ввести иерархическое множество случайных величин даже если первоначально была лишь одна случайная величина

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

Пусть указывает номер этого подмножества. На вто ром этапе каждое подмножество делится на более мелкие подмножества Вторая случайная величина указывает, какому более мелкому подмножеству принадлежит реализация случайной величины. Эти более мелкие подмножества делятся, в свою очередь, до тех пор, пока мы не получим подмножества, состоящие из одного элемента. Число нетривиальных этапов разбиения, очевидно, не может превосходить Фиксированной схеме разбиений можно сопоставить «дерево», изображенное на рис. 1.1. Дальнейшие рассуждения будут относиться к какому-то одному выбранному «дереву».

Рис. 1.2. «Дерево выборов» для одного конкретного примера.

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

В качестве примера «дерева» можно указать простое «дерево», изображенное на рис. 1.2, которое рассматривал Шеннон.

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

Энтропия, связанная с выбором одной ветви из этого узла, есть не что иное, как условная энтропия типа (1.3.2) при

Усреднение по всем узлам второго этапа, как и в (1.3.3), дает полную энтропию выбора на втором этапе:

Вообще энтропия выбора на этапе в узле, который определяется значениями равна

а полная энтропия этапа

Для примера на рис. 1.2 энтропия первого этапа равна бит. Узел имеет энтропию а узел В — энтропию бита.

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

что, действительно, совпадает с суммой Это имеет место не только для данного примера.

Теорема 1.4. Энтропия обладает свойством иерархической аддитивности:

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

Логарифмируя (1.3.5) и учитывая определение (1.3.1) случайной условной энтропии, имеем

Усредняя это равенство в соответствии с (1.3.3), получаем равенство (1.3.4). Доказательство закончено.

Свойство, о котором идет речь в теореме 1.4, является проявлением того простого принципа аддитивности, который был принят в § 1.1. Оно является следствием выбора логарифмической функции в (1.1.1). Легко понять, что из этого свойства вытекает свойство аддитивности (1.2.8), (1.2.9). В самом деле, для независимых случайных величин условная вероятность совпадает с безусловной. Логарифмируя эти вероятности, имеем и после

усреднения Следовательно, равенство обращается

Частное проявление свойства (1.3.4) для двухэтапного разбиения было принято Шенноном [1], а также Файнстейном [1] в качестве одной из аксиом для вывода формулы (1.2.3), т. е. в сущности для специализации логарифмической меры информации. И при других аксиоматических способах определения количества информации свойство аддитивности в той или иной (может быть слабой и частной) форме приходится постулировать, чтобы выделить специальную логарифмическую меру.

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

Теорема 1.5. Каковы бы ни были распределения вероятностей и выполняется неравенство

Доказательство близко к доказательству теоремы 1.2. Оно основано на использовании неравенства (1.2.4) для функции Положим теперь и будем проводить усреднение с весом

Тогда

и

Подстановка этих значений в (1.2.4) дает

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

Теорема 1.6. Условная энтропия не может превосходить безусловную:

Доказательство. Пользуясь теоремой 1.5, заменим в ней на на ; тогда будем иметь

Усреднение этого неравенства по с весом приводит к неравенству

что совпадает с (1.3.8). Доказательство закончено. Аналогично доказывается следующая теорема.

Теорема.1.6а. При добавлении условий условная энтропия не увеличивается: