Interactive demo · Probability and Statistical Inference · Chapter 17

d-separation by reachability: follow the ball

Listing every path between two nodes takes exponential time; the reachability search below decides d-separation in time proportional to the size of the graph. A ball starts at the source X; it travels along arrows in either direction and remembers whether it arrived at a node from a child (moving up, ↑) or from a parent (moving down, ↓). At a node not in the conditioning set W it passes on (up and down if it came up, only down if it came down: a chain or fork stays open). At a node in W it stops, except that a ball arriving from a parent bounces back up at any node that is in W or has a descendant in W: a collider is opened by conditioning on it or on a descendant (rules 1 to 3 of the book). The nodes the ball reaches are d-connected to X given W; the others are d-separated. The bars check Theorem 17.10 on a random distribution Markov to the graph: the exact conditional mutual information I(X; V | W) is zero at the d-separated nodes and positive at the others.

Graph

Clicking a node

The search

Random tables (for the check)

Try these

The queue holds states (node, direction); each state is visited once, so the work is at most twice the number of nodes plus edges. The check uses binary variables with P(v = 1 | parents) = 0.1 + 0.8u for each parent configuration; for such generic tables the only zeros of I(X; V | W) are the ones the graph forces.

In the lecture notes