ПРИЛОЖЕНИЕ 8А. ГРАНИЦЫ ЧЕРНОВА ДЛЯ РАСПРЕДЕЛЕНИЙ ПОГРЕШНОСТИ

8А.1. Симметричные источники

Скорость как функция погрешности симметричного источника, определяемого из условий задается в параметрической форме соотношениями (7.6.69) и (7.6.70), где

Оценим величину где имеет равномерное распределение вероятностей Пусть означает математическое ожидание по Тогда для любого находим следующую границу Чернова:

Полагая где удовлетворяет (7.6.69) и (7.6.70), получаем границу

Чтобы вывести нижнюю границу для для любого положим

и заметим, что

Здесь, поскольку

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

Если задано то перекошенная вероятность для

В перекошенном распределении

Отсюда при любом заданном получаем границу

По неравенству Чебышева (см. задачу 1.4)

так как случайная величина в перекошенном распределении имеет среднее и дисперсию Тогда соотношение преобразуется к виду

Если мало настолько, что то можно выбрать так, чтобы удовлетворялось уравнение

Пусть удовлетворяет (7.6.69), так что Тогда

Так как

поэтому, вычитая из обеих частей этого неравен ства, находим

где использовались обозначения (7.6.70). Подставляя олучаем исксмую границу

8А.2. Двоичный композиционный класс

Пусть задан алфавит источника алфавит представления и мера погрешности типа ошибки в символе Как и к (8.5.23) — (8.5.25), для заданных целых N и определим

Возьмем любое зафиксируем скорость выберем , удовлетворяющее (8.5.27). Предположим, целое таково, что существует для которого согласно (8.5.35)

Ищем для выражения, аналогичные предполагая, что я имеет распределение N

где

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

Пусть означает математическое ожидание Тогда для любого получим границу Чернова

Выберем то значение при котором удовлетворяются параметрические уравнения для Тогда из (7.6.58) находим

Следовательно,

Прежде чем вывести нижние границы, для любых определим функцию

Ее производные по равны

Заметим, что

Для заданного определим перекошенное распределение вероятностей на как

Для этого перекошенного распределения

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

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

откуда находим

Выберем так, чтобы Тогда, как и в

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

Но из следует

так как Тогда граница принимает вид

Задачи

(см. скан)

(см. скан)

(см. скан)

(см. скан)

(см. скан)