Understanding the probability of obtaining a cut of size $m/2$

Question

In the maximum cut problem, we want to maximize the number of edges with distinctly colored endpoints by coloring vertices with 2 colors, say red and blue. By flipping a fair coin for each vertex, we can show that the 2-coloring cuts at least $m/2$ edges, where $m$ is the number of edges in the graph.

Now, I'm reading these notes (Section 11.2.1, page 223) on maximum cut. In particular, I'm interested in the probability that the described coin flipping procedure gives us a cut with at least $m/2$ edges cut.

The analysis is given on page 223, where $p$ is the probability that $X \geq m/2$, where $X$ is a random variable for the number of edges cut. I have a hard time understanding how $E[X]$ can be written in the way it is written (both the claimed equality, and the inequality that follows): what is the justification for writing this (ultimately) as $(1-p)\frac{m-1}{2} + pm$?

(Another example is here on the slide titled "Example 1: Large Cut (4)", where my question is exactly "why??" shown on the slide as well).

Answer 1

The first form is simply $$ E(X)=E(X\mid X<m/2)P(X<m/2) + E(X\mid X\ge m/2)P(X\ge m/2). $$ For the second form, if you know that $X$ is strictly less than $m/2$, then the largest $X$ can be is $(m-1)/2$ (reason: remember $X$ is an integer; now consider the cases $m$ is even, and $m$ is odd); and if you know that $X\ge m/2$, then for sure $X$ is less than or equal to $m$ (a very coarse upper bound, true under any condition).

Answer 2

Going by the example of the slides, the equality is just written out by the definition of expected value. It is broken down into two parts (either you end up with a cut with value less than $m/2$, or at least $m/2$). Then, for the inequality, we (crudely) bound the quantities. Here, by definition, $p$ is the probability that $X \geq m/2$. Thus, the first sum is bounded by $(1-p) (m/2-1)$ since the largest value of $X$ one can obtain is $m/2-1$. Similarly, the second sum is bounded by $pm$, because $m$ is the maximum value for the cut obtainable.