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 известно мало.
Достарыңызбен бөлісу: