

![0_image_0.png](0_image_0.png)

not formally part of the graph, but are shown for clarity.

At this point we invoke the fact that the constraints of are not arbitrary but

X2 X3 X1

X3 X2 X1

$$\begin{array}{r l r l}{U_{1}}&{{}}&{}&{}&{}\\ {X_{3}}&{}&{X_{1}}&{}&{}\\ {X_{2}}&{}&{X_{1}}&{}&{}\\ {\ }&{}&{}&{}&{}\\ {U_{4}}&{}&{}&{}\\ {U_{5}}&{}&{}&{}\\ {X_{2}}&{}&{X_{4}}&{}&{X_{5}}\ \cdot\ X_{7}\\ {\ }&{}&{}&{}\\ {X_{2}}&{}&{X_{4}}&{}&{X_{5}}\ \cdot\ X_{6}\end{array}$$
$$U_{i}$$

Figure 1: Graphical structure and equations for the counterexample. All variables take

![0_image_1.png](0_image_1.png)

values in f ; g The Ui are independent, with equal probabilities for and 1.

Addition and multiplication is done modulo 2. The Ui and the dotted arrows are
X2 X4 X5 implies that X2 U4 U5 from which it follows that X3 U4 U5 U1 since X1 U1 Let us now consider whether or not X4 is conditionally independent of X5 given X2 We can see that X4 and X5 are d-separated by X2 since in step (1) above, we will delete X6 and X7 and all the edges connecting to them, leaving no path from X4 to X5 However, given any value for X2 the variables X4 and X5 are in fact dependent. As seen above, any set of values for the Xi satisfying the equations must be such that X2 X4 X5 0. Hence, if X2 0, then it must be that X4 X5 and if instead X2 1, then it must be that X4 X5 1. Conditional on value for X2 we thus see that X4 is determined by X5 showing that they are not conditionally independent. The problem appears to arise because even though specifying values for all the Ui uniquely determines values for all the Xi specifying value for U1 alone leaves two sets of values for X1; X2; X3 that satisfy the equations associated with these variables, even though only one set of values will satisfy the entire set of equations. Which values for

X1; X2; X3 are part of the overall solution depends on the value of U4 U5 and this
induces dependence between X4 U4 and X5 U5 when the value of X2 is known.
The removal of part of the graph in step (1) of the procedure for determining d-separation

eliminates any possibility of accounting for this dependence.

The problem with Pearl and Dechter's proof appears connected with this. They say,

are functional, namely, for every values of the parents of xi and ui there is

$$\begin{array}{r l}{U_{4}}&{{}}&{U_{5}}\\ {}&{{}}&{X_{2}}\\ {}&{{}}&{d}\end{array}$$
$$U_{4}\qquad\qquad X_{5}$$
$$\mathbf{\dot{\bar{5}}}$$
$${X_{4}}$$
