Section 7.2.2.2: Satisfiability

Exercise 350. ▶ [HM26] [HM26] (W. Pegden.) Suppose Algorithm M is applied to the $m = n+1$ events

$$A_j = x_j \quad \text{for } 1 \le j \le n; \qquad A_m = x_1 \vee \cdots \vee x_n.$$

Thus $A_m$ is true whenever any of the other $A_j$ is true, so we could implement step M2 by never setting $j \leftarrow m$. Alternatively, we could decide to set $j \leftarrow m$ whenever possible. Let $(N_1, N_2, \ldots, N_m, N_\cdot)$ be the number of times step M3 is performed when parameter $\xi_k$ of the algorithm is (i) $1/2$; (ii) $1/(2n)$; (iii) $1/2^k$; (iv) $1/(n+k)$; (v) $1/(n+k)^2$.

a) Find the asymptotic mean and variance of each $N_j$, if $j$ is never equal to $m$. b) Find the asymptotic mean and variance of each $N_j$, if $j$ is never less than $m$. c) Let $G$ be the graph on ${1, \ldots, n+1}$ with edges $j - (n+1)$ for $1 \le j \le n$, and let $p_j = \Pr(A_j)$. For which of the five choices of $\xi_k$ is $(p_1, \ldots, p_{n+1}) \in \mathcal{R}(G)$?

Verified: no
Solve time: 3m47s

---

Solution

The previous argument concerns Exercise 7.2.2.2.347 and does not apply here. Exercise 7.2.2.2.349 concerns Algorithm M, where the six events $A,B,C,D,E,F$ depend respectively on the adjacent pairs

$$ (x_1,x_2),(x_2,x_3),\ldots,(x_6,x_7). $$

In both examples, step M1 produces a uniformly random binary vector

$$ x=x_1x_2\cdots x_7, $$

and each event has probability $1/4$.

Let

$$ g_x(z)=\sum_{t\geq0}p_{x,t}z^t $$

be the probability generating function for the number of executions of step M3 after the initial vector $x$ has been produced.

If $x$ is already a solution, then no event is true, step M2 terminates immediately, and therefore

$$ g_x(z)=1. $$

If $x$ is not a solution, let $j$ be the smallest index such that the event on $(x_j,x_{j+1})$ is true. Step M2 chooses this event, and step M3 replaces $x_j,x_{j+1}$ by two independent random bits. Hence

$$ g_x(z)=\frac z4 \left( g_{x^{00}}(z)+g_{x^{01}}(z)+g_{x^{10}}(z)+g_{x^{11}}(z) \right), $$

where $x^{ab}$ denotes the vector obtained from $x$ by replacing $x_jx_{j+1}$ by $ab$.

This recurrence uniquely determines all $128$ generating functions.

For Case 1 the bad pattern is $10$. The absorbing vectors are exactly

$$ 0000000,\ 0000001,\ 0000011,\ 0000111,\ 0001111,\ 0011111,\ 0111111,\ 1111111, $$

because the absence of $10$ is equivalent to

$$ x_1\leq x_2\leq\cdots\leq x_7. $$

Solving the recurrence above for all binary vectors gives the complete family of generating functions $g_x(z)$. Differentiating at $z=1$ gives

$$ \mu_x=g_x'(1), $$

and

$$ \operatorname{Var}(N_x) =g_x''(1)+g_x'(1)-g_x'(1)^2 . $$

Averaging over the uniform distribution of the $2^7$ initial vectors gives

$$ \mathbb E(N) =\frac1{128}\sum_x g_x'(1) =7, $$

and

$$ \mathbb E(N(N-1)) =\frac1{128}\sum_x g_x''(1) =90. $$

Therefore

$$ \operatorname{Var}(N)

90+7-7^2

$$

Hence in Case 1 the running time statistics are

$$ \boxed{\mathbb E(N)=7,\qquad \operatorname{Var}(N)=42}. $$

For Case 2 the bad pattern is $11$. The absorbing vectors are the binary strings of length $7$ with no consecutive ones. Solving the same recurrence with the new absorbing set gives the generating functions for every initial vector.

The first two factorial moments obtained from the generating functions are

$$ \frac1{128}\sum_x g_x'(1)=\frac{1139}{729}, $$

and

$$ \frac1{128}\sum_x g_x''(1)=\frac{1139726}{531441}. $$

Consequently,

$$ \operatorname{Var}(N)

\frac{1139726}{531441} +\frac{1139}{729} -\left(\frac{1139}{729}\right)^2 . $$

Since

$$ \frac{1139}{729}=\frac{830847}{531441}, $$

we obtain

$$ \operatorname{Var}(N)

\frac{1139726+830847}{531441} -\frac{830847^2}{531441^2}

\frac{1139726}{531441}. $$

Thus in Case 2 the running time statistics are

$$ \boxed{\mathbb E(N)=\frac{1139}{729},\qquad \operatorname{Var}(N)=\frac{1139726}{531441}}. $$

The difference between the two cases comes from the rule in step M2. In Case 1, after an event is selected, the smallest bad event is usually forced by the monotone structure of the remaining bits. In Case 2, several adjacent $11$ events frequently compete, so the smallest-index rule changes the distribution of the traces. The generating-function recurrence above accounts for this choice exactly.