The probabilistic method Let $G = (V,E) $ be a finite graph. For any set $ W $ of vertices and any edge $e \in E $, define the indicator function $$ I_W(e) =  \begin{cases}
1 ,
&\ e \textrm{ connects }  W \textrm{ and } W^c \\ \ \\ 0,&\ \textrm{otherwise} \\ \  \\ \end{cases}  $$
Set $ N_W := \sum_{e \in E} I_W(e)$. Show that there exists $ W \subset V$ such that $N_W \ge \frac{1}{2} \cdot |E| $
Attempt:
The idea is: 
Suppose we toss a fair coin repeatedly.(independent)
$ W \subset V $ denotes this process. 
In other words: For every $ v \in V $ we toss a coin. If the coin shows head,  we say that $ v \in W$, otherwise $ v \notin W$. In this way $N_W$ can be regarded as a random variable. I'm sure that the expected value can us help to solve the problem. Unfortunately I'm stucked here.
Remark: I'm sure that there exists other solutions, but I want to solve it with my attempt.
Thank you for your help.
 A: When starting to learn the probabilistic method, it's often helpful to write out the expected values and summation very explicitly. Often the trick is taking the thing you want to count and counting it in a different way, which in its basic form corresponds to swapping the order of two sums. Let's see this in action with your idea.
$$ \mathbb{E}(N_W) = \sum_W P(W) N_W = \sum_W P(W) \sum_{e\in E} I_W(e) = \sum_{e\in E} \sum_W P(W) I_W(e) $$
We might interpret $\sum_W P(W) I_W(e)$ for a given $e \in E$ as the probability that $e \in [W, W^c]$ over all possible choices of $W$. (You could also just count this sum out directly.) You should be able to argue that this is $\frac{1}{2}$, from which the result immediately follows (the specifics I'll leave to you; they just involve finishing calculating the expected value and interpreting it).
The main idea here is that we switched from counting over all possible $W$ to counting over all edges $e$ first. It was much easier to look at each edge individually, since the edges of the graph are fixed and not probabilistic, then to see how the probabilistic components interact with those fixed components.
(Note that this is actually a really important problem that we've solved: you can take any graph and turn it into a bipartite graph with losing only half the edges.)
