Day 49: d-Separation · Math for Causal Inference

Theory

Blocking a path

Let $\mathbf Z$ be a set of conditioned variables. A path between $X$ and $Y$ is blocked by $\mathbf Z$ if it contains at least one node $M$ such that

$M$ is the middle of a chain ( $\to M \to$ ) or fork ( $\leftarrow M \to$ ) and $M \in \mathbf Z$ , or
$M$ is a collider ( $\to M \leftarrow$ ) and neither $M$ nor any descendant of $M$ is in $\mathbf Z$ .

A path that is not blocked is open (or active). Open paths carry association.

d-separation

$X$ and $Y$ are d-separated by $\mathbf Z$ , written $(X \perp\!\!\!\perp Y \mid \mathbf Z)_G$ , if every path between them is blocked by $\mathbf Z$ . Otherwise they are d-connected.

The global Markov property

If $P$ factorises according to $G$ (Day 47), then

(X \perp\!\!\!\perp Y \mid \mathbf Z)_G \;\Longrightarrow\; X \perp\!\!\!\perp Y \mid \mathbf Z \text{ in } P.

d-separation is sound (it never claims a false independence) and, under faithfulness, complete (every independence in $P$ is a d-separation). The local Markov property is the special case "parents separate a node from its other non-descendants".

Recipe

List every path between $X$ and $Y$ (ignoring arrow directions, no repeated nodes).
For each path, classify each interior node as chain, fork or collider.
The path is open only if every chain/fork middle is outside $\mathbf Z$ and every collider is in $\mathbf Z$ or has a descendant in $\mathbf Z$ .
$X$ and $Y$ are d-separated if no path is open.

Software does this efficiently (the "Bayes-ball" algorithm, or networkx.is_d_separator). The lab lets you click a conditioning set and watch paths open and close.

Non-monotonicity

Adding a variable to $\mathbf Z$ can open a path (if it is a collider or a collider's descendant) as well as close one. "Control for more" is not automatically safer.

Markov blanket

The Markov blanket of $V$ is its parents, children and the other parents of its children. Given its blanket, $V$ is d-separated from every other variable: the blanket is the smallest set worth knowing to predict $V$ .

Part 1 · Warm-up

Exercises 1–5 use this DAG: $Z \to X$ , $Z \to W$ , $W \to Y$ , $X \to M$ , $M \to Y$ , $X \to C$ , $Y \to C$ .

Exercise 1 · List the paths

List every path between $X$ and $Y$ and classify the interior nodes.

Show solution

Step 1. $X \to M \to Y$ : $M$ is a chain middle.

Step 2. $X \leftarrow Z \to W \to Y$ : $Z$ is a fork, $W$ a chain middle.

Step 3. $X \to C \leftarrow Y$ : $C$ is a collider.

Answer: three paths.

Exercise 2 · Nothing conditioned

Are $X$ and $Y$ d-separated by the empty set?

Show solution

Step 1. Path 1: chain through $M$ , not conditioned: open.

Step 2. One open path suffices.

Answer: no, they are d-connected. (Path 2 is also open; path 3 is blocked by the unconditioned collider.)

Exercise 3 · Conditioning on $M$ and $W$

Are $X$ and $Y$ d-separated by $\{M, W\}$ ?

Show solution

Step 1. Path 1: $M$ conditioned, chain: blocked.

Step 2. Path 2: $W$ conditioned, chain: blocked.

Step 3. Path 3: collider $C$ not conditioned and has no descendants: blocked.

Answer: yes, d-separated.

Exercise 4 · Adding $C$

Are $X$ and $Y$ d-separated by $\{M, W, C\}$ ?

Show solution

Step 1. Paths 1 and 2 stay blocked.

Step 2. Path 3: the collider $C$ is now conditioned: open.

Answer: no. Adding $C$ re-connects $X$ and $Y$ (non-monotonicity).

Exercise 5 · A different pair

Is $Z$ d-separated from $M$ by $\{X\}$ ?

Show solution

Step 1. $Z \to X \to M$ : chain at $X$ , conditioned: blocked.

Step 2. $Z \to W \to Y \leftarrow M$ : collider $Y$ ; neither $Y$ nor its descendant $C$ is conditioned: blocked.

Step 3. $Z \to W \to Y \to C \leftarrow X \to M$ : collider $C$ not conditioned: blocked (also $X$ is a fork middle, conditioned).

Step 4. $Z \to X \to C \leftarrow Y \leftarrow M$ : $X$ is a chain middle, conditioned: blocked.

Answer: yes, every path is blocked.

Part 2 · Proofs

Exercise 6 · Neighbours are never separated

Prove that if $X \to Y$ is an edge, no set $\mathbf Z$ (excluding $X, Y$ ) d-separates them.

Show solution

Step 1. The one-edge path $X \to Y$ has no interior nodes.

Step 2. Blocking requires an interior node satisfying condition 1 or 2; there is none.

Step 3. So this path is open for every $\mathbf Z$ , and $X, Y$ are d-connected. $\blacksquare$

This is why missing arrows, not present ones, carry the testable content of a DAG.

Exercise 7 · Local Markov from d-separation

Prove that every node $V$ is d-separated from any non-descendant $N$ (not a parent) by $\operatorname{pa}(V)$ .

Show solution

Step 1. Take any path from $V$ to $N$ . Case A: it starts with an edge into $V$ , $V \leftarrow P$ , so $P$ is a parent.

Step 2. At $P$ the path continues either $\leftarrow P \leftarrow$ (chain) or $\leftarrow P \to$ (fork). $P$ cannot be a collider, because the edge $P \to V$ points out of it. $P \in \operatorname{pa}(V)$ is conditioned, so the path is blocked.

Step 3. Case B: the path starts $V \to C_1$ . Follow it while the arrows keep pointing forward: $V \to C_1 \to C_2 \to \dots$ . All these nodes are descendants of $V$ .

Step 4. $N$ is not a descendant, so the arrows must reverse somewhere: there is a collider $C_k$ with $\to C_k \leftarrow$ , and $C_k$ is a descendant of $V$ .

Step 5. Neither $C_k$ nor its descendants can be parents of $V$ (that would create a cycle). So the collider is unconditioned with no conditioned descendant: blocked. $\blacksquare$

Exercise 8 · The Markov blanket

Prove that $V$ is d-separated from every node outside its Markov blanket $\mathbf B$ (parents, children, children's other parents) given $\mathbf B$ .

Show solution

Step 1. Paths leaving through a parent $P$ : as in Exercise 7, $P$ is a conditioned chain or fork middle: blocked.

Step 2. Paths leaving through a child $C$ and continuing $V \to C \to$ : $C$ is a conditioned chain middle: blocked.

Step 3. Paths continuing $V \to C \leftarrow Q$ : $C$ is a conditioned collider, so open at $C$ ; but then $Q$ is a co-parent, in $\mathbf B$ .

Step 4. At $Q$ the path continues $\leftarrow Q \leftarrow$ or $\leftarrow Q \to$ (not a collider, since $Q \to C$ points out). $Q$ is conditioned: blocked.

Step 5. Every path is blocked. $\blacksquare$

Exercise 9 · No common ancestor, no association

Prove that if $X$ and $Y$ have no common ancestor (counting each node as its own ancestor), they are d-separated by the empty set.

Show solution

Step 1. With $\mathbf Z = \varnothing$ , a path is open only if it has no colliders.

Step 2. A collider-free path has at most one node where the arrows point away on both sides, otherwise there would be a collider between two such nodes. Call that node $S$ (possibly an endpoint).

Step 3. From $S$ , both halves of the path are directed paths towards $X$ and towards $Y$ , so $S$ is a common ancestor.

Step 4. There is none, so no path is open, and $X, Y$ are d-separated. $\blacksquare$ (Reichenbach's principle: dependence requires a causal link or a common cause, absent selection.)

Exercise 10 · More control can hurt

Give a three-node DAG in which $X \perp\!\!\!\perp Y$ is implied but $X \perp\!\!\!\perp Y \mid W$ is not, and one in which the reverse holds.

Show solution

Step 1. Collider $X \to W \leftarrow Y$ : the only path is blocked given $\varnothing$ and open given $W$ .

Step 2. Chain $X \to W \to Y$ (or fork $X \leftarrow W \to Y$ ): the only path is open given $\varnothing$ and blocked given $W$ .

Answer: d-separation is not monotone in the conditioning set; which variables to condition on depends on the graph, not on "more is better". $\blacksquare$

Part 3 · Applied

Exercise 11 · Two stories about microcredit

DAG 1: education $E \to$ loan $L \to$ income $I$ . DAG 2: $E \to L$ , $E \to I$ , $L \to I$ . Which testable independence separates them? In survey data, the regression of income on loans and education gives a large, precise education coefficient. Which DAG survives?

Show solution

Step 1. DAG 1 implies $E \perp\!\!\!\perp I \mid L$ (chain blocked at $L$ ).

Step 2. DAG 2 has the edge $E \to I$ , so by Exercise 6 no independence between $E$ and $I$ is implied.

Step 3. In a linear model, $E \perp\!\!\!\perp I \mid L$ means a zero education coefficient once loans are included.

Answer: a large, precise coefficient rejects DAG 1; DAG 2 survives (education affects income other than through loans).

Exercise 12 · Pollution, allergies and the emergency room

Air pollution $P \to$ asthma attack $A \leftarrow$ allergy $G$ , and $A \to$ emergency visit $E$ . Pollution and allergy have no common cause. Is $P \perp\!\!\!\perp G$ implied? Is $P \perp\!\!\!\perp G \mid E$ ? What does this mean for a study using only emergency-room records?

Show solution

Step 1. One path: $P \to A \leftarrow G$ , a collider at $A$ .

Step 2. Given nothing: blocked, so $P \perp\!\!\!\perp G$ .

Step 3. Given $E$ : $E$ is a descendant of the collider, so the path opens: not d-separated.

Answer: among ER patients, pollution and allergies will look negatively related (an attack on a clean-air day is more likely to be allergic). ER-only data condition on a collider's descendant.

Exercise 13 · School meals

A DAG for a school-meals programme: household income $I \to$ meals $M$ , $I \to$ attendance $A$ , $M \to$ nutrition $N \to$ test score $T$ , $A \to T$ , rainfall $R \to A$ . Decide: (a) $M \perp\!\!\!\perp R$ ? (b) $M \perp\!\!\!\perp R \mid T$ ? (c) $M \perp\!\!\!\perp T \mid \{N, I\}$ ?

Show solution

Step 1. (a) Paths $M$ – $R$ : $M \leftarrow I \to A \leftarrow R$ (collider $A$ ) and $M \to N \to T \leftarrow A \leftarrow R$ (collider $T$ ). Both blocked: yes.

Step 2. (b) Conditioning on $T$ opens the collider in the second path: $M \to N \to T \leftarrow A \leftarrow R$ is open. Also $T$ is a descendant of $A$ , opening the first path. Not d-separated.

Step 3. (c) Paths $M$ – $T$ : $M \to N \to T$ (blocked by $N$ ) and $M \leftarrow I \to A \to T$ (blocked by $I$ , a fork). Yes.

Answer: yes, no, yes. Statement (c) is testable: given nutrition and income, meals should not predict test scores.

Exercise 14 · Checking an instrument

The Vietnam draft lottery $Z$ affects military service $D$ , which affects later earnings $Y$ ; unobserved motivation $U$ affects both $D$ and $Y$ . (a) Is $Z \perp\!\!\!\perp U$ implied? (b) Is $Z \perp\!\!\!\perp Y \mid D$ implied? (c) Why is "regress earnings on the lottery, controlling for service" a mistake?

Show solution

Step 1. (a) Path $Z \to D \leftarrow U$ has a collider at $D$ : blocked. Yes, $Z \perp\!\!\!\perp U$ (the lottery is random).

Step 2. (b) Paths $Z$ – $Y$ : $Z \to D \to Y$ (blocked by $D$ ) and $Z \to D \leftarrow U \to Y$ (collider $D$ conditioned: open). Not d-separated.

Step 3. (c) Conditioning on service opens $Z \to D \leftarrow U \to Y$ , so the "direct effect" of the lottery picks up motivation differences: among veterans, those with losing lottery numbers volunteered.

Answer: use the lottery as an instrument (Phase 5), not as a control alongside service.

Exercise 15 · When is survey non-response ignorable?

In a household survey, income $Y$ is missing when the response indicator $R = 0$ . Covariates $X$ (region, household size) are always observed. Draw two DAGs, one where $R$ depends only on $X$ and one where it also depends on $Y$ , and state the d-separation that makes complete-case analysis within $X$ valid.

Show solution

Step 1. DAG A: $X \to Y$ , $X \to R$ . Paths $Y$ – $R$ : $Y \leftarrow X \to R$ , blocked by $X$ . So $Y \perp\!\!\!\perp R \mid X$ : missing at random (Day 14).

Step 2. DAG B: add $Y \to R$ (rich households refuse). Now $Y$ and $R$ are adjacent; no set separates them.

Step 3. Under DAG A, $P(y \mid x, R = 1) = P(y \mid x)$ , so complete cases within each $X$ cell (or weighting by $1/P(R = 1 \mid X)$ ) recover the income distribution.

Answer: the condition is $Y \perp\!\!\!\perp R \mid X$ ; under DAG B it fails (missing not at random) and only bounds or extra assumptions help.

Verify in Python

import networkx as nx

dsep = getattr(nx, "is_d_separator", None) or nx.d_separated   # name changed in networkx 3.3

G = nx.DiGraph([("Z", "X"), ("Z", "W"), ("W", "Y"), ("X", "M"), ("M", "Y"), ("X", "C"), ("Y", "C")])
print("paths X-Y:", list(nx.all_simple_paths(G.to_undirected(), "X", "Y")))
for Zs in [set(), {"M", "W"}, {"M", "W", "C"}]:
    print(f"X _||_ Y | {sorted(Zs)}:", dsep(G, {"X"}, {"Y"}, Zs))
print("Z _||_ M | X:", dsep(G, {"Z"}, {"M"}, {"X"}))

# Exercise 13: school meals
S = nx.DiGraph([("I", "M"), ("I", "A"), ("M", "N"), ("N", "T"), ("A", "T"), ("R", "A")])
print("M _||_ R:", dsep(S, {"M"}, {"R"}, set()), "| M _||_ R | T:", dsep(S, {"M"}, {"R"}, {"T"}),
      "| M _||_ T | N,I:", dsep(S, {"M"}, {"T"}, {"N", "I"}))

# Exercise 14: draft lottery
L = nx.DiGraph([("Z", "D"), ("D", "Y"), ("U", "D"), ("U", "Y")])
print("Z _||_ U:", dsep(L, {"Z"}, {"U"}, set()), "| Z _||_ Y | D:", dsep(L, {"Z"}, {"Y"}, {"D"}))

# All pairwise marginal independences implied by the school-meals DAG
nodes = sorted(S)
print("marginally independent pairs:", [(a, b) for i, a in enumerate(nodes) for b in nodes[i + 1:] if dsep(S, {a}, {b}, set())])

Key takeaways

A path is blocked by a conditioned chain or fork middle, or by an unconditioned collider with no conditioned descendants.
d-separation (all paths blocked) implies conditional independence in every distribution that factorises over the DAG.
Conditioning can open paths as well as close them; the graph, not intuition, decides what to control for.

Day 49. d-Separation

Theory

Blocking a path

d-separation

The global Markov property

Recipe

Non-monotonicity

Markov blanket

Part 1 · Warm-up

Exercise 1 · List the paths

Exercise 2 · Nothing conditioned

Exercise 3 · Conditioning on $M$ and $W$

Exercise 4 · Adding $C$

Exercise 5 · A different pair

Part 2 · Proofs

Exercise 6 · Neighbours are never separated

Exercise 7 · Local Markov from d-separation

Exercise 8 · The Markov blanket

Exercise 9 · No common ancestor, no association

Exercise 10 · More control can hurt

Part 3 · Applied

Exercise 11 · Two stories about microcredit

Exercise 12 · Pollution, allergies and the emergency room

Exercise 13 · School meals

Exercise 14 · Checking an instrument

Exercise 15 · When is survey non-response ignorable?

Verify in Python

Key takeaways

Simulation Lab: d-Separation Explorer

Day 49. d-Separation

Theory

Blocking a path

d-separation

The global Markov property

Recipe

Non-monotonicity

Markov blanket

Part 1 · Warm-up

Exercise 1 · List the paths

Exercise 2 · Nothing conditioned

Exercise 3 · Conditioning on MMM and WWW

Exercise 4 · Adding CCC

Exercise 5 · A different pair

Part 2 · Proofs

Exercise 6 · Neighbours are never separated

Exercise 7 · Local Markov from d-separation

Exercise 8 · The Markov blanket

Exercise 9 · No common ancestor, no association

Exercise 10 · More control can hurt

Part 3 · Applied

Exercise 11 · Two stories about microcredit

Exercise 12 · Pollution, allergies and the emergency room

Exercise 13 · School meals

Exercise 14 · Checking an instrument

Exercise 15 · When is survey non-response ignorable?

Verify in Python

Key takeaways

Simulation Lab: d-Separation Explorer

Exercise 3 · Conditioning on $M$ and $W$

Exercise 4 · Adding $C$