ПРИЛОЖЕНИЕ 6Б

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

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

где

кодовая последовательность, соответствующая узлу По предположению путь соответствует последовательности источника, отличающейся от переданной последовательности в первом подблоке. В ансамбле кодов величины х статистически независимы от величин х из а также статистически независимы друг от друга. Поэтому из также статистически независимые случайные величины. Следует заметить, что так как из те же самые, что из то вообще говоря, не являются статистически независимыми случайными величинами (см. задачу 6.43). Положим при

и при положим Отсюда получим при Пусть

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

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

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

Удобно выбрать используя получаем

где суммирование производится по всем возможным значениям Произведя суммирование отдельно для каждою [как в (5.5.7) — (5.5.10)], получим

Аналогично имеем

Вспоминая что со это выражение приводим

Применяя к сумме по неравенство Коши, получаем

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

Далее следует найти верхнюю границу второго члена в Напомним, что

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

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

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

Положим

Тогда при любом таком, что и при любом и

Применительно к нашему случаю так, что Теперь покажем, что откуда следует согласно что

Аналогично (6Б.12) имеем

На последнем шаге мы воспользовались неравенством Коши аналогично тому, как это сделано в Так как по предположению то справедливо.

Случайная величина а статистически независима от случайной величины следовательно,

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

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

Случайные блуждания и доказательство леммы 6Б.1

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

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

При любом заданном определим перекошенные распределения вероятностей с помощью равенств

Пусть последовательность статистически независимых случайных величин, каждая из которых принимает значения с вероятностями и рассмотрим «перекошенное» случайное блуждание, для которого и

при

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

Заметим, что является вероятностью того, что при перекошенном блуждании первое достижение значения, меньшего или равною и, произойдет в момент Следовательно, является вероятностью того, что при перекошенном случайном блуждании когда-нибудь будет достигнуто значение,

меньшее или равное и. Наконец, при эти вероятности относятси к первоначальному случайному блужданию.

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

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

Рис. 6Б.1. График функции для где принимает как положительные, так и отрицательные значения.

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

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

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

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

Здесь мы хотим использовать этот результат для вывода границы сверху величины

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

то отсюда видно, что при применяя получаем

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

Можно также показать (см. Феллер (1966), т. 2, гл. XII, § 5), что асимптотически при больших и где С не зависит от .