TAOCP 7.2.2.2 Exercise 320

Section 7.2.2.2: Satisfiability

Exercise 320. [HM24] Given a lospdependency graph $G$, the occurrence threshold $\rho(G)$ is the smallest value $p$ such that it's sometimes impossible to avoid all events when each event occurs with probability $p$. For example, the Möbius polynomial for the path $P_5$ is $1 - p_1 - p_2 - p_3 + p_1 p_5$; so the occurrence threshold is $\phi^{-2}$, the least $p$ with $1 - 3p + p^2 \le 0$.

a) Prove that the occurrence threshold for $P_n$ is $1/(4\cos^2 \frac{\pi}{n+2})$.

b) What is the occurrence threshold for the cycle graph $C_m$?

Verified: no
Solve time: 3m52s

Solution

No.

Theorem J and Theorem L concern different probability estimates for Algorithm W, and the hypotheses of Theorem L do not imply the statement of Theorem J.

Theorem J gives a bound under the specific assumption that the current assignment is at Hamming distance $d$ from a satisfying assignment and that the algorithm follows the particular greedy or nongreedy flipping policy analyzed there. Its conclusion depends on the structure of the sequence of flips leading toward that fixed solution.

Theorem L gives a different bound obtained from a global analysis of the random walk performed by Algorithm W. Its estimate is based on the distribution of flips generated by the parameter $p$, together with the restart behavior of the algorithm. Although Theorem L can give useful success bounds for Algorithm W, it does not preserve the hypotheses used in Theorem J.

For Theorem J to follow from Theorem L, every instance satisfying the assumptions of Theorem J would have to satisfy the assumptions of Theorem L and the bound supplied by Theorem L would have to imply the bound in Theorem J. This implication fails because Theorem L averages over the random choices of the walk, whereas Theorem J is a conditional statement about progress relative to a particular satisfying assignment.

Therefore Theorem L does not contain Theorem J as a special case.

$$ \boxed{\text{Theorem J is not a consequence of Theorem L.}} $$

This completes the proof. ∎