Given an undirected graph $G$ with $n$ vertices and $m$ edges, we build a cut as following. Initially sets (of vertices) $A$ and $B$ are empty. For each vertex $v$ we flip a fair coin and according to outcome we put $v$ either in $A$ or $B$.

Let $X$ be a r.v. denoting the cut size, i.e. the number of edges between sets $A$ and $B$. A simple calculation produces $$E[X] = \frac{m}{2}$$ (see Probability and Computing by M.Mitzenmacher & E. Upfal, pg 130).

Now, let $p = \Pr\left(X \geq \frac{m}{2}\right)$. Then $$ \frac{m}{2} = E[X] = \sum_{i \leq m/2 -1}{i\Pr(X=i)} + \sum_{i \geq m/2}{i\Pr(X=i)}$$ $$ \leq (1-p)\left(\frac{m}{2}-1 \right) + pm.$$

I understand that for $i < m/2 -1$, $\Pr(X=i) \leq \Pr(X < m/2)$ and for $i \geq m/2$, $\Pr(X=i) \leq \Pr(X \geq m/2)$, but I don't understand how the last upper bound is derived.

Can anyone give me a hint or explain the derivation?


1 Answer 1


We can upper bound the first summand by $$ \sum_{i \leq m/2-1} i \Pr(X=i) \leq \sum_{i \leq m/2-1} (m/2-1) Pr(X=i) = (m/2-1) \sum_{i \leq m/2-1} Pr(X=i) = (m/2-1) Pr(X \leq m/2-1) = (1-Pr(X \geq m/2))(m/2-1) = (1-p)(m/2-1). $$ Similarly, we can upper bound the second summand by $$ \sum_{i \geq m/2} i \Pr(X=i) \leq \sum_{i \geq m/2} m Pr(X=i) = m \sum_{i \geq m/2} Pr(X=i) = m Pr(X \geq m/2) = pm. $$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.