 Conditional expectations for maximum cut

Let $G=(V,E)$ be a finite undirected simple graph, with $n=|V|$ vertices and $m=|E|$ edges. A cut of a graph assigns each vertex a label zero or one; an edge crosses precisely when its endpoints have different labels. Its size is the number of crossing edges. A maximum cut maximizes that size.

For the analysis, assign independent fair bits $X_v$ to the vertices. For each edge $uv$, the indicator random variable $I_{uv}=1_{\{X_u\ne X_v\}}$ has expected value $1/2$: exactly two of the four equally likely endpoint assignments cross. Thus linearity of expectation gives the random cut lower bound:Linearity of expectation does not require the indicator random variables to be independent. What matters here is the stipulated distribution of the endpoint bits.