Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Prob["ycnex"] = р, РгоЬ["неудача"] = 1 — р.
Тогда
Probf'fc успехов в п испытаниях"] = (^Рк (1 — Р)п~к > (3.5.1)
где (^) обозначает число сочетаний из п элементов по к.
Докажем справедливость равенства (3.5.1). Во-первых, количество вариантов, в которых может произойти событие "среди п испытаний зафиксировано к "успехов" и п — к "неудач", равно числу сочетаний из п элементов по к, т.е. (?). Во-вторых, каждой точке поля вероятностей соответствует к "успехов" и п — к "неудач", поэтому вероятность извлечь такую точку равна р*(1 — р)п~к.
Если случайная величина ?п принимает значения 0,1,..., п, и для величины р G (0,1) выполняется условие
Probfc, = к] = Qp* (1 - р)п-К (к = 0,1,..., п),
то говорят, что величина fn имеет биномиальное распределение (binomial distribution). Сравнивая это выражение с формулой (3.5.1), приходим к выводу, что испытания Бернулли подчиняются биномиальному распределению. Обозначим через Ь(к; п, р) биномиальный член (binomial term), соответствующий значени-ям к = 0,1,..., п и 0 < р < 1.
Пример 3.8. Рассмотрим следующие задачи.
1. Предположим, что в ходе эксперимента идеальная монета подбрасывается 10 раз. Чему равна вероятность того, что орел не выпадет ни разу или орел выпадет сколько-то раз (один, два,... или 10)?
2. Чему равна вероятность события "орел выпадет пять раз"?
3. Чему равна вероятность события "орел выпадет не более пяти раз"? Поскольку событие, описанное в задаче 1, происходит всегда, его вероятность
равна единице. Действительно, применяя второе правило сложения вероятностей,
к fi \n—fc
102
Часть II. Математические основы
имеем следующее.
ю ю
РгоЬ |^){"Орел выпадает г раз"} = Prob ["Орел выпадает г раз"] =
i=l i=0
Ю /1Г>\ /, \ 10-i
10
10
= (1 + 1Г(|) = 1.
Решая задачу 2, получаем такой результат.
5 У \ 2 ) = Ю24 ~ ®?46.
При решении задачи 3 мы должны просуммировать вероятности всех событий, в которых орел выпадает не более пяти раз.
Prob (J {"Орел выпадает г раз из 10"} = (^\ ^ (10) ^ °>623- ч i=i ^ ' i=o ^г ' а
На рис. 3.1 изображен график биномиального распределения для р = 0,5 и п = 10, использованного при анализе примера 3.8.
Следует обратить особое внимание на разницу между задачами 3.8.2 и 3.8.3.' Вероятность события, указанного в задаче 3.8.2, равна площади среднего прямо-1 угольника, изображенного на рис. 3.1, а вероятность события, описанного в зада-Л че 3.8.3, равна площади первых шести прямоугольников.
В приложениях биномиальных распределений (см. разделы 4.4.1, 4.4.5.1 и 18.5.1) вероятность обнаружить ровно г "успехов" (как в примере 3.8.2) вы-1 зывает меньше интереса, чем вероятность обнаружить не менее г "успехов" (как-в примере 3.8.3). Более того, сумма нескольких членов может быть более значимой, чем суммы других членов. Перейдем теперь к исследованию "значимых'! и "незначимых" сумм в биномиальном распределении.
3.5.2.1 Центральный член и хвосты
Рассматривая последовательные биномиальные члены, приходим к следующей формуле.
Ь(к;п,р) _ (п - к + 1)р _ i [ (п + 1)р - к
Ь(к - 1; п, р) к(1-р) к(1- р)
Второе слагаемое в правой части является положительным при к < [п + 1)р и отрицательным при к > (п + 1)р. Итак, дробь (3.5.2) больше единицы при!
Глава 3. Теория вероятностей и теория информации
103
Ь(5; 10,0.5) -0.246
у = Ь(х; 10,0.5)
10
Рис. 3.1. Биномиальное распределение
к < (п + 1)р и меньше единицы при к > (п + 1)р. Следовательно, с увеличением числа к величина Ь{к;п,р) возрастает, если к < {п + 1)р, и уменьшается, если к > (п + 1)р. Значит, биномиальный член Ь(к;п,р) достигает максимума в точке к = [(n + l)pj. Биномиальный член
Ь([(п+1)р\;п,р) (3.5.3)
называется центральным (central term). Поскольку точка [{п+ 1)р\ является точкой максимума биномиального члена, она представляет собой наиболее вероятное количество успехов. Обратите внимание на то, что, если число (п + 1)р является целым, дробь (3.5.2) равна единице, и, следовательно, в данном случае существуют два центральных биномиальных члена Ь((п + 1)р — 1;п,р) и 6((п + 1)р; п,р).
Допустим, что г > [п + 1)р, т.е. точка г расположена правее точки, соответствующей наиболее вероятному количеству успехов. Как известно, величина Ь(к;п,р) убывает при всех к > г. Можно оценить скорость убывания этой величины, заменив число к числом г в правой части равенства (3.5.2). Это приводит нас к следующему неравенству.
Ь(к; п, р)<Ь(к-1-п,р)з, где s = (те + г-^)Р < 1. (3.5.4)
г{1-р)
В частности,
Ь(к;п,р) < b(r;n,p)s.
104
Часть II. Математические основы
Обратите внимание на то, что оценка (3.5.4) выполняется для всех чисел к = г + + 1, г + 2,..., п. Следовательно,
Ь{т + г;п,р) < Ь(г;п,р)бг для г = 1,2,... (3.5.5)
Допустим теперь, что г > пр, и вычислим верхнюю границу вероятности обнаружить не менее г успехов.
п п—г
Prob[?n ^ г] = ^ Ь(к; п,р) = ^ Ъ(г + i; п,р). (3.5.6)
к=т г=0
Из (3.5.5) следует, что
П—Г ОО j
Prob[?n ^ г] < Ь(г; n, р) ^ sl < Ь(г; n, р) ^ sl = Ь(г; п, р) :j—j;-
i=0 i=0
Заменяя параметр s выражением получаем
г(1 - р)
