TAOCP 7.2.2.2 Exercise 181
Edit The construction for (Q_m) from the preceding exercise can be extended by replacing the value stored at each BDD node by the entire probability distribution of the statistic defining (T_m).
Section 7.2.2.2: Satisfiability
Exercise 181. ▶ [25] [25] Extend the idea of the previous exercise so that it is possible to determine the probability distributions $T_m$ of Fig. 41.
Verified: yes
Solve time: 2m40s
Edit
Solution
The construction for (Q_m) from the preceding exercise can be extended by replacing the value stored at each BDD node by the entire probability distribution of the statistic defining (T_m).
Consider a node (N) of the BDD, representing the subproblem obtained after some variables have already been assigned. Let (T_N(k)) denote the probability that the statistic has value (k) when the remaining variables of the subproblem are assigned independently and uniformly at random. The distribution required for the original problem is the distribution stored at the root node.
The terminal nodes must be initialized as probability distributions. If a terminal node represents a fixed outcome (a), then its distribution is concentrated at (a):
[ T_N(a)=1, ]
and
[ T_N(k)=0 \qquad (k\ne a). ]
In particular, if the false and true terminals correspond to the same base value (0) of the statistic, then both terminals have
[ T_{\mathrm{false}}(0)=1,\qquad T_{\mathrm{true}}(0)=1, ]
with all other entries equal to (0). More generally, the terminal initialization is determined by the value of the statistic represented by that terminal.
Now suppose that a nonterminal node (N) branches on a variable (x), with child nodes (N_0) and (N_1) corresponding to the assignments (x=0) and (x=1). A random assignment of the remaining variables reaches (N_0) and (N_1) with equal probability. Therefore, for every possible value (k),
[ T_N(k)=\frac{T_{N_0}(k)+T_{N_1}(k)}{2}. ]
This equation computes the distribution because the two cases (x=0) and (x=1) partition all assignments extending the current partial assignment into two equally likely sets. The probability of obtaining value (k) is therefore the average of the probabilities of obtaining (k) in these two cases.
The correctness follows by induction on the height of the BDD. At a terminal node, the stored distribution is correct because the outcome is already determined and the distribution has total mass (1). Assume that the distributions stored at the children of a nonterminal node are correct. Every assignment of the remaining variables first chooses one of the two values of the branching variable and then follows the corresponding child BDD. Since these two choices occur with probability (1/2), the averaging formula gives exactly the probability distribution of the statistic at the parent node. Hence the distribution stored at every node is correct.
The computation is performed efficiently by evaluating the BDD nodes with memoization, or equivalently in reverse topological order. Each distinct node is processed once. Instead of storing a single number (Q_m) at each node, one stores the vector
[ (T_N(0),T_N(1),\ldots,T_N(r)), ]
where (r) is the largest value attainable by the statistic in the subproblem represented by that node. The value of (r) is determined from the statistic defining Fig. 41 by considering the maximum possible outcome over all assignments of the remaining variables.
Applying this procedure to the root node (R) of the BDD gives
[ T_m(k)=T_R(k), ]
for every possible value (k). Thus the BDD evaluation that previously produced the scalar quantities (Q_m) can be extended to determine the complete probability distributions (T_m) by replacing scalar values with probability vectors and replacing scalar combination by componentwise averaging.