TAOCP 7.2.2.2 Exercise 183

Exercise 183. [M30] [M30] Discuss the relation between Figs. 42 and 43.

Verified: no
Solve time: 4m17s

Edit

Solution

Let (T_m) be the number of satisfying assignments remaining after (m) clauses have been selected, and let (P) be the number of clauses selected when satisfiability is first lost. Thus

[ \Pr(P=m)=p_m. ]

Figure 42 concerns the distribution

[ \Pr(T_m=1), ]

while Figure 43 concerns the distribution of the stopping time (P). The similarity between the figures comes from the fact that a formula with a single remaining satisfying assignment is close to the point where the next clause destroys satisfiability.

There are

[ \binom{5}{3}2^3=80 ]

possible distinct clauses on five variables. Fix a particular assignment (A). For each choice of three variables, exactly one of the eight possible clauses on those variables is false under (A), namely the clause containing the three literals contradicted by (A). Hence (A) falsifies

[ \binom{5}{3}=10 ]

of the possible clauses.

Suppose that after (m) clauses the formula has exactly one satisfying assignment, namely (A). The clauses falsified by (A) cannot have appeared among the first (m) clauses, because any one of them would have eliminated (A). Therefore all ten clauses falsified by (A) remain among the

[ 80-m ]

unused clauses. Consequently,

[ \Pr(P=m+1\mid T_m=1)=\frac{10}{80-m}. ]

Thus the formulas counted in Figure 42 contribute to the probability in Figure 43 according to

[ \Pr(T_m=1)\frac{10}{80-m}. ]

This contribution explains the displacement of the two curves. The event (T_m=1) describes the moment when the formula has reached its last surviving assignment. The event (P=m+1) describes the following step, when a remaining clause eliminates that last assignment. Therefore the main feature of Figure 42 should appear one clause earlier than the corresponding feature of Figure 43.

The relation is not an exact equality, because a formula can become unsatisfiable after the next clause even when it has more than one satisfying assignment. If (T_m=k>1), the next clause destroys satisfiability precisely when every one of those (k) assignments falsifies that clause. Such events contribute additional terms to (p_{m+1}). In general,

\sum_{k\geq 1} \Pr(T_m=k) \Pr(P=m+1\mid T_m=k). ]

The term with (k=1) is

[ \Pr(T_m=1)\frac{10}{80-m}, ]

while the terms with (k>1) represent the possibility that the final clause eliminates several surviving assignments at once.

The figures therefore should not be interpreted as displaying identical probability distributions. Rather, Figure 42 records the approach to the final surviving assignments, and Figure 43 records the subsequent destruction of all surviving assignments. The one-clause shift and the slowly varying factor

[ \frac{10}{80-m} ]

make the two curves have similar shapes. Any discrepancy between them comes from cases in which more than one satisfying assignment remains immediately before the formula becomes unsatisfiable.

Hence the relation between Figs. 42 and 43 is that the distribution in Fig. 43 is approximately the distribution in Fig. 42 shifted one step to the right and modified by the probability that the next clause is one of the clauses eliminating the last remaining assignment:

[ \boxed{ p_{m+1} \text{ has a major contribution } \Pr(T_m=1)\frac{10}{80-m}. } ]

This explains why the two figures have nearly the same shape.