# What is the correct definition for completeness in d-separation in directed graphical models?

I was reading Koller's book of probabilistic graphical models and in section 3.3.2 she discusses what properties should hold for d-separation as a method for determining independence. She tries to motivate that hopefully, separation should be sound and complete. Sound in the sense that, if we have that two nodes $X$ and $Y$ are d-separated given some set of nodes in the graph $\vec{Z}$, then we are guaranteed that they are in fact conditionally independent given $\vec{Z}$. Complete in the sense that hopefully, d-separation detects all possible independencies. She tries to make those terms rigorous by providing some explanations and definitions and I wish to ask about the definitions she provides for completeness.

First define that $I(P)$ is the set of all independencies that hold in distribution P and similarly, $I(G)$ are all independencies that hold in graph G. Also, let the notation $d-sep_G(X;Y \perp \vec{Z})$ be defined as; X is d-separated from Y in graph $G$ given (the set of nodes) $\vec{Z}$.

In that section (3.3.2) she defines the following notion:

A distribution P is faithful to G if, whenever $(X \perp Y | \vec{Z}^{\,}) \in I(P)$, then $d-sep_G(X;Y \perp \vec{Z})$. In other word, any independence in P is reflected in the d-separation properties of the graph.

The following is the important part. In trying to define for completeness, she suggests the following notion of completeness:

1) For any distribution P that factorizes over $G$, we have that P is faithful; if X and Y are not d-separated given $\vec{Z}$ in G, then X and Y are dependent in all distribution P that factorize over G.

However, it ends up that this is actually not a good definition for completeness (for some reason which I don't completely understand yet but is not the main issue in this question) and decides to define a weaker definition. The definition is instead:

2) If $(X \perp Y \mid \vec{Z})$ in all distributions P that factorize over $G$, then $d-sep_G(X;Y \mid \vec{Z})$. And the contrapositive: if $X$ and $Y$ are not d-separated given $\vec{Z}$ in G, then X and Y are dependent in some distribution P that factorizes over G

So this is the main issue with my question. Even though she provides two supposedly different definitions, I fail to appreciate what is the true difference between the two. It seems to me that they both say the exact same thing (I know, they don't because she says that the second is "weaker"), but I wanted to understand the difference between the two definition and why the second one is weaker.

Maybe the a good way to approach this problem is by instead of having English sentences describing the definitions, if instead we could express the definitions compactly using only quantifiers and mathematical notation. In this picture, BC has a positive direct effect on DVT, but also a negative indirect effect via Pregnancy (BC reduces the risk of pregnancy, and pregnancy increases the risk of DVT). So the total effect of BC on DVT depends on the relative weights of these pathways. Notably, if $\gamma = \alpha\beta$, then the pathways perfectly cancel out, and BC is independent of DVT.
So there is a set of parameterizations of this model where the distribution $P$ is "unfaithful" to the graph: it has an extra independence that we don't get from the graphical structure. However there are plenty of distributions $P'$ that do include the dependence (for example, any linear model where $\gamma \neq \alpha\beta$).
The $d$-separation and faithfulness principles are quite different. $d$-separation tells you all the independence relations that are entailed by the graph; it doesn't say anything about additional independences that might hold. Faithfulness says that the independences entailed by the graphical factorization are the only independences that hold. I hope this example helps make it concrete.