RELEVANT LEMMAS

The following result is used in Section 5.4:

Lemma 1   If a joint distribution satisfies constraints $C_l[p(X_i\vert\mbox{nd}(X_i))]$, then it satisfies constraints $C_l[p(X_i\vert\mbox{pa}(X_i))]$.

To prove this result, take $\tilde{W}(X_i) = \emptyset$ in the following lemma.

Lemma 2   Consider a joint distribution that satisfies constraints $C_l[p(X_i\vert\mbox{nd}(X_i))]$, and for every node X_i, $\tilde{W}(X_i)$ is a subset of $\mbox{nd}(X_i)$ that does not overlap with the parents of X_i. Then the following constraints are also satisfied:

$$\sum_{j=1}^{\vert\hat{X_i}\vert} \gamma_{ijkl} p(X_i = X_{ij}\vert[\mbox{pa}(X_i)]_k, \tilde{W}(X_i)) \leq \gamma_{i0kl}.$$ (6)

Sketch of proof. Consider an arbitrary joint distribution satisfying constraints $C_l[p(X_i\vert\mbox{nd}(X_i))]$. Denote the set $(\mbox{nd}(X_i) \backslash \{ \mbox{pa}(X_i), \tilde{W}(X_i) \})$ by $\tilde{W}'(X_i)$. Obtain by marginalization the distribution of $\tilde{W}'(X_i)$, $p(\tilde{W}'(X_i))$.

Select all constraints that are repetitions of a single original constraint for fixed $[\mbox{pa}(X_i)]_k$. These constraints are all identical, except that values of $\tilde{W}(X_i)$ and $\tilde{W}'(X_i)$ vary across constraints. Multiply every one of these constraints by the appropriate value of $p(\tilde{W}'(X_i))$, and add all constraints that refer to a particular value of $\tilde{W}(X_i)$; constraints (6) are then obtained after algebraic manipulations.