MIT
46
Proof of Sampling
lSampled
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
lAt
most n2a cuts have value ac
lPr[any
cut of value ac deviates] = O(n-a)
lSum
over all a ³ 1