{ "nbformat": 4, "nbformat_minor": 5, "metadata": { "kernelspec": { "name": "python3", "display_name": "Python 3" }, "language_info": { "name": "python" }, "colab": { "provenance": [] } }, "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Day 49: d-Separation\n", "\n", "*Beginner to Ninja: Math for Causal Inference*\n", "\n", "One rule for reading every conditional independence a DAG implies. A path is blocked by a conditioning set if it has a chain or fork whose middle is conditioned on, or a collider that is not; two sets are d-separated if every path between them is blocked.\n", "\n", "**Learning outcomes**\n", "\n", "- Decide whether a path is open or blocked given a conditioning set.\n", "- Decide whether two variables are d-separated by enumerating paths.\n", "- Prove the Markov blanket property and that the local Markov property is a special case of d-separation.\n", "- Use d-separation to compare candidate DAGs, check instruments and reason about missing data." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Theory\n", "\n", "### Blocking a path\n", "\n", "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\n", "\n", "1. $M$ is the middle of a **chain** ($\\to M \\to$) or **fork** ($\\leftarrow M \\to$) and $M \\in \\mathbf Z$, or\n", "2. $M$ is a **collider** ($\\to M \\leftarrow$) and **neither $M$ nor any descendant of $M$** is in $\\mathbf Z$.\n", "\n", "A path that is not blocked is **open** (or *active*). Open paths carry association.\n", "\n", "### d-separation\n", "\n", "$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**.\n", "\n", "### The global Markov property\n", "\n", "If $P$ factorises according to $G$ (Day 47), then\n", "\n", "$$\n", "(X \\perp\\!\\!\\!\\perp Y \\mid \\mathbf Z)_G \\;\\Longrightarrow\\; X \\perp\\!\\!\\!\\perp Y \\mid \\mathbf Z \\text{ in } P.\n", "$$\n", "\n", "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\".\n", "\n", "### Recipe\n", "\n", "1. List every path between $X$ and $Y$ (ignoring arrow directions, no repeated nodes).\n", "2. For each path, classify each interior node as chain, fork or collider.\n", "3. 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$.\n", "4. $X$ and $Y$ are d-separated if no path is open.\n", "\n", "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.\n", "\n", "### Non-monotonicity\n", "\n", "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.\n", "\n", "### Markov blanket\n", "\n", "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$.\n", "\n", "## Part 1 · Warm-up\n", "\n", "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$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 1 · List the paths\n", "\n", "List every path between $X$ and $Y$ and classify the interior nodes.\n", "\n", "
Show solution\n", "\n", "**Step 1.** $X \\to M \\to Y$: $M$ is a chain middle.\n", "\n", "**Step 2.** $X \\leftarrow Z \\to W \\to Y$: $Z$ is a fork, $W$ a chain middle.\n", "\n", "**Step 3.** $X \\to C \\leftarrow Y$: $C$ is a collider.\n", "\n", "**Answer:** three paths.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 2 · Nothing conditioned\n", "\n", "Are $X$ and $Y$ d-separated by the empty set?\n", "\n", "
Show solution\n", "\n", "**Step 1.** Path 1: chain through $M$, not conditioned: open.\n", "\n", "**Step 2.** One open path suffices.\n", "\n", "**Answer:** no, they are d-connected. (Path 2 is also open; path 3 is blocked by the unconditioned collider.)\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 3 · Conditioning on $M$ and $W$\n", "\n", "Are $X$ and $Y$ d-separated by $\\{M, W\\}$?\n", "\n", "
Show solution\n", "\n", "**Step 1.** Path 1: $M$ conditioned, chain: blocked.\n", "\n", "**Step 2.** Path 2: $W$ conditioned, chain: blocked.\n", "\n", "**Step 3.** Path 3: collider $C$ not conditioned and has no descendants: blocked.\n", "\n", "**Answer:** yes, d-separated.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 4 · Adding $C$\n", "\n", "Are $X$ and $Y$ d-separated by $\\{M, W, C\\}$?\n", "\n", "
Show solution\n", "\n", "**Step 1.** Paths 1 and 2 stay blocked.\n", "\n", "**Step 2.** Path 3: the collider $C$ is now conditioned: open.\n", "\n", "**Answer:** no. Adding $C$ re-connects $X$ and $Y$ (non-monotonicity).\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 5 · A different pair\n", "\n", "Is $Z$ d-separated from $M$ by $\\{X\\}$?\n", "\n", "
Show solution\n", "\n", "**Step 1.** $Z \\to X \\to M$: chain at $X$, conditioned: blocked.\n", "\n", "**Step 2.** $Z \\to W \\to Y \\leftarrow M$: collider $Y$; neither $Y$ nor its descendant $C$ is conditioned: blocked.\n", "\n", "**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).\n", "\n", "**Step 4.** $Z \\to X \\to C \\leftarrow Y \\leftarrow M$: $X$ is a chain middle, conditioned: blocked.\n", "\n", "**Answer:** yes, every path is blocked.\n", "\n", "
\n", "\n", "## Part 2 · Proofs" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 6 · Neighbours are never separated\n", "\n", "Prove that if $X \\to Y$ is an edge, no set $\\mathbf Z$ (excluding $X, Y$) d-separates them.\n", "\n", "
Show solution\n", "\n", "**Step 1.** The one-edge path $X \\to Y$ has no interior nodes.\n", "\n", "**Step 2.** Blocking requires an interior node satisfying condition 1 or 2; there is none.\n", "\n", "**Step 3.** So this path is open for every $\\mathbf Z$, and $X, Y$ are d-connected. $\\blacksquare$\n", "\n", "This is why missing arrows, not present ones, carry the testable content of a DAG.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 7 · Local Markov from d-separation\n", "\n", "Prove that every node $V$ is d-separated from any non-descendant $N$ (not a parent) by $\\operatorname{pa}(V)$.\n", "\n", "
Show solution\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "**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$.\n", "\n", "**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$.\n", "\n", "**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$\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 8 · The Markov blanket\n", "\n", "Prove that $V$ is d-separated from every node outside its Markov blanket $\\mathbf B$ (parents, children, children's other parents) given $\\mathbf B$.\n", "\n", "
Show solution\n", "\n", "**Step 1.** Paths leaving through a parent $P$: as in Exercise 7, $P$ is a conditioned chain or fork middle: blocked.\n", "\n", "**Step 2.** Paths leaving through a child $C$ and continuing $V \\to C \\to$: $C$ is a conditioned chain middle: blocked.\n", "\n", "**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$.\n", "\n", "**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.\n", "\n", "**Step 5.** Every path is blocked. $\\blacksquare$\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 9 · No common ancestor, no association\n", "\n", "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.\n", "\n", "
Show solution\n", "\n", "**Step 1.** With $\\mathbf Z = \\varnothing$, a path is open only if it has no colliders.\n", "\n", "**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).\n", "\n", "**Step 3.** From $S$, both halves of the path are directed paths towards $X$ and towards $Y$, so $S$ is a common ancestor.\n", "\n", "**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.)\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 10 · More control can hurt\n", "\n", "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.\n", "\n", "
Show solution\n", "\n", "**Step 1.** Collider $X \\to W \\leftarrow Y$: the only path is blocked given $\\varnothing$ and open given $W$.\n", "\n", "**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$.\n", "\n", "**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$\n", "\n", "
\n", "\n", "## Part 3 · Applied" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 11 · Two stories about microcredit\n", "\n", "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?\n", "\n", "
Show solution\n", "\n", "**Step 1.** DAG 1 implies $E \\perp\\!\\!\\!\\perp I \\mid L$ (chain blocked at $L$).\n", "\n", "**Step 2.** DAG 2 has the edge $E \\to I$, so by Exercise 6 no independence between $E$ and $I$ is implied.\n", "\n", "**Step 3.** In a linear model, $E \\perp\\!\\!\\!\\perp I \\mid L$ means a zero education coefficient once loans are included.\n", "\n", "**Answer:** a large, precise coefficient rejects DAG 1; DAG 2 survives (education affects income other than through loans).\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 12 · Pollution, allergies and the emergency room\n", "\n", "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?\n", "\n", "
Show solution\n", "\n", "**Step 1.** One path: $P \\to A \\leftarrow G$, a collider at $A$.\n", "\n", "**Step 2.** Given nothing: blocked, so $P \\perp\\!\\!\\!\\perp G$.\n", "\n", "**Step 3.** Given $E$: $E$ is a descendant of the collider, so the path opens: not d-separated.\n", "\n", "**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.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 13 · School meals\n", "\n", "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\\}$?\n", "\n", "
Show solution\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "**Answer:** yes, no, yes. Statement (c) is testable: given nutrition and income, meals should not predict test scores.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 14 · Checking an instrument\n", "\n", "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?\n", "\n", "
Show solution\n", "\n", "**Step 1.** (a) Path $Z \\to D \\leftarrow U$ has a collider at $D$: blocked. Yes, $Z \\perp\\!\\!\\!\\perp U$ (the lottery is random).\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "**Answer:** use the lottery as an instrument (Phase 5), not as a control alongside service.\n", "\n", "
" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Exercise 15 · When is survey non-response ignorable?\n", "\n", "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.\n", "\n", "
Show solution\n", "\n", "**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).\n", "\n", "**Step 2.** DAG B: add $Y \\to R$ (rich households refuse). Now $Y$ and $R$ are adjacent; no set separates them.\n", "\n", "**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.\n", "\n", "**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.\n", "\n", "
\n", "\n", "## Verify in Python" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "*Your work:*" ] }, { "cell_type": "code", "metadata": {}, "execution_count": null, "outputs": [], "source": [ "import networkx as nx\n", "\n", "dsep = getattr(nx, \"is_d_separator\", None) or nx.d_separated # name changed in networkx 3.3\n", "\n", "G = nx.DiGraph([(\"Z\", \"X\"), (\"Z\", \"W\"), (\"W\", \"Y\"), (\"X\", \"M\"), (\"M\", \"Y\"), (\"X\", \"C\"), (\"Y\", \"C\")])\n", "print(\"paths X-Y:\", list(nx.all_simple_paths(G.to_undirected(), \"X\", \"Y\")))\n", "for Zs in [set(), {\"M\", \"W\"}, {\"M\", \"W\", \"C\"}]:\n", " print(f\"X _||_ Y | {sorted(Zs)}:\", dsep(G, {\"X\"}, {\"Y\"}, Zs))\n", "print(\"Z _||_ M | X:\", dsep(G, {\"Z\"}, {\"M\"}, {\"X\"}))\n", "\n", "# Exercise 13: school meals\n", "S = nx.DiGraph([(\"I\", \"M\"), (\"I\", \"A\"), (\"M\", \"N\"), (\"N\", \"T\"), (\"A\", \"T\"), (\"R\", \"A\")])\n", "print(\"M _||_ R:\", dsep(S, {\"M\"}, {\"R\"}, set()), \"| M _||_ R | T:\", dsep(S, {\"M\"}, {\"R\"}, {\"T\"}),\n", " \"| M _||_ T | N,I:\", dsep(S, {\"M\"}, {\"T\"}, {\"N\", \"I\"}))\n", "\n", "# Exercise 14: draft lottery\n", "L = nx.DiGraph([(\"Z\", \"D\"), (\"D\", \"Y\"), (\"U\", \"D\"), (\"U\", \"Y\")])\n", "print(\"Z _||_ U:\", dsep(L, {\"Z\"}, {\"U\"}, set()), \"| Z _||_ Y | D:\", dsep(L, {\"Z\"}, {\"Y\"}, {\"D\"}))\n", "\n", "# All pairwise marginal independences implied by the school-meals DAG\n", "nodes = sorted(S)\n", "print(\"marginally independent pairs:\", [(a, b) for i, a in enumerate(nodes) for b in nodes[i + 1:] if dsep(S, {a}, {b}, set())])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Key takeaways\n", "\n", "- A path is blocked by a conditioned chain or fork middle, or by an unconditioned collider with no conditioned descendants.\n", "- d-separation (all paths blocked) implies conditional independence in every distribution that factorises over the DAG.\n", "- Conditioning can open paths as well as close them; the graph, not intuition, decides what to control for." ] } ] }