Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Prob[?n ^ г] < Ь(г;п,р)
г — (п + 1)р
Учитывая, что между центральным биномиальным членом и величиной Ь(г; п, р) расположены только г — (п + 1)р биномиальных членов, превышающих число Ъ{т; п,р), причем их сумма не превышает единицы, получаем неравенство
b(r;n,p) < (г — (п + 1)р)-1-
В итоге имеем следующую оценку.
К1 ~ Р) (г — (п + 1)р)
Prob[?n ^ г] ^--\ \\ х2 для г > (п + 1)р. (3.5.7)
Левая часть неравенства (3.5.7) называется правым хвостом (right tail) биномиального распределения. Легко убедиться, что если величина г немного отличается от центральной точки (п + 1)р, то знаменатель дроби в соотношении (3.5.7) не равен нулю, и весь правый хвост ограничен величиной порядка (пр)-1. Следовательно, правый хвост является малой величиной и стремится к нулю при увеличении числа п.
Аналогично можно вывести оценку для левого хвоста (left tail):
Prob[?n ^ г] ^ -для г < [п + 1)р. (3.5.8)
(n + 1 — г)р ((п + 1)р — г)
Читатель может самостоятельно выполнить это задание (упражнение 3.7).
Глава 3. Теория вероятностей и теория информации
105
На первый взгляд, из неравенств (3.5.7) и (3.5.8) следует, что два хвоста биномиального распределения ограничены величинами, имеющими порядок Однако следует отметить, что из неравенств (3.5.7) и (3.5.8) можно получить лишь верхние оценки. На самом деле хвост стремится к нулю намного быстрее, чем А. Этот факт иллюстрируется следующим примером (см. также доказательство стойкости и полноты протокола 18.4 в разделе 18.5.1.1).
Пример 3.9. Пусть р = 0,5. Вычислим левые хвосты биномиального распределения, ограниченные точкой г = п{р — 0,01), для разных чисел п.
1. Для п = 1 ООО соответствующий левый хвост равен
Prob[f < 490] « 0,25333.
2. Для п = 10 000 соответствующий левый хвост равен
Prob[f < 4 900] и 0,02221.
3. Для п = 100 000 соответствующий левый хвост равен
Prob[f < 49 000] и 1,24241 х Ю-10.
Сравнивая эти результаты, легко убедиться, что хвост уменьшается до нуля гораздо быстрее, чем -.
Поскольку р = 0,5, распределение плотности вероятности является симметричным (см. рис. 3.1). У симметричного распределения правый и левый хвосты совпадают, если они содержат одинаковое количество членов. Следовательно, в задаче 3.9.3 сумма двух хвостов, состоящих из 98 000 членов (т.е. 98% всех членов), практически равна нулю, а сумма членов, соответствующих наиболее вероятному количеству успехов (т.е. 2% всех членов в окрестности центрального члена), практически равна единице. а
3.5.3 Закон больших чисел
Напомним определение 3.2. Оно утверждает, что если в результате п одинаковых испытаний событие Е происходит р раз, причем эта частота является устойчивой, а число п достаточно велико, то величина ^ называется вероятностью события Е.
Допустим, что в схеме испытаний Бернулли вероятность успеха равна р, а случайная величина представляет собой количество "успехов" среди п испытаний. Тогда ^ равна среднему количеству "успехов" среди п испытаний. В соответствии с определением 3.2 величина ^ должна быть близкой к числу р.
106
Часть II. Математические основы
Рассмотрим, например, вероятность того, что величина превосходит число р + а для любого а > 0 (т.е. число а является произвольно малым, но фиксированным). Очевидно, что эта вероятность равна следующей величине.
п
Prob[?n > п{р + а)] = ]Г Ъ(г; п, р).
i=n(p+a)+l
С учетом оценки (3.5.7) получаем, что
Prob[?n > п(р + а)] < —. (3.5.9)
па
Таким образом,
Prob[?n > п{р + а)] -> 0(п -> со). (3.5.10)
Аналогично можно доказать, что
Prob[fn < п(р — а)] —» 0(п —» со).
Отсюда следует закон больших чисел (law of large numbers):
lim Prob
n—>oo
--p < a\ =
i I J
1.
Эта форма закона больших чисел называется также теоремой Бернулли (Bernoulli's theorem). Теперь совершенно ясно, что определение 3.2 является следствием закона больших чисел. Однако мы сформулировали его в виде определения, поскольку этот закон имеет интуитивный характер.
3.6 Парадокс дней рождений
Рассмотрим следующую задачу для произвольной функции / : X t—> У, где Y — множество, состоящее из п элементов.
Найти величину к для оценки вероятности е (т.е. 0 < е < 1), такую что для к попарно разных элементов х^,х2, ...,Хк€ иХ набор, состоящий из к значений функции f(xi),f(x2), - • • ,f(xk), удовлетворяет неравенство
Prob[/(a;i) = f(xj)] ^ е для некоторых г ф j.
Иначе говоря, при к вычислениях функции коллизия возникает с вероятностью не меньше е.
Глава 3. Теория вероятностей и теория информации
107
В этой задаче требуется найти число к, которое удовлетворяет некоторой оценке вероятности снизу для любой функции. Предполагается лишь, что функция обладает так называемым свойством случайности: такие функции отображают равномерно распределенные числа из множества X в равномерно распределенные числа из множества Y. Очевидно, что только такая функция позволяет увеличить число к при заданной оценке вероятности так, чтобы эти условия выполнялись для любой функции при той же оценке вероятности. Следовательно, необходимо, чтобы #Х > #Y. В противном случае могут существовать функции, у которых коллизии вообще не возникают.
