5. Граница для энтропии на основании частот предсказания

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

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

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

Слагаемые, стоящие в левой части неравенства, могут быть интерпретированы следующим образом: представим себе числа в виде упорядоченной последовательности отрезков убывающей высоты (рис. 3). Истинное значение можно рассматривать как сумму прямоугольных распределений, как это показано на том же рисунке. Левая часть неравенства (18) есть тогда энтропия этого множества отрезков. Таким образом, прямоугольное распределение имеет общую вероятность Энтропия этого распределения равна Общая энтропия равна

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

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

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

Рис. 3. Прямоугольное разложение монотонного распределения.

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

Следует отметить, что нижняя граница строго меньше за исключением того случая, когда каждая строка таблицы имеет

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

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

увеличивается при выравнивающем переносе между Предположим, что перенос происходит от причем первая вероятность убывает на а вторая возрастает на ту же величину. Тогда в сумме (20) изменяются три слагаемых и изменение и дается выражением

Член в скобках имеет вид Но функция выпукла при положительных х, поскольку

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