Section 7.2.2.2: Satisfiability

Exercise 355. [HM21] In (152), prove that $E_j \le 1/\delta$ when $(p_1, \ldots, p_m)$ has positive slack $\delta$. Hint: Consider replacing $p_i$ by $p_j + \delta p_j$.

Verified: no
Solve time: 3m44s

Solution

Let $E_j$ denote the expected number of executions of the resampling step associated with the bad event $A_j$, as in (152). The standard witness-tree expression for this expectation is

$$ E_j=\sum_{\tau\in\mathcal{T}_j} w(\tau), $$

where $\mathcal{T}_j$ is the family of proper witness trees whose root is labeled $j$, and $w(\tau)$ is the probability weight of the witness tree $\tau$.

Assume that the hypothesis (133) holds. Thus there are numbers $\theta_1,\ldots,\theta_m$ with

$$ 0\leq \theta_i<1 $$

such that

$$ p_i\leq \theta_i\prod_{i\sim k}(1-\theta_k). $$

For a witness tree $\tau$ rooted at $j$, let $n_i(\tau)$ be the number of vertices of $\tau$ carrying label $i$. The witness-tree probability estimate gives

$$ w(\tau)\leq \prod_i \left( \theta_i^{,n_i(\tau)} (1-\theta_i)^{,d_i(\tau)} \right), $$

where $d_i(\tau)$ is the number of possible children of label $i$ that are excluded by the tree structure. Summing over all possible children of a vertex labeled $i$ contributes a factor

$$ \sum_{S\subseteq N(i)} \prod_{k\in S}\theta_k \prod_{k\notin S}(1-\theta_k)=1. $$

Therefore, when the witness trees are summed from the leaves upward, every nonroot vertex contributes a total factor of at most $1$, while the root label $j$ contributes the factor

$$ \theta_j+\theta_j^2+\theta_j^3+\cdots . $$

The first power of $\theta_j$ corresponds to the tree consisting only of the root. The higher powers correspond to additional descendants labeled $j$. Hence

$$ E_j\leq \sum_{r\geq1}\theta_j^r . $$

Because $0\leq\theta_j<1$, this geometric series converges and has value

$$ \sum_{r\geq1}\theta_j^r

\frac{\theta_j}{1-\theta_j}. $$

Consequently,

$$ \boxed{ E_j\leq \frac{\theta_j}{1-\theta_j} }. $$

This completes the proof.

∎