Directed Graphical Models: D-Separation and the Markov Blanket

A directed graphical model, or Bayesian network, is a directed acyclic graph whose nodes are random variables together with one conditional distribution per node, conditioned on that node’s parents. The graph contributes no numbers; it contributes a claim about which factorizations of the joint are permitted, and the conditional distributions fill in the entries. For a graph with nodes $X_1, \dots, X_n$ the joint asserted by the graph is

$$p(X_1, \dots, X_n) = \prod_{i=1}^{n} p\bigl(X_i \mid \mathrm{Pa}(X_i)\bigr)$$

Every acyclic graph has at least one topological order, an ordering in which each node appears after all of its parents, and in that order the chain rule factors simplify exactly to the parent sets, because $p(x_i \mid x_1, \dots, x_{i-1})$ depends on the predecessors only through the parents. That is the technical content of the graph: it picks one factorization out of the many that the chain rule permits. The edges are not required to describe a causal process, and nothing in the semantics forbids interpreting them that way.

The topology fixes the parameter count

A node with $k$ parents, all binary, has a conditional table with $2^k$ rows and one free parameter per row, so the model needs $2^k$ numbers per node plus the marginal of every parentless node. With a bound $k$ on in-degree the whole model fits in at most $n \cdot 2^k$ parameters, and the same argument that makes the factored joint compact applies here, as described in Conditional Independence and the Factorization of Joint Distributions. A complete undirected graph with more than two nodes is not a candidate at all, because a complete directed graph contains cycles; the densest legal structure orients every edge forward along one topological order, which costs $2^n - 1$ parameters and reduces to the untabulated joint.

Three path shapes, one blocking rule

Independence statements read off a directed graph come from the shapes a connecting path can take. A path here means any sequence of edges regardless of their direction.

In a chain $a \rightarrow b \rightarrow c$, condition on $b$ and $a$ is independent of $c$: once the middle value is known, the earlier one adds nothing. In a fork $a \leftarrow b \rightarrow c$, the same is true, with $b$ a common cause rather than an intermediary. In a collider $a \rightarrow b \leftarrow c$, the behaviour reverses: $a$ and $c$ are dependent given $b$, while without evidence about $b$ they are independent along that path.

This gives one rule. A path is blocked by a set of evidence nodes if it contains either a non-collider that is in the set, or a collider such that neither the collider nor any of its descendants is in the set. Two sets of variables are d-separated by the evidence when every path between them is blocked, and d-separation implies conditional independence in every distribution that factors according to the graph. The clause about descendants is what makes a collider behave asymmetrically: evidence about a descendant of the collider opens the path exactly as evidence about the collider does, which is the graph’s account of explaining away. Two causes that are independent a priori become dependent once their common effect, or anything downstream of it, is observed.

The Markov blanket is the only neighbourhood an update needs

Multiplying out the factorization shows that a variable $x_i$ appears in exactly two kinds of factor: its own conditional $p(x_i \mid \mathrm{Pa}(x_i))$, and the conditional of each child, since $x_i$ is a parent of those children. Every other factor is free of $x_i$. The variables appearing in those factors are the parents of $x_i$, its children, and the other parents of its children — the co-parents. That set is the Markov blanket, and conditioned on it, $x_i$ is independent of every other variable in the graph.

The blanket gives an exact locality property. Any query about $x_i$ given evidence, including its posterior marginal, can be computed from the factors touching the blanket alone; the rest of the network enters only through the values of the blanket variables, which act as sufficient context. Sizes follow immediately: a node with $k$ parents, $m$ children, and total co-parent count $c$ has a blanket of size $k + m + c$. Sampling schemes that resample one variable at a time against its blanket exploit this, which is why a single-variable conditional is cheap to write down even when the joint is not.

Compact conditional distributions for large parent sets

Tabular conditionals are the straightforward encoding, and they are the wrong choice when a node has many parents. A child with ten binary parents needs 1024 rows. A canonical-family distribution can collapse that: in the noisy-OR model each parent is an independent cause that fails to trigger the child with some probability $q_i$, and the child is off exactly when every active cause fails, so $p(\text{child} = 0 \mid \text{parents}) = \prod_{i \in \text{active}} q_i$. A child with ten parents therefore needs ten parameters instead of 1024, at the cost of ruling out interaction patterns the product form cannot express, such as one cause amplifying another. Context-specific tables, in which rows are grouped by the value of a subset of the parents and share parameters within a group, are a second encoding with the same character: fewer parameters, less freedom.

Hard evidence and soft evidence are not interchangeable

The blocking rule is stated for evidence that assigns values to variables, and d-separation is sound only for that case. A second kind of observation appears often: a reading that changes the probability of a variable without fixing its value, as a noisy sensor does. Such soft evidence multiplies the model by a likelihood over the variable, and the variable does not become observed for the purpose of blocking paths. Treating it as an observation is a reliable way to produce wrong independence claims, because information can still flow through a variable whose distribution has merely been reweighted. The formal fix changes the graph rather than the rule: introduce a new child of the variable to carry the observation, and note that this child is a descendant, so it opens every collider path it touches and behaves like any other observed descendant.

Sampling methods make the same distinction concrete. Likelihood weighting draws assignments from the prior model and weights each one by the likelihood of the soft evidence, so the variable keeps its full range of values in every drawn state; the estimator’s weakness is that the weights degenerate as the likelihood concentrates on few states, leaving a handful of samples carrying almost all the mass. Rejection sampling, which discards draws incompatible with a hard observation, is valid only when the evidence really is a value. The bookkeeping differs in a way that shows up in the table sizes: a hard observation on a binary variable fixes one of two entries, while a soft observation on the same variable adds a factor of two numbers that both remain free, so the extra information costs domain size rather than a single assignment. Both cases mark the boundary of the graph’s claims: d-separation reasons about observed values, and it says nothing about a factor-shaped observation.

Where the graph and the distribution disagree

D-separation is sound with respect to the factorization: an independence it reports holds in every distribution that factors according to the graph. It is not complete. A distribution can satisfy independencies that no d-separation statement of the graph predicts, and the standard name for a distribution whose independencies are exactly the graph’s is a faithful one. Near-deterministic conditional distributions make faithfulness fail in a way that is easy to construct: if a child is almost surely a copy of a parent, the pair behaves as a single variable and independencies appear that the graph does not show.

Two further failure modes are structural. A cyclic graph has no consistent factorization under this semantics, because the conditionals would define a joint that does not normalize, so cycles must be broken or handled by different machinery for reciprocal dependence. And a deterministic conditional between continuous variables places probability on a lower-dimensional set, which breaks the density-based derivation of the independencies and makes plain d-separation reasoning unreliable at that node. The remedy is reparameterization, not a larger table.

The value of the directed form is that the semantics are local and checkable on the graph, so structure can be reasoned about without touching numbers. Where reciprocal or non-directional dependence is the natural description, the undirected counterpart described in Markov Random Fields and the Intractability of the Partition Function replaces the parent sets with clique potentials; and once the structure is fixed, answering a query still requires an inference algorithm, the accounting for which begins with Exact Inference by Variable Elimination and the Cost of Treewidth.