| Proof of Sampling |
|
|
|
|
|
|
|
|
|
|
|
|
| l | Sampled with
probability r /c, |
||||||||||
| » | a cut of value ac has mean ar |
||||||||||
| » | [Chernoff]:
deviates from expected size by |
||||||||||
| more than e with probability at most n-3a |
|||||||||||
| l | At most
n2a cuts have value ac |
||||||||||
| l | Pr[any
cut of value ac deviates] = O(n-a) |
||||||||||
| l | Sum over all a ³ 1 |
||||||||||
