"Given a probability distribution $P(x_1, \dots, x_n)$ and any ordering d of the variables, the DAG(directed acyclic graph) created by designating as parents of $X_i$ any minimal set П$_{X_i}$ of predecessors satisfying $$P(x_i|П_{X_i}) = P(x_i|x_1, \dots, x_{i-1}), П_{X_i}\subseteq \{X_1, \dots, X_{i-1}\}$$ is a Bayesian network of P."

This text is a Corollary 3 in Chapter 3 from the book "Probabilistic Reasoning in Intelligent Systems".

I do not see how it is correct. Consider a simple network $X_1 \to X_2$ and ordering $d=\{X_2, X_1\}$. This ordering will induce a network that consist from two disconnected nodes $X_1$ and $X_2$. From this network follows that $X_1$ and $X_2$ are independent, even though they are.

Is this Corollary wrong or I am missing something?

PS Essential property of a Bayesian network for a probability distribution P is that it reflects independent relations (I-map of P). If two sets X, Y of variables are d-separable given set Z then X, Y are independent according to P given Z. In my example with two variables d-separable is just whether there is a path between variables or not (Z is empty set).

This Corollary is for Theorem 9 of the book:

[Verma 1986] Let M be any semi-graphoid. If D is a boundary DAG of M relative to ANY ordering d, then D is a minimal I-map of M.

Note that any probability distribution is a semi-graphoid.


1 Answer 1


The ordering is $\{X_2,X_1\}$ will produce a network $X_2 \to X_1$ because $X_1,X_2$ are dependent on each other. The two nodes can't be disconnected because they aren't independent. Both networks are valid but it's better if the ordering has the "causes" first and the "symptoms" last.

For a good example of what can happen with different orderings, see pages 38,39 of these notes.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .