0

In https://lucatrevisan.github.io/teaching/bwca17/lectures/lecture02.pdf (Lemma 6), the professor claimed that:

"With high probability over the choice of $G$ from $G_{n,\frac{1}{2}}$, the greedy algorithm finds a cut of size $\frac{n^2}{8}+\Omega(n^{1.5})$."

The proof of the lemma is clear except one detail:

Let the cut we construct in the $i-1$th loop in the greedy algorithm be $E(S,T)$. When we process node $v_i$ in the $i$-th loop, let the the number of edges between nodes in $S$/$T$ and $v_i$ be $X_i$/$Y_i$, the proof just directly claimed that the expectation of $|X_i-Y_i|$ is $\Omega(\sqrt{i})$ and the variance is $O(i)$.

I think this is not trivial. Is there any proof for the detail mentioned above?

graph lover
  • 1

1 Answers1

3

The handout specifies that $X_i$ and $Y_i$ are respectively the sum of $a_i$ and $b_i$ random bits. Since we're taking the expected absolute difference $Z_i = |X_i - Y_i|$ of sums of $0$s and $1$s, the problem reduces to finding the expectation of absolute difference between the number of $0$s and $1$s in the random bitstrings (again the absolute difference and the fact we aim for asymptotic characterisations and not precise expressions). Now concatenate both random bitstrings to obtain a bitstring $B$ of length $2i$. Then if we take the distribution $Y_i$ (note that up to symmetry we can also call this $X_i$) of the number of ones, $Y_i \sim \mathsf{Bin}\left(2i, \frac12\right)$, and therefore there are $2i - Y_i$ zeros, so that $Z_i = |2i - Y_i - Y_i| = 2|Y_i - i|$.

Applying the CLT gives us that $(Y_i - i)\sqrt{2i^{-1}} \xrightarrow{d} \mathcal{N}(0, 1)$, and therefore $$\mathbb{E}[Z_i] = 2 \cdot \sqrt{\frac{i}{2}}\mathbb{E}\left[\left|(Y_i - i)\sqrt{2i^{-1}}\right|\right] = \sqrt{2i}\mathbb{E}[\mathcal{N}(0, 1)] = \sqrt{2i} \cdot \sqrt{\frac{2}{\pi}} = \Omega(\sqrt{i}).$$ The computation for the variance goes in exactly the same way.

Ekene E.
  • 537