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