## Method of Conditional Probabilities and Expectations

Derandomization.

- Theory: is P=RP?
- practice: avoid chance of error, chance of slow.

### The Probabilistic Method for Expectations

Outline

- goal to show exists object of given “value”
- give distribution with greater “expected value”
- deduce goal

Conditional Expectation. Max-Cut

- Imagine placing one vertex at a time.
- $x_i=0$ or $1$ for left or right side
- $E[C] = (1/2)E[C | x_1=0] + (1/2)E[C | x_1=1]$
- Thus, either $E[C | x_1=0]$ or $E[C|X_1=1] \ge E[C]$
- Pick that one, continue
- More general, whole tree of element settings.
- Let $C(a) = E[C \mid a]$.
- For node $a$ with children $b,c$, either $C(b)$ or $C(c) \ge C(a)$.

- By induction, get to leaf with expected value at least $E[C]$
- But no randomness left, so that is actual cut value.
- Problem: how compute node values? Easy.

Conditional Probabilities. Set balancing. (works for wires too)

- Review set-balancing Chernoff bound
- Think of setting item at a time
- Let $Q$ be bad event (unbalanced set)
- We know $\Pr[Q] < 1/n$.
- $\Pr[Q] = 1/2\Pr[Q \mid x_{i0}]+1/2\Pr[Q \mid x_{i1}]$
- Follows that one of conditional probs. less than $\Pr[Q]< 1/n$.
- More general, whole tree of element settings.
- Let $P(a) = \Pr[Q \mid a]$.
- For node $a$ with children $b,c$, $P(b)$ or $P(c)< P(a)$.
- $P(r) < 1$ sufficient at root $r$.
- at leaf $l$, $P(l)=0$ or $1$.

- One big problem: need to compute these probabilities!

### Pessimistic Estimators.

- Alternative to computing probabilities
- four neceessary conditions:
- $\Phat$ upper bound on true probability of trouble.
- $\Phat(r) < 1$
- $\min \{\Phat(b),\Phat(c)\} < \Phat(a)$
- $\Phat$ computable

- Apply to set balancing
- Let $Q_i = \Pr[\mbox{unbalanced set $i$}]$
- Let $\Phat(a) = \sum \Pr[Q_b \mid a]$ at tree node $a$
- note this is just expected number of violated constraints
- Claim 3 conditions.
- HW

- Result: deterministic $O(\sqrt{n\ln n})$ bias.
- more sophisticated pessimistic estimator for wiring.

### Wiring

Use multicommodity flow computation.

Recall:

- fractional relaxation congestion $w$
- used chernoff to argue $\Pr[>(1+\epsilon)w] \le 1/m$ for every edge
- then union bound over all edges

Different pessimistic estimator.

- Recall Chernoff bound derivation $$ \begin{eqnarray*} X &= \sum &X_i\\ \Pr[X \ge (1+\epsilon)\mu] &\le \frac{E[e^{tX}]}{e^{t(1+\epsilon)\mu}} \\ &= cE[e^{t\sum X_i}]\\ \end{eqnarray*} $$
- Sum this quantity over edges to get pessimistic estimator. \[ cE[\sum_e e^{t\sum_i X_i^e}] \] (here $X_i^e$ is 1 if path for $i$ terminal uses $e$).
- Check conditions:
- Upper bound? yes, that's why use it
- below one at root? yes---that's how we proved randomized rounding worked
- decrease at child? yes, because is an expected value, so average over children
- computable? yes, as $\prod_i E[e^{tX_i^e}]$