Derandomization via smaller sample space

One way to turn the above randomized algorithm into a deterministic one is to go over all $S \in \Omega$ and check whether $|\delta_G(S)| \geq m/2$. Since we know that such $S$ exists, our algorithm would always find one. But such an algorithm would take exponential time, since the sample space size is $2^n$.

Our goal is to define a different sample space of polynomial size and show that the expected cut size in this new sample space is still at least $m/2$. This will immediately imply a polynomial time algorithm.

Consider the probability space in Example 39 where we have $|\Omega| \leq 2n$ and there are $n$ pairwise independent events $E_1,\ldots, E_n$ that are balanced (${\mathbb P}[E_i] = 1/2$ for all $i$). Now, each atomic event $\omega \in \Omega$ corresponds to a cut $S$ so that:

$i \in S$ if and only if $\omega \in E_i$

Therefore, we can define the random variable $X = |\delta_G(S)|$ in the same way (since $X$ depends on $\omega$). We have that $X= \sum_e X_e$ as before. Now let us consider, for $e = \{i,j\}$,

${\mathbb P}[\{i,j\} \in \delta_G(S)] = {\mathbb P}[i \in S, j \not\in S] + {\mathbb P}[i \not \in S, j \in S]$

The point is that, the event $i \in S$ is exactly the event $E_i$ and $j \in S$ is $E_j$. Therefore, using the fact that they are (pairwise) independent,

${\mathbb P}[\{i,j\} \in \delta_G(S)] = (1/2)(1/2) + (1/2)(1/2) = 1/2$

Repeating the previous calculation, we have ${\mathbb E}[X] = \sum_e {\mathbb E}[X_e] = m/2$. This implies the same result, but now we are using a much smaller probability space (of size $2n$)! Therefore, the algorithm could go over all $2n$ atomic events in the sample space and check if it corresponds to a cut of size at least $m/2$.

In a way, the key message is that the analysis of expectation only relies on pairwise independence, instead of (full) independence. This allows us to obtain a deterministic algorithm instead of the randomized algorithm since the probability space is much smaller. Such an example illustrates another intimate connection between computation and probability: Probabilistic analysis that only relies on a limited degree of independence (in particular, $O(1)$-wise independence) can almost always be turned into an efficient algorithm.