7.1. Биномиальное распределение

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

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

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

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

где

Доказательство. Это неравенство можно получить, аппроксимируя факториалы по формуле Стирлинга [2], которую мы запишем в виде неравенств

где любое натуральное число.

Подставив вместо факториалов в числителе выражение (7.2) их верхнюю границу, задаваемую неравенством (7.5), а в знаменателе — соответствующую нижнюю границу, задаваемую тем же неравенством, мы получаем верхнюю границу в неравенстве (7.3). Имеем

где определено в выражении (7.4). Показатель степени в последнем множителе в правой части неравенства (7.6) отрицателен для любого положительного целого

Таким образом, последний множитель в правой части неравенства (7.6) можно положить равным 1, что и приводит к верхней границе неравенства (7.3).

Нижняя граница неравенства (7.3) получается аналогично заменой факториала в числителе выражения (7.2) меньшей из двух нижних границ в неравенстве (7.5) и двух факториалов в знаменателе выражения (7.2) соответствующей верхней границей из неравенства (7.5). Эти подстановки немедленно приводят к нижней границе в неравенстве (7.3). Ч. Т. Д.

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

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

где любое натуральное число, меньшее

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

Полагая

получаем из выражения (7.9), что

и, следовательно,

Далее,

Подставляя правую часть этого выражения в правую часть выражения (7.12), получаем верхнюю границу в соотношении (7.8).

Нижнюю границу в соотношении (7.8) получим, замечая, что все члены суммы положительны и что как показывает неравенство (7.11), наибольший член этой суммы. Ч. Т. Д.

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

Вероятность появления какой-либо последовательности, содержащей точно событий событий В, равна

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

т. е. равна числу различных последовательностей, содержащих точно событий событий В [см. тождество (7.2)], умноженному на вероятность появления каждой из таких последовательностей [см. равенство (7.15)]. Вероятность, заданная соотношением (7.16), является членом биномиального распределения вероятностей, и характер ее зависимости от показан на рис. 7.2 для

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

Рис. 7.2. Графики нормированных биномнальных коэффициентов и биномиального распределения для

Эта вероятность в соответствии с выражением (7.16) равна

Желательно оценить эти вероятности с помощью более удобных функций от Для этой цели нам потребуется следующая теорема.

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

где

Доказательство. Вывод этого неравенства весьма сходен с выводом неравенства (7.8). Для отношения последовательных слагаемых суммы в неравенстве (7.18) мы получаем

Затем полагаем

Из выражения (7.20) следует, что

так что

Кроме того,

Подставляя правую часть этой формулы в правую часть формулы (7.23), получаем верхнюю границу неравенства (7.18). Его нижнюю границу получим, замечая, что все члены суммы положительны и что, как показывают неравенства (7.22), наибольший из них. Ч. Т. Д.

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

Теорема. Пусть число различных последовательностей, состоящих из событий событий В, для которых и биномиальный член, определенный в тождестве (7.16); обозначим

Тогда

Доказательство. Верхнюю границу в неравенстве (7.26) можно вывести, следуя тому же методу, который применялся при выводе верхних границ выражений (7.8) и (7.18). Для того чтобы получить выражение для отношения последовательных слагаемых в выражении (7.26), мы заметим, что в силу формулы (7.2).

Тогда мы находим, что отношение последовательных слагаемых

Пусть

где

Можно легко проверить, что параметр а, определенный в формуле (7.30), становится равным единице, когда равно значению данному в выражении (7.25). Тогда, как следует из формулы (7.29),

так что

Далее,

Подставляя правую часть этой формулы в правую часть неравенства (7.33), получаем верхнюю границу соотношения (7.26). Нижняя граница в нем получается, если заметить, что все члены суммы положительны и что, как видно из неравенства (7.32), наибольший из них.

При выводе верхней границы в неравенстве (7.27) используется специальный прием, называемый методом «перекошенных распределений вероятностей», который в общем виде будет рассмотрен в разд. 8.2. Верхняя граница в неравенстве (7.26) справедлива только для поскольку достигает максимального значения при несколько большем чем Отсюда следует, что для рост сумм в выражении (7.26) по медленней линейного.

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

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

В самом деле,

Мы замечаем, кроме того, что

так что

Отсюда следует, что

что совпадает с выражением (7.27).

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