THEOREM 2

First note that the linear fractional program in the statement of the theorem is identical to the following program:

$$\overline{p}\left( X_q\vert E \right) = \max \left( \frac{ ... ...um_{X_i \in (\tilde{X} \backslash E)} p(\tilde{X})} \right),$$ (7)

subject to constraints (5), $\sum_{\tilde{S}} p(\tilde{S}) = 1$ and $p(\tilde{X}) = q(\tilde{W}\vert\tilde{S}) p(\tilde{S})$, where

$$q(\tilde{W}\vert\tilde{S}) = \prod_{W_i \in \tilde{W}} q(W_i\vert\mbox{pa}(W_i)).$$ (8)

Note that $q(\tilde{W}\vert\tilde{S})$ is the unique joint distribution for $\tilde{W}$ given $\tilde{S}$. Uniqueness is guaranteed by the fact that the variables in $\tilde{W}$ form a Bayesian network: (1) irrelevance is equal to independence in standard Bayesian networks; (2) Lemma 2 guarantees that all irrelevance conditions are valid when restricted to the network of $\tilde{W}$; (3) independence of a variable from its nondescendants given its parents characterizes a unique Bayesian network [22].

The strategy of the proof is to demonstrate that the linear program expressed by (7) subject to constraints (5), (8) and $\sum_{\tilde{S}} p(\tilde{S}) = 1$, is identical to program (3) subject to $C_l[p(X_i\vert\mbox{nd}(X_i))]$ and the unitary constraint.

Start from program (3). Uniqueness of $q(\tilde{W}\vert\tilde{S})$ leads to constraints:

$$p(\tilde{W}\vert\tilde{S}) = q(\tilde{W}\vert\tilde{S}),$$

which are equivalent to the constraints summarized by Expression (8). Use this equality in Expressions $C_l[p(X_i\vert\mbox{nd}(X_i))]$ and the unitary constraint. Expression $\sum_{\tilde{S}} p(\tilde{S}) = 1$ is immediately obtained from the unitary constraint. For constraints $C_l[p(X_i\vert\mbox{nd}(X_i))]$, divide $\tilde{W}$ in two sets of variables; $\tilde{W}'$ contains variables in $\tilde{W}$ that are nondescendants of X_i, and $\tilde{W}''$ contains variables in $\tilde{W}$ that are descendants of X_i. Constraints $C_l[p(X_i\vert\mbox{nd}(X_i))]$ become:

$$\sum_{j=1}^{\vert\hat{X_i}\vert} \left( \gamma_{ijkl} \su... ...\tilde{W}') q(\tilde{W}'\vert\tilde{S}) p(\tilde{S}) \right)$$

$$- \gamma_{i0kl} \sum_{ \tilde{X} \backslash \mbox{nd}(X_i)... ...\tilde{W}') q(\tilde{W}'\vert\tilde{S}) p(\tilde{S}) \leq 0.$$

The summations involve all variables in $\tilde{W}''$, so these variables can be summed out. Variables in $\tilde{W}'$ are fixed and make no reference to X_i or any of its descendants, so they can be taken out of the summation and cancelled. These operations reduce the inequality above to constraint (5). The only situation where this cancellation cannot occur is when a node has no nondescendants; in this case, all other nodes are descendants of the node and are summed out so the result holds. This proves that program (7) subject to (5), (8), and $\sum_{\tilde{S}} p(\tilde{S}) = 1$, is identical to program (3) subject to $C_l[p(X_i\vert\mbox{nd}(X_i))]$ and the unitary constraint.