Приложение

Лемма. Пусть имеются М возможных событий с вероятностями Допустим, что энтропия Н удовлетворяет неравенству

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

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

Из того, что функция является выпуклой вниз с наклоном 1 при

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

или

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

Так как является монотонно возрастающей функцией от то отсюда следует, что

Первая оценка сверху получается с помощью представления соответствующего слагаемого в виде

Так как то нетрудно заметить, что при эта величина ограничена сверху числом справедливость леммы тривиальна в силу того, что при этом Оценка соответствующего слагаемого числом 3 очевидна. Последнее слагаемое имеет вид Дифференцируя, устанавливаем, что при она принимает максимальное значение, равное . Так как наш результат противоречит условию леммы, то тем самым она доказана.

Основным применением этой леммы является установление нижней грани для вероятности ошибки в системах кодирования. Если известно, что в некоторой ситуации «неопределенность», т. е. условная энтропия сообщения при заданном принятом сигнале, превышает величину А, то доказанная лемма дает нижнюю грань для вероятности ошибки. В самом деле, неопределенность является некоторым средним, взятым по множеству принятых сигналов. Отсюда где — вероятность принимаемого сигнала а — соответствующая энтропия, сообщения. Если — это нижняя грань, используемая в лемме, т. е.

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

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

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