Главная > Теория информаци и связи > Передача информации. Статическая теория связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

8.4. Нижние границы полиномиальных слагаемых

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

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

словами, распределение вероятностей для каждого события а, равно

Опять свяжем с каждым событием случайную величину

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

Снова обозначим через

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

и ее дополнения где — множество последовательностей, для которых Общий метод получения этих нижних границ основан на том, что в правой части выражения (8.81) мы пренебрегаем всеми слагаемыми, кроме наибольшего. Поэтому мы должны предварительно изучить более подробно, чем раньше, структуру полиномиального распределения вероятностей, связанного с ансамблем последовательностей

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

Значение случайной величины для некоторой последовательности равно

а следовательно, зависит только от композиции последовательностей. Число различных последовательностей С одинаковой

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

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

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

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

Доказательство. Правая часть неравенства (8.86) получается подстановкой вместо факториала в числителе равенства (8.84) нижней границы, задаваемой неравенством (7.5), а вместо каждого факториала в знаменателе — верхней границы, также задаваемой неравенством (7.5). Эти подстановки дают

Очевидно, это неравенство все еще останется справедливым, если в знаменатель вместо каждого подставить Кроме того, если все целые отличны от нуля, то неравенство останется справедливым, если вместо каждого в показателе последнего сомножителя в правой части неравенства (8.87) подставить 1. Эти подстановки немедленно дают неравенство (8.86). Если - число целых отличных от нуля, то число факториалов в знаменателе равенства (8.84) равно следовательно, в выражении (8.86) вместо должно быть

подставлено Но так как то выражение (8.86) останется справедливым с независимо от значения Ч. Т. Д.

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

Для этого нам потребуется следующая лемма.

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

и определим

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

и

Доказательство. Определим целых чисел задаваемых неравенствами

Из этого определения следует, что

где положительное целое, не превосходящее Очевидно, соотношения (8.91) и (8.92) будут выполняться, если положить целых равными а остальные целых равными

Значение разности между Двумя частями соотношения (8.88), а именно

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

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

Мы покажем теперь, что величина (8.97) положительна для совокупности целых чисел и отрицательна для совокупности целых чисел

С этой целью заметим, что поскольку целые числа удовлетворяют условию (8.91), то

В силу соотношений (8.98), отсюда следует, что

Далее имеем

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

Для завершения доказательства покажем, что совокупность целых чисел может быть преобразована в совокупность целых чисел последовательными шагами, на одном из которых должна получиться совокупность целых чисел удовлетворяющая неравенствам (8.93) и (8.94). Согласно соотношениям (8.98), является наибольшим значением для которого

Положим и для всех других значений положим Для этой новой совокупности, все еще удовлетворяющей условиям (8.91) и (8.92), значение величины (8.97) меньше ее значения, принимаемого для совокупности на

Наибольшее значение в этой новой совокупности целых чисел, для которых равно Далее увеличим на единицу, а уменьшим на единицу. При этом сумма чисел остается неизменной, а величина (8.97) уменьшится на

Вообще, увеличим целое последовательно на единицу и уменьшим целое на единицу, где наибольшее значение для которых Каждая последующая операция такого типа уменьшает значение (8.97) на величину, меньшую или равную А. В конечном счете совокупность целых чисел будет совпадать с совокупностью

В силу соотношений (8.102) и (8.103), мы можем сделать вывод, что вышеприведенный процесс изменяет значение величины (8.97) от положительного к отрицательному последовательными шагами, величина которых не превышает максимальной разности А, определенной в выражении (8.90). Отсюда следует, что должна существовать совокупность целых чисел удовлетворяющая как условию (8.93), так и (8.94). Ч. Т. Д.

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

среднему значению, задаваемому правой частью соотношения (8.88).

Теорема. Пусть

— среднее значение случайной величины Тогда существует совокупность из целых чисел и некоторое значение индекса такое, что случайная величина, определяемая выражением (8.83), удовлетворяет двум неравенствам

где А задается условием (8.90), а вероятность соответствующей композиции, задаваемой равенством (8.85), удовлетворяет неравенству

Доказательство. Из выражений (8.85) и (8.86) имеем

Мы должны найти верхнюю границу для суммы, стоящей в правой части этого соотношения. Для этой цели положим

Из предыдущей теоремы известно, что существует совокупность из целых чисел для которой выполняются условия (8.107) и (8.108). Эта совокупность целых чисел, так же как и совокупность, полученная увеличением и уменьшением на единицу, удовлетворяет соотношениям (8.91) и (8.92), а потому для них обеих

Далее с помощью равенства (2.91) мы находим, что

С другой стороны, равенство (8.91) означает, что

и, в силу неравенства (8.112), вместо каждого можно под ставить 1. Отсюда следует, что

Подстановка правой части этого неравенства в сумму в неравенстве (8.110) дает соотношение (8.109) для совокупности целых чесел Тот же самый результат получается для целых чисел в силу того, что неравенства (8.112) и (8.114) удовлетворяются также и для второй совокупности. Ч. Т. Д.

<< Предыдущий параграф Следующий параграф >>
Оглавление