d-separation

Given a directed graph \(G = (\mathbf{V},\mathbf{E})\), a path \(P\) between \(V_1,V_2 \in \mathbf{V}\) is blocked by a set \(\mathbf{B}\subset \mathbf{V}\) if:

• \(\exists\) non-collider \(B\) in the path \(P\) such that \(B \in \mathbf{B}\).
• \(\exists\) collider \(B\) in the path \(P\) such that \(B \notin \mathbf{B}\).

Sets of variables \(\mathbf{X},\mathbf{Y} \subset \mathbf{V}\) are d-separated by \(\mathbf{B}\), sometimes denote \(\mathbb{I}_G(\mathbf{X},\mathbf{Y}|\mathbf{B})\) if all paths between \(\mathbf{X},\mathbf{Y}\) are blocked by \(\mathbf{B}\).

The notion of d-separation is important since they allow us to identify all conditional independencies that hold in Bayesian Networks (BNs), namely given a BN \((G,\mathbb{P})\), the distribution \(\mathbb{P}\) entails all and only all the conditional independencies that are identified by d-separation in \(G\) (Theorem 2.1 (Neapolitan and others 2004)).