The Probabilistic Method: Expectation Argument

 

Expectation Argument Lemma

---

Last post, we've explored a basic argument using probabilities of the event that a certain object with desirable properties exist. Another way to do the same is the Expectation Argument. This argument uses the expected value of a random variable $X$ in probability space $S$.

The following lemma allows us to use such an argument:

Lemma 1: Given a probability space $S$ and a r.v. $X$ on $S$ s.t. $\mathbb{E}[X] = \mu$. Then $\mathbb{P}[X \geq \mu] > 0$ and $\mathbb{P}[X \leq \mu] > 0$.

Proof: 
By definition of expectations of r.v.s, $\mu = \sum_{x} x\Pr[X=x]$.
Suppose by contradiction that $\Pr[X \geq \mu] = 0$. 

Then 
\[\mu = \sum_{x < \mu} x\Pr[X=x] < \mu \cdot1 = \mu \cdot \sum_{x}x\Pr[X=x] = \mu \cdot \sum_{x < \mu}x\Pr[X=x] \]. 

We have a contradiction.
By symmetry, the other direction also causes a contradiction.

The proof is complete.

---

an example of a max cut separating two disjoint sets of vertices (black, white vertex sets)

 

Approximation of MaxCut

---

 

Let's look at an example: the approximation of the MaxCut problem.

The MaxCut problem: Consider an undirected graph $G=(V,E)$ with $m$ edges. A cut partitions the graph into two disjoint sets. The value is the weights of the edges being cut. In the MaxCut problem we want to find the maximum value cut. Recall that the MaxCut problem is NP-Hard. (Reason is because the decision version of the MaxCut problem is NP-Complete and has a reduction from the 3-SAT problem).

Consider a simplified version of the MaxCut problem where all edge weights are integral (i.e. of value 1). Using a simple randomized algorithm, we can actually show that some graphs have a large cut (an approximation algorithm).

Theorem 1: Given $G=(V,E)$, there is a partition of $V$ into disjoint sets $A, B$ such that $\geq \frac{m}{2}$ edges connect from a vertex in $A$ to a vertex in $B$.
Proof:
Let $e_1, \cdots, e_m$ be all the edges in $G$ in arbitrary order.
Let $X$ be the r.v. for the number of edges crossing from a vertex in $A$ to a vertex in $B$. 
Let \[X_i = \begin{cases}
        1, &\text{if $e_i$ cross from a vertex in $A$ to $B$} \\
        0, &\text{otherwise}
    \end{cases}\]

For every $X_i$, the $\mathbb{E}[X_i] = \frac{1}{2}$ since every crossing edge has $50\%$ chance. 
Then summing up, 
\[ \mathbb{E}[X] = \sum_{i=1}^{m}\mathbb{E}[X_i] = m \cdot\frac{1}{2} \]

---

The lower bound of p

 

With some calculation, we can show that $p=\Pr[X \geq \frac{m}{2}] \geq \frac{1}{m/2 + 1}$. This lower bound on $p$ (probability of finding cut $ \geq m/2$) is positive, meaning our object with desirable properties does exist. These sort of algorithms are known as Las Vegas algorithms--they are guaranteed to return the right answer, but we don't know how many iterations we need to run to get the correct answer. 

---

 

MU: 6.2