MIT
100
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)
lIf E[X] ³ 4(log n)/e2, “tight
concentration”
»Deviation
by e probability < 1 / n
lNo one variable
is a big part of E[X]