MIT
36
Analysis: Chernoff Bound
lRandom variables Xi Î [0,1]
lSum X = å Xi
lBound deviation
from expectation
Pr[ |X-E[X]| ³ e E[X] ] <
exp(-e2E[X] / 4)
l“Probably, X Î (1±e) E[X]”
lIf E[X] ³ 4(ln n)/e2, “tight
concentration”
»Deviation
by e probability < 1 / n