# Impossible DAGs

$$\newcommand{\ci}{\perp\!\!\!\perp}$$ Although a probabilistic directed acyclic graph (DAG) can only be inferred from conditional independence (CI) properties of the variables up to a Markov equivalence class, are there CI properties which cannot be represented as a DAG?

Maybe answering my question, in the paper "Beware of the DAG!", NIPS 2008, from AP Dawid, the author says:

"It is important to note that, for given variable set $$\mathscr{V}$$, the collection of CI properties $$\mathscr{C}$$ that can be represented by a DAG is very special. Thus with $$\mathscr{V} =\{X,Y,Z\}$$, the pair of properties $$\{X \ci Y,X\ci Y\ |\ Z\}$$ has no DAG representation."

Is that so? What about a DAG without edges, wouldn't it satisfy those properties?

• Since the D in DAG means directed, a 'DAG' without arrows is not a DAG. – Juho Kokkala Jan 23 '15 at 16:35
• Well, you could put an arrow between X and Z or Y and Z, if you'd like... In any case, one could argue the trivial graph is a directed acyclic graph, since there are no cycles and every edge is directed (it is also undirected, but that's the beauty of zero). – Leo Azevedo Jan 23 '15 at 16:40
• By 'a DAG without arrows' in the final sentence, do you mean a DAG without edges at all? – Juho Kokkala Jan 23 '15 at 16:55
• Corrected 'DAG without arrows' to 'DAG without edges' – Leo Azevedo Jan 23 '15 at 17:32
• @Alexis: I agree. My previous comments stems from the original wording of the question, 'DAG without arrows'. I misinterpreted that to mean 'a graph with undirected edges'. – Juho Kokkala Jan 23 '15 at 19:28

$$\newcommand{\ci}{\perp\!\!\!\perp}$$ Based on comments, I assume by 'a DAG without arrows' you mean the DAG with no edges.
The graph with no edges indeed has the conditional independence properties $$X \ci Y$$ and $$X\ci Y\ |\ Z$$. However, the point is that there is no DAG that implies exactly those conditional independence properties. The trivial DAG also implies other conditional independence properties, for example $$Y \ci Z$$, and thus it is not a DAG representation of the pair of properties $$\{X \ci Y,X\ci Y\ |\ Z\}$$.