MIT
102
For network reliability
lRandom
edge failures
»Estimate
FAIL(p) = Pr[graph disconnects]
lNaï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