| For network reliability |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Random edge
failures |
||||||||||
| » | Estimate FAIL(p) = Pr[graph disconnects] |
||||||||||
| l | Naïve Monte Carlo
simulation |
||||||||||
| » | Chernoff
bound---“tight concentration” |
||||||||||
| Pr[ |X-E[X]|
£ e E[X] ] < exp(-e2E[X] / 4) |
|||||||||||
| » | O(log n / e2FAIL(p)) trials expect O(log n / e2) |
||||||||||
| network
failures---sufficient for Chernoff |
|||||||||||
| » | So
estimate within e in O*(m/e2FAIL(p)) time |
||||||||||
