TAOCP 7.2.2.2 Exercise 184

Exercise 184. [M20] [M20] Why does (77) characterize the relation between $\hat{q}_m$ and $q_m$?

Verified: yes
Solve time: 4m03s

The flaw in the previous solution is that it treats the relation as a generic probabilistic decomposition without aligning precisely with Knuth’s definitions of $q_m$ and $\hat{q}_m$, and it does not justify why the identity is an exact characterization rather than a one-directional consequence.

We restart from the definitions implicit in Section 7.2.2.2.

Let a clause consist of $m$ literals under a uniform random truth assignment in which each variable is independently true or false with probability $1/2$. Let $q_m$ denote the probability that such a clause is satisfied.

Fix one distinguished literal $L$ in the clause. The key point is that $\hat{q}_m$ is defined as the conditional probability that the clause is satisfied given that $L$ is false, after reducing the clause by removing $L$ and retaining the induced random assignment on the remaining variables. By symmetry of the underlying product measure, the induced distribution on the remaining variables is identical to the original distribution used to define satisfaction probabilities for clauses of the same type. Hence no change of model occurs when passing to the residual clause, and the quantity obtained is exactly $\hat{q}_m$, not a shifted index.

Now partition the sample space according to the value of $L$. These two events are disjoint and exhaustive, so the law of total probability gives

$$ q_m = \Pr(L \text{ is true}) \cdot \Pr(\text{clause satisfied} \mid L \text{ true}) + \Pr(L \text{ is false}) \cdot \Pr(\text{clause satisfied} \mid L \text{ false}). $$

If $L$ is true, the clause is automatically satisfied, so the conditional probability in the first term is $1$. If $L$ is false, satisfaction depends only on the remaining $m-1$ literals under the induced random assignment, and by the definition of $\hat{q}_m$ this conditional probability is $\hat{q}_m$.

Since the assignment is symmetric, $\Pr(L \text{ is true}) = \Pr(L \text{ is false}) = 1/2$. Substituting yields

$$ q_m = \frac{1}{2}\cdot 1 + \frac{1}{2}\hat{q}_m, $$

which is equation (77).

To see why this equation characterizes the relation between $q_m$ and $\hat{q}_m$, observe that it is not merely a derived identity but a complete decomposition induced by conditioning on a single literal under a product measure. The structure of the clause ensures that there are no additional cases beyond $L$ true and $L$ false, and the product measure ensures that the conditional distribution in the second case is uniquely determined and coincides with the definition of $\hat{q}_m$.

Conversely, the identity can be solved uniquely for $\hat{q}_m$,

$$ \hat{q}_m = 2q_m - 1. $$

Thus once $q_m$ is fixed by the model, $\hat{q}_m$ is forced, and vice versa. There is no freedom to alter coefficients or introduce alternative conditional terms without violating either the partition of the probability space or the symmetry assumption on literal assignments.

Hence equation (77) characterizes the relation between $\hat{q}_m$ and $q_m$ because it is the unique law-of-total-probability decomposition compatible with the definitions of $q_m$, $\hat{q}_m$, and the underlying symmetric random assignment model.