3.5. Граница Чернова и лемма Неймана — Пирсона

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

Теорема 3.6.1 (Шеннон, Галлагер и Берлекэмп [1967]). Нртт произвольные распределения вероятностей (плотности вероятностей) на -мерном пространстве наблюдений и пусть два его непересекающихся подмножества, а и их соответствующие дополнения. Допустим, что существует хотя бы одно такое, что Тогда для любого справедливо по крайней мере одно из следующих неравенств:

где

— неположительная выпуклая функция на интервале Более того, если выбрать

то одновременно справедливы обе следующие верхние границы

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

Рис. 3.9. Типичная функция и соотношение между показателями

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

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

правая часть которого растет линейно с ростом Поэтому при квадратные корни в показателях правых частей соотношений (3.5.1) и (3.5.2) становятся асимптотически бесконечно малыми по сравнению с остальными членами показателей. Следовательно, отбросив эти члены, вместе с асимптотически еще менее важным множителем 1/4, мы обнаружим, что альтернативные нижние оценки совпадут с верхними. Тогда, как это показано на рис. 3.9, прямая, касательная к в некоторой точке пересечет вертикальные прямые при отрицательных значениях равных обоим показателям. Из формулировки теоремы следует также, что, зафиксировав показатель, и, следовательно, асимптотическое значение равным где мы можем быть уверены, что показателем будет следовательно, меньшего (более отрицательного) показателя для не существует. Меньшее значение показателя (или у потребует смещения касательной на «функциональных качелях», что приведет к увеличению второго показателя. Должно быть ясно, что теорема по существу эквивалентна лемме Неймана-Пирсона, хотя и дает больше информации, чем ее обычная форма. Кроме того, подмножества, на которых обе верхние оценки асимптотически совпадают с нижними, и, следовательно, лучшие из возможных подмножеств задаются соотношениями (3.5.4). Но они соответствуют оптимальному по лемме Неймана — Пирсона правилу отношения правдоподобий с порогом который равен наклону касательной на рис. 3.9.

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

Тогда неравенства (3.5.5) и (3.5.6) дадут совпадающие верхние границы, а (3.5.1) и (3.5.2) — асимптотически совпадающие нижние границы. Следовательно, если где то

где при Из рис. 3.9 ясно, что это соответствует случаю, когда прямая касательна к в точке минимума.

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

Введем логарифмическое отношение правдоподобия

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

Когда перекашивающая переменная стремится к 0 или стремится к или к соответственно. Если мы примем теперь за случайный вектор с распределением вероятностей (плотностью) то из соотношений (3.5.9) — (3.5.12) ясно, что случайная величина имеет среднее и дисперсию следовательно, Больше того, из (3.5.3) вытекает, что переходит в равенство тогда и только тогда, когда для каждого Следовательно, представляет собой неположительную выпуклую функцию на указанном интервале.

Сравнив между собой соотношения (3.5.3), (3.5.11) и (3.5.12), легко увидим, что

Теперь мы можем получить верхние границы (3.5.5) и (3.5.6). Выберем решающие области в соответствии с (3.5.4), т. е. в соответствии с решающим правилом отношения правдоподобия с

порогом Воспользовавшись (3.5.11), их можно выразить в виде

откуда следует, что

и

Следовательно, из (3.5.13) и (3.5.14) имеем

а поскольку вероятность (плотность), то суммы (интегралы) в (3.5.18) и (3.5.19) ограничены единицей, что и доказывает справедливость неравенств (3.5.5) и (3.5.6).

Теперь докажем справедливость нижних границ (3.5.1) и (3.5.2) для произвольных непересекающихся решающих областей. Начнем с того, что введем множество

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

где обозначают среднее и дисперсию относительно Поэтому

и мы можем оценить снизу суммируя по меньшим множествам в каждом случае, что дает

Но для любого из (3.5.20) следует, что

поэтому для любого из (3.5.13), (3.5.14) и (3.5.24) имеем

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

И, наконец, поскольку и не пересекаются, то

Отсюда вследствие (3.5.21) получаем

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

Объединяя неравенства (3.5.27) — (3.5.30), получим нижние границы (3.5.1) и (3.5.2), что и заканчивает доказательство теоремы

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

и

где распределение вероятностей (плотность), общее для всех N случайных величин. Введем фиктивное распределение (плотность)

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

Следовательно, (3.5.4) сведется к

где, как это следует из (3.5.31) и (3.5.33),

Следовательно, положив

получим из (3.5.36) некоторую верхнюю границу хвоста распределения

где Это также и граница Чернова, ее, как можно было предполагать, нетрудно вывести непосредственно, не обращаясь к приведенной выше теореме (см. задачи 2.10 и 3.18). Рассуждая так же, как при доказательстве теоремы, можно показать, что граница (3.5.38) асимптотически: точна (Галлагер [1968]).