Suppose we sample uniformly at random (without replacement) a set $S$ of edges from an undirected and unweighted graph $G = (V,E)$, creating a new graph $G'=(V',S)$ of only sampled nodes and edges. Let $(A,B)$ be the max cut in G with size equal to $|(A×B)∩E|$, and let $(A',B')$ be another generic cut with size $|(A'×B')∩E|$. Let $|(A'×B')∩S|$ be the size of $(A',B')$ in $G'$. Show that the probability that $|(A'×B')∩S|·\frac{|E|}{|S|}$ is greater than: $$|(A'×B')∩E| + ε·|(A×B) ∩ E|$$ is small. Consider the following Chernoff bounds for the proof: $$Pr\biggl[\sum_{i=1}^{|S|} X_i>(1+ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{3}\biggr)$$ $$Pr\biggl[\sum_{i=1}^{|S|} X_i<(1-ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{2}\biggr)$$
where $\mu$ is the expected value of the set of |S| of random variables.
Now, I am quite confused on this. I computed the expected value of the size of $(A',B')$ in $G'$ as: $$\mu=E\bigl[|(A'×B')∩S|\bigr] = \frac{|(A'×B')∩E|}{|E|} |S| $$ Then I could apply the first Chernoff bound to show that: $$Pr\biggl[|(A'×B')∩S|>(1+ε)|S|\mu\biggr] < exp\biggl(-\frac{\epsilon^2|S|\mu}{3}\biggr)$$ However I don't really know $\mu$ since I don't know the size $|(A'×B')∩E|$. Any suggestion?
The Chernoff bound does not apply here since $S$ is sampled without replacement and thus the $X_i$'s are not independent. Let $X = |(A' \times B') \cap S|$. It is easy to see that $X$ follows the hypergeometric distribution. That is, $$ \Pr(X = k) = \frac{\binom{|(A'\times B') \cap E|}{k}\cdot\binom{|E| - |(A'\times B')\cap E|}{|S| - k}}{\binom{|E|}{|S|}} $$ Therefore, $$ \mathbb{E}[X] = \frac{|(A'\times B') \cap E|}{|E|}\cdot |S| $$ By the paper by Skala, $$ \Pr(X \geq \mathbb{E}[X] + |S|\cdot t) \leq e^{-2t^2|S|} $$ from which by letting $t = \epsilon\cdot \frac{|(A\times B)\cap E|}{|E|}$, we attain \begin{align} &\Pr\left(|(A' \times B') \cap S| \geq \frac{|(A'\times B')\cap E|}{|E|}\cdot |S| + t|S|\right) \leq e^{-2t^2|S|} \\ \Rightarrow\ &\Pr\left(|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}\geq {|(A'\times B')\cap E|} + t|E|\right) \leq e^{-2t^2|S|} \\ \Rightarrow\ &\Pr\left(|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}\geq {|(A'\times B')\cap E|} + \epsilon\cdot|(A \times B)\cap E|\right) \leq e^{-2\left(\epsilon\cdot\frac{|(A\times B)\cap E|}{|E|}\right)^2|S|} \end{align} Note that $\frac{|(A\times B) \cap E|}{|E|} \geq \frac{1}{2}$ since the max cut of a graph has at least $|E| / 2$ edges. Hence, the RHS of the last inequality can be upper bounded by $e^{-\epsilon^2|S|/2}$.