Section 7.2.2.2: Satisfiability

Exercise 349. ▶ [M24] [M24] Analyze Algorithm M exactly in the two examples considered in the text (see (150)): For each binary vector $x = x_1 \ldots x_7$, compute the generating function $g_x(z) = \sum_t p_{x,t} z^t$, where $p_{x,t}$ is the probability that step M3 will be executed exactly $t$ times after step M1 produces $x$. Assume that step M2 always chooses the smallest possible value of $j$. (Thus, in Case 2, formula in (150) will never occur.)

What are the mean and variance of the running times, in (i) Case 1? (ii) Case 2?

Verified: no
Solve time: 7m06s

---

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.