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?


1 Answer 1


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$ Commented Jan 12, 2018 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
    Commented Jan 13, 2018 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
    Commented Jan 13, 2018 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$ Commented Jan 13, 2018 at 13:49
  • $\begingroup$ @GianlucaJohnMassimiani You are right. I did wrong. The last $|S|$ is not required. $\endgroup$
    – PSPACEhard
    Commented Jan 14, 2018 at 3:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .