If you want to skip the backstory and jump right to the rules to follow to determine whether nodes in a DAG are independent, go to The Find.

## I recently had to do a homework on Bayesian Networks and determine whether pairs of nodes were conditionally independent to a set of nodes. Prior to this homework, in an introductory course, I had heard the terms ⏪ Prelude

**d-separation**and

**d-connection**thrown around and knew they had something to do with independence. Perhaps because it was introductory course, I hadn’t bothered actually looking into what they meant back then. So, as I often do, I set about trying to find info - outside course notes - that would untangle the link between

**d-connection**and

**blocked paths**.

## 🔍 The Search

After a bit of digging, I stumbled upon an online website that seemed to be, from its title, the ultimate won’t-waste-your-time and succinct resource: D-separation without tears.

Unfortunately, before I even had the chance to shed any tears, I realized that the resource wasn’t all that concise. So I continued my search, slogging, plodding and plowing until, at last, I found two sets of slides that had all I needed to write the meat of this post. Check out the References section to find the links to them.

## 📖 The Find

Here’s a condensed summary of the important information I dug up. It assumes that the reader knows what nodes, edges and conditional independence are.

**Definition 1.**A

**path**is a sequence of

*distinct*edges connecting two nodes.

**Remark 1.** For concision, paths are often represented as sequences of nodes,
instead of sequences of edges.

**Definition 2.**Let $P$ be a path. A node is said to be a

**collider**in the path $P$ if it has two incoming edges in $P$ .

**Definition 3.**Let $P$ be a path. A node is said to be a

**non-collider**in the path $P$ if it is not a collider in the path.

**Example 1.** In the graph just above,

- $E$ is a collider in the path $(D,B,E,C)$ because it has two incoming edges $BE$ and $CE$.
- $C$ is a collider in the path $(A,C,D)$ because it has two incoming edges $AC$ and $DC$.
- $C$ is
*not*a collider (it is a non-collider) in the path $(A,D,C)$. - $(A,C,E,B)$ and $(A,D,B)$ are paths between $A$ and $B$ but $(A,D,B,D,B)$ is not.

**Definition 4.**A path $P$ between two nodes is said to be

**blocked**by a set of nodes $Ω$ if at least one the following conditions is satisfied:

- there is a collider in the path $P$ such that neither the collider nor any of its descendants is in $Ω$.
- there is a non-collider in the path $P$ that belongs to $Ω$.

**Example 2.**Let $$$Ω={C}$ . In Network Graph 1 , the path $P=(A,C,E)$ between $A$ and $E$ is blocked by $Ω$ because $C$ is a non-collider in the path that belongs to $Ω$ , which satisfies condition 2.

**Example 3.** Let $Ω=∅$. In Network Graph 1, the path $P=(D,B,E)$ is not blocked by $Ω$ because neither condition 2 can be met, since
$Ω$ is empty, nor can condition 1 be met, since none of the nodes in the
path is a collider.

Now that you’ve hopefully understood the first four definitions, you’re ready to apply the rule to determine whether nodes are conditionally independent.

**Theorem 1.**Given three sets of nodes, $X$ , $Y$ , $C$ , if all paths from any node of $X$ to any node of $Y$ are blocked by $C$ , then $X⊥⊥Y∣C$ .

**Remark 2.** The theorem implies that testing for conditional dependence, that is
$X⊥⊥Y∣C$, only requires that one path be “not” blocked.

**Remark 3.** If there is no set of nodes conditioned on, then $C=∅$
in the theorem.

The only piece of the puzzle left is to understand d-separation and d-connection. Here are their definitions.

**Definition 5.**Let $A$ and $B$ be two nodes and $C$ , a set of nodes. $A$ and $B$ are said to be

**d-separated**given $C$ if and only if all paths between $A$ and $B$ are blocked by $C$ . Equivalently, in this case, by Theorem 1, $A⊥⊥B∣C$ .

**Definition 6.**Let $A$ and $B$ be two nodes and, $C$ , a set of nodes. $A$ and $B$ are said to be

**d-connected**given $C$ if a path between $A$ and $B$ is not blocked by $C$ . Equivalently, in this case, by Theorem 1, $A⊥⊥B∣C$ .

## 🏋️ Exercises

The following exercises have to do with the network graph below. Please note that to make the notation lighter, I drop the curly braces surrounding sets.

**False.** There are no nodes nodes conditioned on. Therefore, any path
between $B$ and $E$ must satisfy the first condition to be blocked. Consider
the path $P=(B,A,E)$. Since there are no colliders in $P$, condition 1
cannot be satisfied, by default. Hence, since just this one path is blocked,
then $B⊥⊥E$.

**True.** Again, it’s simply a matter of going through each path and
verifying whether it’s blocked. The paths are:

- $(B,A,E)$: The path is blocked because $A$ is a non-collider and it is conditioned on so condition 2 is satisfied.
- $(B,F,I,E)$: The path is blocked because $I$ is a collider in the path that satisfies condition 1.
- $(B,F,G,J,I,E)$: The path is blocked because $J$ is a collider in the path that satisfies condition 1.
- $(B,C,D,H,G,J,I,E)$: The path is blocked because $J$ is a collider in the path that satisfies condition 1.
- $(B,C,D,H,G,F,I,E)$: The path is blocked because $I$ is a collider in the path that satisfies condition 1.

**True.** Same reasoning as for Exercise 2.

**True.** Same reasoning as for Exercise 2.

**False.** The path $(A,E,I)$ is not blocked.

**False.** The path $(A,B,F,I)$ is not blocked.

**True.** All paths are blocked. The paths are:

- $(B,F,G)$: Blocked because $F$ is a non-collider that is conditioned on so condition 2 is satisfied.
- $(B,F,I,J,G)$: Blocked because $J$ is a collider that satisfies condition 1.
- $(B,A,E,I,J,G)$: Ditto.
- $(B,A,E,I,F,G)$: Blocked because $F$ is a non-collider that is conditioned on so condition 2 is satisfied.
- $(B,C,D,H,G)$: Blocked because $H$ is a collider that satisfies condition 1.

**False.** The path $(B,A,E,I,J,G)$ is not blocked.

Invert the edge between B and F.