Введение в современную криптографию
ПРЕДПОЛОЖЕНИЕ А7 (граница объединения)
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
- Бұл бет үшін навигация:
- ТЕОРЕМА A.8 (Теорема Байеса)
- ПРЕДПОЛОЖЕНИЕ А.9 *Полезные вероятностные границы
| ПРЕДПОЛОЖЕНИЕ А7 (граница объединения)
Повторное применение границы объединения для любых событий E1, . . . , Ek дает Условная вероятность E1 с учетом E2, обозначенная Pr[E1 | E2], определяется как пока Pr[E2] ƒ= 0. (Если Pr[E2] = 0, то Pr[E1 | E2] не определено). Это представ- ляет вероятность того, что событие E1 происходит с учетом того, что событие E2 произошло. Непосредственно из определения следует, что Pr[E1 ^ E2] = Pr[E1 | E2] • Pr[E2] ; равенство справедливо, если Pr[E2] = 0 до тех пор, пока мы интерпретируем умножение на 0 с правой стороны обычным образом. Теперь можно легко вывести теорему Байеса. ТЕОРЕМА A.8 (Теорема Байеса) Если Pr[E2] ƒ= 0, то 312 ДОКАЗАТЕЛЬСТВО Это следует из того, что Пусть n – события, такие что Pr[E1 v• • • v En] = 1 и Pr[Ei ^ Ej ] = 0 для всех i ƒ= j. То есть {Ei} – разбиение пространства всех возможных событий, так что с вероятностью 1 одно из событий Ei, точно происходит. Тогда для любого F Особый случай, когда n = 2 и E2 = E¯1, давая Pr[F]=Pr[F^E1]+Pr[F^E¯1] = Pr[F | E1] • Pr[E1] + Pr[F | E¯1] • Pr[E¯1]. Принимая F=E1v E2, получим более строгую версию границы объединения: Pr[E1 v E2] = Pr[E1 v E2 | E1] • Pr[E1] + Pr[E1 v E2 | E¯1] • Pr[E¯1] ≤ Pr[E1] + Pr[E2|E¯1]. Распространив это на события E1, . . . , En, получим ПРЕДПОЛОЖЕНИЕ А.9 *Полезные вероятностные границы Рассмотрим некоторые термины и положения вероятностных границ, которые являются стандартными, но могут не встречаться в базовом курсе дискретной ма- тематики. Приведенный здесь материал используется только в разделе 7.3. Случайная (дискретная, действительная) величина X является переменной, значение которой присваивается вероятностно из некоторого конечного множе- ства S действительных чисел. X – неотрицательная величина, если не принимает отрицательных значений; это 0/1-случайная переменная, если S = {0, 1}. 0/1-слу- чайные переменные X1, . . . , Xk являются независимыми, если для всех b1, . . . , bk справедливо, что Pr[X1 = b1 ^ • • • ^ Xk = bk] = Qk Pr[Xi = bi]. Обозначим как Exp[X] математическое ожидание случайной величины X; если X принимает в множестве S, то Exp[X]x ∑s∈S s • Pr[X = s]. Одним из наиболее важ- ных фактов является то, что математическое ожидание линейно ; для случайных величин X1, . . . , Xk (с произвольными зависимостями) имеем Exp[∑i Xi] = ∑i Exp[Xi]. Если X1, X2 – независимые, то Exp[Xi • Xj] = Exp[Xi] • Exp[Xj ]. Неравенство Маркова полезно, когда о X известно мало. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|