Введение в современную криптографию


ПРЕДПОЛОЖЕНИЕ А7 (граница объединения)



Pdf көрінісі
бет228/249
Дата14.06.2023
өлшемі6.4 Mb.
#475029
1   ...   224   225   226   227   228   229   230   231   ...   249
Криптография Катц

ПРЕДПОЛОЖЕНИЕ А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 известно мало.


Достарыңызбен бөлісу:
1   ...   224   225   226   227   228   229   230   231   ...   249




©dereksiz.org 2024
әкімшілігінің қараңыз

    Басты бет