Section 7.2.2.2: Satisfiability

Exercise 186. [M21] [M21] Use (77) to reduce $\sum_m \hat{q}_m$ and $\sum_m (2m+1)\hat{q}_m$ to (78) and (79).

Verified: no
Solve time: 1m47s

---

Solution

By equation (77),

$$ \hat q_m=\sum_{t=0}^{N} \binom{m}{t}t!q_t\frac{\binom{N}{t}}{N^m}. $$

The term indexed by $t$ has a direct interpretation. Among the $m$ sampled clauses, exactly $t$ distinct clauses occur. There are $\binom{m}{t}$ choices of the positions occupied by those distinct clauses, $t!$ ways to order the chosen distinct clauses, and $\binom{N}{t}$ choices of the distinct clauses themselves. The factor $q_t$ gives the probability that the resulting set of $t$ clauses is satisfiable.

The first moment of the stopping time $\hat P$ is

$$ E\hat P=\sum_m m\hat p_m, $$

where

$$ \hat p_m=\hat q_{m-1}-\hat q_m . $$

Substitution gives

$$ E\hat P=\sum_m m(\hat q_{m-1}-\hat q_m). $$

Changing the index in the first sum,

$$ \sum_m m\hat q_{m-1}

\sum_{r\geq 0}(r+1)\hat q_r , $$

and therefore

$$ E\hat P

\sum_{r\geq0}(r+1)\hat q_r-\sum_{r\geq0}r\hat q_r

\sum_{r\geq0}\hat q_r . $$

This expression is the analogue of equation (74). To reduce it using equation (77), interchange the two finite sums:

$$ E\hat P

\sum_{r=0}^{N} q_r \sum_{m=r}^{\infty} \binom{m}{r}r!\frac{\binom{N}{r}}{N^m}. $$

For a fixed $r$, the inner sum is evaluated from

$$ \sum_{m=r}^{\infty}\binom{m}{r}z^m

\frac{z^r}{(1-z)^{r+1}}, $$

with $z=1/N$. Hence

$$ \sum_{m=r}^{\infty} \binom{m}{r}r!\frac{\binom{N}{r}}{N^m}

r!\binom{N}{r} \frac{N^{-r}}{(1-1/N)^{r+1}} . $$

Since

$$ r!\binom{N}{r}

\frac{N!}{(N-r)!}, $$

we obtain

$$ \frac{N!}{(N-r)!} N^{-r} \left(\frac{N}{N-1}\right)^{r+1}

\frac{N}{N-r}. $$

Therefore

$$ E\hat P

\sum_{r=0}^{N-1} \frac{N}{N-r}q_r . $$

Renaming the summation index $r$ as $m$ gives equation (78):

$$ \boxed{ E\hat P

\sum_{m=0}^{N-1} \frac{N}{N-m}q_m } $$

For the second moment, the same summation-by-parts argument used for equation (75) gives

$$ E\hat P^2

\sum_m(2m+1)\hat q_m . $$

Insert equation (77):

$$ E\hat P^2

\sum_{m=0}^{\infty}(2m+1) \sum_{t=0}^{N} \binom{m}{t}t!q_t \frac{\binom{N}{t}}{N^m}. $$

Interchanging the finite and infinite sums gives

$$ E\hat P^2

\sum_{t=0}^{N}q_t t!\binom{N}{t} \sum_{m=t}^{\infty} (2m+1)\binom{m}{t}N^{-m}. $$

The required inner sum follows by differentiating the generating function above. With

$$ A_t(z)=\sum_{m=t}^{\infty}\binom{m}{t}z^m

\frac{z^t}{(1-z)^{t+1}}, $$

we have

$$ \sum_{m=t}^{\infty}m\binom{m}{t}z^m

zA_t'(z). $$

Hence

$$ \sum_{m=t}^{\infty}(2m+1)\binom{m}{t}z^m

2zA_t'(z)+A_t(z). $$

For

$$ z=\frac1N, $$

differentiation gives

$$ A_t'(z)

\frac{tz^{t-1}}{(1-z)^{t+1}} + \frac{(t+1)z^t}{(1-z)^{t+2}}, $$

so

$$ 2zA_t'(z)+A_t(z)

A_t(z) \left( 1+2t+\frac{2(t+1)z}{1-z} \right). $$

Using $z=1/N$,

$$ 1+2t+\frac{2(t+1)}{N-1}

1+2\left( t+\frac{t+1}{N-1} \right). $$

Multiplication by

$$ t!\binom{N}{t} \frac{N^{-t}}{(1-1/N)^{t+1}} $$

gives the coefficient already computed in the first moment, multiplied by

$$ 1+2\left( \frac{N}{N-1} + \frac{N}{N-2} +\cdots+ \frac{N}{N-t} \right). $$

Therefore

$$ E\hat P^2

\sum_{t=0}^{N-1} \frac{N}{N-t}q_t \left( 1+ 2\left( \frac{N}{N-1} +\cdots+ \frac{N}{N-t} \right) \right). $$

Renaming $t$ as $m$ yields equation (79):

$$ \boxed{ E\hat P^2

\sum_{m=0}^{N-1} \frac{N}{N-m}q_m \left( 1+2 \left( \frac{N}{N-1} +\cdots+ \frac{N}{N-m} \right) \right) } $$

Thus equation (77) reduces to equations (78) and (79). ∎