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
  Imply can use $\Phat$ instead of actual.
• 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}]$