THEOREM 1

The following is a sketch for the proof of Theorem 1; a more detailed proof is available [8].

Consider three arbitrary disjoint sets of variables in the network, $\tilde{X}$, $\tilde{Y}$ and $\tilde{Z}$, such that $\tilde{X}$ is d-separated from $\tilde{Z}$ given $\tilde{Y}$. Take the type-1 extension $K(\tilde{X}, \tilde{Y}, \tilde{Z})$ and obtain, by conditionalization, $K(\tilde{X}\vert\tilde{Y},\tilde{Z})$ and $K(\tilde{X}\vert\tilde{Y})$. Call $\mbox{ext}K$ the set of extreme points of K.

Given any function $f(\tilde{X})$ solely of $\tilde{X}$, obtain its lower expectation $\underline{E}[f(\tilde{X})\vert\tilde{Y}, \tilde{Z}] = \min_{p \in \mbox{\foo... ... \sum_{\tilde{X}} f(\tilde{X}) p(\tilde{X}\vert\tilde{Y}, \tilde{Z}) \right).$ The minimum is attained at an extreme point of the type-1 extension. Because every such extreme point satisfies Expression (1), $p(\tilde{X}\vert\tilde{Y}, \tilde{Z}) = p(\tilde{X}\vert\tilde{Y})$ for these points (by d-separation), and the lower expectation is equal to $\underline{E}[f(\tilde{X})\vert\tilde{Y}]$.

Because a lower expectation uniquely defines a convex set of distributions (Section 2.2), the lower expectation $\underline{E}[f(\tilde{X})\vert\tilde{Y}]$ uniquely defines $K(\tilde{X}\vert\tilde{Y})$ and the lower expectation $\underline{E}[f(\tilde{X})\vert\tilde{Y}, \tilde{Z}]$ uniquely defines $K(\tilde{X}\vert\tilde{Y},\tilde{Z})$. Because both lower expectations are equal for arbitrary f, the underlying credal sets are the same. This argument guarantees that $\tilde{Z}$ is irrelevant to $\tilde{X}$ given $\tilde{Y}$; the same argument proves that $\tilde{X}$ is irrelevant to $\tilde{Z}$ given $\tilde{Y}$. So $\tilde{X}$ is independent of $\tilde{Z}$ given $\tilde{Y}$.