 |
 |
23 of 32 |  |
 |
 |
MIT
Proof of Sampling
l
[Chernoff]: When sampled with
probability
9
ln
n / e
2c
, a cut of value ac
(
m =
9
a
ln
n /
e
2
)
deviates by more than
e
with probability n
-³a
l
Saw: At most
n
2
a
cuts have value <ac
l
Pr[any cut of value ac
deviates] = O
(n
-a
)
l
Sum over all
a
> 1