MIT
101
Application
lLet Xi=1
if trial i is a failure, else 0
lLet X = X1 + … + Xt
lThen E[X] = t · FAIL(p)
lChernoff says X
within relative e of E[X] with probability 1-exp(e2 t FAIL(p)/4)
lSo choose t
to cancel other terms
»“High
probability” t = O(log n / e2FAIL(p))
»Deviation
by e with probability < 1
/ n