# Upper bound derivation of expected time for finding a large cut

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

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.$$