
$$\mathbf{M}^{\prime}$$
$$d$$ $$X_{1},\,\cdot\,\cdot\,,\,X_{n}$$
$$\begin{array}{c}{{U_{1},\,.\,.\,.\,,\,U_{n}}}\\ {{X_{1},\,.\,.\,.\,,\,X_{n}}}\end{array}$$

$$X_{1},\,\cdot\,\cdot\,,\,X_{n}$$

Neal associated with non-ancestors of W do not constrain the permitted values of solution for xi This implies that, for any set W of variables, the equations

The example here shows that the equations involving non-ancestors of W can indeed con-
Institute for Robotics and Intelligent Systems.

$$\mathrm{fl}$$
Judea Pearl (personal communication) has suggested that the d-separation criterion

can be salvaged by requiring not only that U1; : : : ; Un uniquely determine X1; : : : ; Xn but
W. . .

strain the permitted values for W

$$X_{i}$$
$$X_{i}$$
$$X_{1},\,\cdot\,\cdot\,,\,X_{n}$$

$$s o m\,e$$
$$\mathrm{ffi}$$
$$\begin{array}{c c c}{{X_{6}}}&{{}}&{{}}&{{X_{7}}}\end{array}\mathrm{~fl}$$
also that this unique solution for X1; : : : ; Xn can be obtained by procedure in which the
Xi are updated in accordance with the causal structure of the network. In such casual
dynamical procedure, each Xi is repeatedly replaced by the value computed for it from the
corresponding Ui and the current values of its parents, according to the equation for that
Xi until stable state is reached. The 
ow of information in such procedure follows the
direction of the arrows in the network. Consequently, nodes that are not ancestral to any

node of interest can have no in
uence on these nodes, justifying their elimination in step

(1) of the procedure for determining d-separation.

In general, whether or not such dynamical procedure eventually nds the solution for

X1; : : : ; Xn may depend on whether the Xi are updated simultaneously or sequentially, and
if they are updated sequentially, on the order of these updates. For present purposes, it is

sucient that some updating scheme exist that is guaranteed, for any values of U1; : : : ; Un

to lead to the unique solution, starting with any initial values for X1; : : : ; Xn If such
an update order exists, d-separation will imply conditional independence. In the example

above, any updating order will for some initial state lead to cyclic behaviour in which the

values of X6 and X7 
ip back and forth, so the example does not satisfy this stronger
condition.

One should note that the example in this note does not invalidate the result of Spirtes

(1995) that d-separation can be used to determine conditional independence in linear networks of normally distributed variables even if they contain cycles. In the same paper,

Spirtes also gave counterexample showing that d-separation need not imply conditional

independence in non-linear networks of continuous random variables that contain cycles.

This problem cannot be avoided by simply discretizing the continuous variables, as the

problem reappears in the form of non-existence or non-uniqueness of solutions. This note

shows that in non-linear networks of discrete variables stronger condition than uniqueness

is required for d-separation to be valid. Although such stronger condition involving causal

dynamics can be seen as natural, the need to verify this stronger condition does reduce

the attractiveness of networks with cycles as way of formalizing causal situations with

feedback.

$$d$$

## Acknowledgments

thank Peter Spirtes and Thomas Richardson for helpful comments. This work was supported by the Natural Sciences and Engineering Research Council of Canada and by the
