5.4. ОБОБЩЕННОЕ НЕРАВЕНСТВО ЧЕБЫШЕВА И ГРАНИЦА ЧЕРНОВА

В этом параграфе результаты § 5.3 будут выведены вновь в более общем виде, что даст тем самым дополнительное понимание использованных там методов. При передаче сообщения 1 и декодировании по максимуму правдоподобия для двух кодовых слов ошибка происходит, если Другими словами, ошибка происходит, если логарифм отношения правдоподобия удовлетворяет условию

Для каналов без памяти согласно можно представить в виде суммы N слагаемых

где

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

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

теории вероятности, и поэтому она заслуживает более общего рассмотрения.

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

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

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

Чтобы показать на примере, насколько малоэффективно это неравенство, предположим, что рост случайно выбранного человека. Если см, то (5.4.5) утверждает, что вероятность того, что выбранный человек окажется выше чем см, не больше 1/2, а вероятностьтого, что выбранный человек окажется выше чем см не больше 1/10.

Предположим теперь, что является произвольной случайной величиной со средним значением и дисперсией Если положить в то получим

Обозначая это неравенство можно переписать в виде, в котором обычно представляется неравенство Чебышева,

Можно получить большое число других неравенств, называемых обобщенными неравенствами Чебышева, если положить равным другим функциям от Здесь будет особенно интересно неравенство, которое обычно называется границей Чернова; оно получается, если положить где произвольное действительное число. В результате получим

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

Пусть в (5.4.9) равно где А — произвольное действительное число. При неравенство эквивалентно неравенству так что (5.4.9) принимает вид

Аналогично, если то неравенство эквивалентно неравенству что дает

Зависимость функции от изображена на рис. 5.4.1. Она принимает значение 1 при и ее первая производная при равна

Рис. 5.4.1. Вид границы Чернова.

Вторая производная всегда положительна, что следует из равенства Поэтому, если то граница, устанавливаемая (5.4.12), больше чем 1 при всех следовательно, является бесполезной. Аналогично, если то бесполезной является граница в (5.4.11). Другими словами, (5.4.11) и (5.4.12) могут быть использованы только при оценивании «хвостов» распределения.

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

Для большинства применений более удобно оставить свободным параметром, чем считать, что является решением (5.4.13).

Границы (5.4.11) и (5.4.12) полезны в основном тогда, когда является суммой статистически независимых случайных величин:

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

Так как статистически независимы, то математическое ожидание произведения равно произведению математических ожиданий, и, таким образом,

где производящая функция моментов случайной величины Подставляя (5.4.14) в (5.4.11) и (5.4.12), получаем

Неравенство (5.4.15) можно теперь применить к оценке вероятности ошибки для кода с двумя кодовыми словами [см. (5.4.4)]. В этом случае задается равенством (5.4.3) и вероятностная мера берется при условии, что было передано сообщение 1. Имеем

Это в точности совпадает с результатом (5.3.6).

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

Эти функции связаны с помощью соотношения (5.4.14) следующим образом:

Точно так же из (5.4.13) следует, что которое оптимизирует границу, задается с помощью производной от следующим образом:

Подставляя (5.4.19) и (5.4.20) в (5.4.15) и (5.4.16), получаем параметрические границы

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

для нерешетчатой случайной величины и

для решетчатой случайной величины.

В этих выражениях функции о стремятся к нулю быстрее, чем с ростом При любом заданном функцией о можно пренебречь при достаточно больших хотя, когда стремится к 0, это требуемое N становится все больше и больше. является расстоянием между соседними выборочными значениями (см. приложение а А равно расстоянию между и ближайшим большим последовательным выборочным значением При те же самые выражения справедливы для

Рис. 5.4.2.

Эти выражения остаются также в силе для непрерывных случайных величин если для в некоторой окрестности нуля.

Для различных биномиальных распределений на рис. 5.4.2 проведено сравнение асимптотического выражения, границы Чернова, истинного значения и гауссовского приближения. Можно заметить, что граница Чернова и асимптотические выражения в (5.4.24) являются плохими приближениями при А, близких к (при малых но что при больших А гауссовское приближение является плохим, а граница Чернова и асимптотическое выражение — хорошими.