I read this: estimate value of maximum cut in graph by random sampling but I didn't understand how to solve my problem that is very similar.
My problem is let $G(V, E)$ be an unweighted and undirected graph. Let $S$ be a set of $\frac{24n}{ε^{2}}$ edges sampled uniformly at random without replacement. Assume that we only have access to the sampled edges of graph. Our goal is to estimate the weight of the max-cut $w(A, B) = |(A \times B) \cap E|$. Specifically, show that we can obtain a $(1 \pm \epsilon)$ approximate estimate by computing
$$|(A \times B) \cap S| \cdot \frac{|E|}{|S|},$$ while also showing that for any cut $(A', B')$ that is not the max-cut, the probability that the estimated cut value $|(A' \times B') \cap S| \cdot \frac{|E|}{|S|}$ is greater than
$$|(A' \times B') \cap E| + \epsilon \cdot |(A \times B) \cap E|$$
is small. Your algorithm has to succeed with probability at least $\frac{1}{2}$, but can take an arbitrary time.
Base your estimation on the following two probabilistic inequalities:
- Given a set of $|S|$ i.d.d. Bernoulli random variables $X_{1}, ..., X_{|S|}$ with expected value $\mu$, the Chernoff bounds state
$$P[\sum_{i=1}^{|S|}X_{i} > (1 + \epsilon)|S| \cdot \mu] < exp(- \frac{\epsilon^{2} \cdot |S| \cdot \mu}{3}) \text{ and}$$ $$P[\sum_{i=1}^{|S|}X_{i} < (1 - \epsilon)|S| \cdot \mu] < exp(- \frac{\epsilon^{2} \cdot |S| \cdot \mu}{2})$$
- The union bound states that given multiple not necessarily disjoint Bernoulli random variables $E_{i}$,
$$P[\cup E_{i}] \le \sum P[E_{i}|. $$