MIT
99
Monte Carlo Simulation
lFlip
a coin for each edge, test graph
lk failures in t
trials Ž FAIL(p) » k/t
lE[k/t] = FAIL(p)
lHow
many trials needed for confidence?
»“bad
luck” on trials can yield bad estimate
»clearly
need at least 1/FAIL(p)
lChernoff bound: O*(1/e2FAIL(p)) suffice to
give probable accuracy within e
»Time
O*(m/e2FAIL(p))