Section 7.2.2.2: Satisfiability

Exercise 352. [M21] [M21] Show that $E_j \le \theta_j/(1 - \theta_j)$ in (152), when (133) holds.

Verified: no
Solve time: 10m35s

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.

∎