| Chernoff Bound |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Random
variables Xi
` [0,1] |
||||||||||
| l | Sum X = å Xi |
||||||||||
| l | Bound deviation
from expectation |
||||||||||
| Pr[ |X-E[X]| m e E[X] ] <
exp(-e2E[X]/4) |
|||||||||||
| l | If E[X] m 4(log n)/e2, “tight concentration” |
||||||||||
| » | Deviation by e probability < 1 / n |
||||||||||
| l | No one variable
is a big part of E[X] |
||||||||||