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