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 &amp; 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 &lt; m/2 -1$, $\Pr(X=i) \leq \Pr(X &lt; 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?
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.
$$