Приложение II. Неравенства Чернова

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

А. Неравенство Чернова для одной величины

Пусть дискретная случайная величина имеет распределение Обозначим производящую функцию моментов случайной величины I:

Функция непрерывна вместе со всеми производными в интервале —

Пусть величины суть независимых наблюдений случайной величины 1. Рассмотрим сумму

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

В силу независимости наблюдений

что позволяет переписать выражение (60) так:

Нас интересует вероятность того, что не менее некоторой величины, скажем А. Рассмотрим множество в этом множестве выполняется неравенство В силу этого из неравенства (60) следует, что

Принимая во внимание формулы (60а) и (61), можно переписать последнее неравенство:

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

где

Аналогично можно доказать неравенство

Нетрудно убедиться в том, что

где

Функцию мы будем назыьать "перекошенным" распределением вероятностей случайной величины

этот термин был впервые введен Крамером [4]. Математическое ожидание величины относительно этого распределения равно Нетрудно также показать, что

Таким образом, является дисперсией случайной величины I относительно "перекошенного" распределения. Величина всегда, кроме тривиального случая положительна при — следовательно, монотонно увеличивается с ростом

Коэффициент при в показателе правой части неравенств (63) и (13) равен Функция имеет производную, равную Итак, кроме случая функция причем равенство достигается лишь при

Математическое ожидание величины относительно распределения равно Следовательно, неравенство (63) справедливо лишь при значениях равных или превосходящих среднее значение величины тогда как неравенство (13) справедливо для значений не превосходящих среднее значение величины Далее, из формул (64) и (65) следует, что

где — минимальное и максимальное значения

величины соответственно. Таким образом, величина однозначно определяется величиной Область значений и а также их взаимосвязь графически изображены на рис. 2.

Предположим, что величина I с положительной вероятностью может принимать значение — но всегда остается меньше Тогда функция определена только для и потому не является производящей функцией моментов величины Тем не менее, вывод неравенства (63) остается справедливым для Если же I всегда больше — но с положительной вероят

ностью принимает значение то функция определена только для

В данной работе в качестве случайной величины чаще всего выбирается взаимная информация между и -входным и выходным символами дискретного канала с матрицей переходных вероятностей и входным распределением Это значит, что

где

С каждой парой символов мы связываем две вероятности:

и

Пользуясь равенством (58), можно определить функции соответствующие этим двум распределениям.

Если канал невырожденный [т. е. если для всех пар то случайная величина принимает только конечные значения и функции определены для

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

Подставляя выражения (69) и (70) в формулу (58), мы получаем, что в общем случае

Из формулы (71) следует, что

Сравнивая выражение для с выражением для мы находим

Для невырожденного канала соотношение (74) выполняется для Из него, в частности, что т. е. что равняется среднему значению величины I относительно распределения

Простота соотношения (74) делает выбор величины в виде весьма удобным для наших исследований.

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

В силу известного неравенства между геометрическим и арифметическим средними [9]

равенство достигается в том и только том случае, когда входные символы имеют равные вероятности перехода в выходной символ. Подставляя неравенство (76) в формулу (75), находим, что Равенство будет иметь место тогда и только тогда, когда все вероятности перехода в символ равны между собой при любом значении Так как пропускная способность канала в этом (и только в этом) случае равна нулю, то утверждение доказано.

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

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

Если выбирать в виде то величины можно определить так, чтобы условие (77) выполнялось. При из формулы (74) следует, что Подставляя в указанной форме в неравенство (63), получаем

Точно так же из неравенства (13) следует, что

Б. Неравенство Чернова для двух величин

Пусть суть случайные зависимые величины с распределением Рассмотрим независимых наблюдений пары величин , образуем две суммы

и найдем оценку сверху для вероятности

Введем в рассмотрение производящую функцию моментов пары случайных величин

где

Из формулы (81) находим

Из последнего неравенства следует нужный нам результат:

где

Применим полученный результат к случайным величинам

и

распределение которых определяется условием

здесь вообще говоря, произвольное распределение, так что

При таком определении случайных величин формула (82) примет вид

(кликните для просмотра скана)