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}$.

  • $\begingroup$ Thank you! What if we remove the assumption of sampling without replacement, and we assume sampling with replacement. Is it possible to solve it using the above Chernoff bounds? I can't figure it out... $\endgroup$ – Gianluca John Massimiani Jan 12 '18 at 8:02
  • 1
    $\begingroup$ @GianlucaJohnMassimiani For notational convenience, let $C' = A' \times B'$ and $C = A \times B$. We have \begin{align}&\Pr\left(|C' \cap S| \cdot \frac{|E|}{|S|} \geq |C' \cap E| + \epsilon \cdot |C \cap E|\right) \\ =\ & \Pr\left(|C' \cap S| \cdot \frac{|E|}{|S|} \geq |C' \cap E| + \epsilon \cdot \frac{|C \cap E|}{|C' \cap E|} \cdot |C' \cap E|\right) \\ \leq\ &\mathsf{exp}\left(-\frac{\epsilon^2\cdot \left(\frac{|C \cap E|}{|C' \cap E|}\right)^2\cdot |S| \cdot \frac{|C' \cap E|}{|E|}\cdot |S|}{3}\right)\end{align} $\endgroup$ – PSPACEhard Jan 13 '18 at 3:57
  • $\begingroup$ @GianlucaJohnMassimiani Then notice that $$ \left(\frac{|C \cap E|}{|C' \cap E|}\right)^2 \cdot \frac{|C' \cap E|}{|E|} = \frac{|C \cap E|}{|C' \cap E|} \cdot \frac{|C \cap E|}{|E|} \geq 1 \cdot \frac{1}{2}$$ $\endgroup$ – PSPACEhard Jan 13 '18 at 4:01
  • $\begingroup$ @PSPACE-Hard Why you have inside ≤ exp(...) two times |S| ?(I'm talking about the last case where replacement is allowed) I did the same reasoning but I don't have two |S| in the multiplication, did i do something wrong? If yes could you provide me intermediate steps? Also how to do that for the second bound I mean the one having (1-ε). Thanks in advance. $\endgroup$ – Richard Yellow Jan 13 '18 at 13:49
  • $\begingroup$ @GianlucaJohnMassimiani You are right. I did wrong. The last $|S|$ is not required. $\endgroup$ – PSPACEhard Jan 14 '18 at 3:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.