Actual d-separation without tears

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.

⏪ Prelude

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 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.

Network Graph 1

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 $A C$ and $D C$ .
$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 $Ω = \emptyset$ . 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 \neq ⊥ ⊥ Y ∣ C$ , only requires that one path be “not” blocked.

Remark 3. If there is no set of nodes conditioned on, then $C = \emptyset$ 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 \neq ⊥ ⊥ 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.

Network Graph 2

Actual d-separation without tears

⏪ Prelude

🔍 The Search

📖 The Find

🏋️ Exercises

📑 References

Table of Contents