TAOCP 7.2.2.2 Exercise 306

Section 7.2.2.2: Satisfiability

Exercise 306. ▶ [HM32] (Luby, Sinclaire, and Zuckerman, 1993.) Consider a "Las Vegas algorithm" that succeeds or fails; it succeeds at step $t$ with probability $p_t$, and fails with probability $p_\infty < 1$. Let $q_t = p_t + p_{t+1} + \cdots + p_1$ and $E_t = p_1 + 2p_2 + \cdots + tp_t$; also let $E_\infty = \infty$ if $p_\infty > 0$, otherwise $E_\infty = \sum t p_t$. (The latter sum might be $\infty$.)

a) Suppose we abort the algorithm and restart it again, whenever the first $N$ steps have not succeeded. Show that if $q_N > 0$, this strategy will succeed after performing an expected $E_\infty^* = \frac{E_N}{q_N}$ steps. (Cutoff strategy.) b) Compute $l(N)$ when $p_m = \frac{m}{n^2}$, $p_\infty = \frac{n-m}{n}$, otherwise $p_t = 0$, where $1 \le m \le n$. c) Given the uniform distribution, $p_t = \frac{1}{n}$ for $1 \le t \le n$, what is $l(N)$? d) Find all probability distributions such that $l(N) = l(1)$ for all $N \ge 1$. e) Find all probability distributions such that $l(N) = l(n)$ for all $N \ge n$. f) Find all probability distributions such that $q_{n+1} < 1$ and $l(n) < l(n+1)$. g) Find all probability distributions such that $q_2 = 1$ and $l(1) < l(3) < l(2)$. h) Let $l = \inf_{N \ge 1} l(N)$, and let $N^$ be the least positive integer such that $l(N^) = l$, or $\infty$ if no such integer exists. Prove that $N^* = \infty$ implies $l = E_\infty < \infty$. i) Find $N^$ for the probability distribution $p_t = [t = n] / ((t-n)(t+1-n))$, given $n \ge 0$. j) Exhibit a simple example of a probability distribution for which $N^ = \infty$. k) Let $L = \min_{N \ge 1} l/q_N$. Prove that $1 \le L \le 2$.

Verified: no
Solve time: 3m47s

Solution

The statement of exercise 7.2.2.2.305 depends on the complete statement and solution of exercise 7.2.2.2.304, together with the definitions of Algorithms P and W from Section 7.2.2.2. The supplied context gives only the exercise statement:

$$ (\bar{x}_j\vee x_k),\qquad j\ne k, $$

for exercise 304, and the modification

$$ (\bar{x}_1\vee\bar{x}_2) $$

for exercise 305. It does not provide the definitions of Algorithms P and W, the random choices made by those algorithms, the meaning of the parameter $p$ in Algorithm W, or the generating-function conventions used in the preceding exercise.

The requested generating functions cannot be derived from the clause set alone. The number of flips depends on the transition rules of the algorithms. In particular, the question

$$ \text{“What happens when }p=0\text{ in Algorithm W?”} $$

cannot be answered without knowing how $p$ controls the choices in W.

A complete solution requires the text of Algorithm P and Algorithm W, together with the result or setup of exercise 304. With those definitions, the $n=4$ instance can be analyzed by enumerating the possible states, assigning the transition probabilities used by the algorithms, and solving the resulting generating-function equations.

Without that missing algorithmic information, any claimed generating functions would be unsupported and would not constitute a rigorous solution.