ПРЕДПОЛОЖЕНИЕ А.10 (неравенство Маркова)

313
ДОКАЗАТЕЛЬСТВО Допустим, что X принимает значения в множестве S. 
Имеем
Дисперсия X, обозначенная как Var[X], определяет, насколько X отклоняется 
от своего математического ожидания. Имеем Var[X] Exp[(X − Exp[X])2] = 
Exp[X2] − Exp[X]2, и можно легко показать, что Var[aX + b] = a2Var[X]. Для 
0/1-случайной величины Xi, имеем Var[Xi] ≤ 1/4, поскольку в этом случае 
Exp[Xi] = Exp[X2] и, таким образом, Var[Xi] = Exp[Xi](1−Exp[Xi]), которая ста-
новится максимальной при Exp[Xi] = 1 .
ПРЕДПОЛОЖЕНИЕ А.11 (неравенство Чебышева) Пусть X – случайная 
величина и δ > 0. Тогда:
ДОКАЗАТЕЛЬСТВО Определим неотрицательную случайную величину Y 
(X −Exp[X])2 и затем применим неравенство Маркова. Таким образом,
0/1-случайные величины X1, . . . , Xm are pairwise independent, если для каж-
дого i ƒ= j и каждого bi, bj∈{0, 1} справедливо, что
Pr[Xi = bi^Xj = bj ] = Pr[Xi = bi] • Pr[Xj = bj ].
Если X1, . . . , Xm попарно независимы, то 
(Это следует, поскольку Exp[Xi • Xj ] = Exp[Xi] • Exp[Xj] когда i ƒ= j, используя по-
парную независимость). Важное следствие неравенства Чебышева приведено ниже.
СЛЕДСТВИЕ A.12 Пусть X1, . . . , Xm – попарно независимые случайные 
величины с одним и тем же математическим ожиданием µ и дисперсией σ2. 
Тогда для каждого δ > 0,
ДОКАЗАТЕЛЬСТВО При линейности математического ожидания 
неравенство Чебышева для случайной величины. Применяя 
, имеем

314
Из использования попарной независимости следует, что
Неравенство получено комбинацией двух приведенных выше выражений.
Пусть 0/1-случайные величины X1, . . . , Xm, каждая из которых дает оценку 
некоторого фиксированного (неизвестного) бита b. То есть, Pr[Xi = b] ≥ 1/2 + ε 
для всех i, где ε > 0.
Можно оценить b, рассмотрев значение X1; эта оценка будет корректной с 
вероятностью Pr[X1 = b]. Более точную оценку можно получить, рассмотрев 
значения X1, . . . , Xm и взяв значение, которое появляется большую часть вре-
мени. Проанализируем, насколько хорошо это выполняется, когда X1, . . . , Xm 
являются попарно независимыми.

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: