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