How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
D-separation is separation in the ancestral moral graph
Statement
For disjoint , d-separates and in if and only if deleting from leaves no undirected path from to .
Facts & Assumptions
Given: The finite DAG, disjoint vertex sets, and graph conventions above.
A path is active exactly when it has no conditioned noncollider and every collider has a conditioned descendant, including itself. Paths, active paths, and d-separation in a finite DAG
The ancestral moral graph retains ancestors of , forgets arrow directions, and joins distinct parents of a common child. The ancestral moral graph of a DAG
Every active finite route between distinct endpoints outside has an active path. Every active finite route contains an active path
Proof
Given: The hypotheses in the statement.
Suppose an active path joins to . From any noncollider follow an outgoing path edge forward until reaching an endpoint or a collider. The reached endpoint is in , while a reached collider is an ancestor of by activity. Thus every path vertex is in . Replace each collider segment by its moral edge ; colliders cannot be consecutive along a path. The resulting walk avoids , since all retained internal vertices were noncolliders and the endpoints are outside . Loop deletion in this undirected graph yields a moral path avoiding .
Conversely suppose a moral path avoiding joins to . Keep its skeleton edges, and expand each remaining moral edge using a common child as . This is a finite route; its inserted occurrences are colliders and all its other occurrences are outside . Every collider is in . Call a collider occurrence bad if its vertex is not an ancestor of . Among routes joining to with every vertex in and every noncollider outside , minimize the number of bad collider occurrences; the expanded route makes the class nonempty. If is a bad occurrence, it is an ancestor of some . A directed path from to avoids , since otherwise would be an ancestor of . If , replace the whole prefix up to this occurrence of by that directed path traversed backward; if , replace the suffix by the path traversed forward. If , simply terminate at that occurrence. Otherwise the retained incident arrow points into and the new incident arrow points out of , making it an allowed noncollider. All new internal chain occurrences are noncolliders outside , and other retained occurrences have their original incidences. Intersections of the chain with the retained segment cause repetitions only; no loops are deleted in this step, and activity is defined occurrence by occurrence. At least the selected bad occurrence disappears and no new bad occurrence is introduced, contradicting minimality. Thus the minimum route is active. Its endpoints are distinct because are disjoint, and [F3] gives an active path with those endpoints.
An active path therefore exists if and only if there is a moral path avoiding . Negating this equivalence proves the claim. If either endpoint set is empty, neither type of path exists and both separation statements hold.
Depends on
Used by
Dependency tree · one level
3 results within one dependency step of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Judea Pearl, Causal Diagrams for Empirical Research, §2-1, p. 672 (standard reference, not scraped)
- Miguel A. Hernán and James M. Robins, Causal Inference: What If, Fine Point 6.1, pp. 78–79 (standard reference, not scraped)