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