Conditional Independence and the Factorization of Joint Distributions

A joint distribution over $n$ binary variables is specified by $2^n - 1$ numbers: one probability for each of the $2^n$ assignments, minus the constraint that they sum to one. At $n = 10$ that is 1023 numbers, which is tedious but writable. At $n = 20$ it is roughly $1.05 \times 10^6$, which is already awkward to elicit. At $n = 100$ it exceeds $10^{30}$, and no procedure that visits each entry can terminate. Yet models with hundreds of variables are built and used, and the only reason is that their distributions are assumed to have structure that makes most of those entries redundant.

The chain rule alone buys nothing

The chain rule expands a joint into a product of conditionals in any variable order:

$$p(x_1, \dots, x_n) = \prod_{i=1}^{n} p(x_i \mid x_1, \dots, x_{i-1})$$

This is an identity, true for every distribution, and it changes nothing: the last factor still conditions on $n-1$ variables and its table has $2^{n-1}$ rows. The expansion becomes useful only when a conditional is asserted to depend on a small subset of its predecessors. If each $x_i$ depends on at most $k$ of the earlier variables, each conditional table in the worst case holds $2^k$ entries, and the whole product holds at most $n \cdot 2^k$ entries. At $n = 20$ and $k = 3$ that is at most 160 numbers against $2^{20} - 1 \approx 1.05 \times 10^6$ for the unrestricted table.

The sharpest illustration of the gain is a chain: $n$ binary variables, each dependent only on its immediate predecessor. The chain rule in that order needs one free parameter for the first variable and one free parameter per row of each of the remaining $n - 1$ conditionals, so $n$ free parameters and $2n$ stored entries, against $2^n - 1$ for the unrestricted joint. At $n = 30$ the counts are 30 free parameters and 60 entries against roughly $1.07 \times 10^9$, and at $n = 100$ the last figure is no longer writable as a decimal in any useful sense.

The assertion that makes the reduction possible is conditional independence. Variables $X$ and $Y$ are conditionally independent given $Z$, written $X \perp!!!\perp Y \mid Z$, when

$$p(X, Y \mid Z) = p(X \mid Z),p(Y \mid Z)$$

for every assignment of $Z$ with positive probability; equivalently $p(X \mid Y, Z) = p(X \mid Z)$. The restriction to assignments with positive probability is not pedantry. Conditioning on probability-zero events is undefined, so where the model places a hard zero the independence question has no answer, and an implementation that divides by a zero-probability conditional will produce infinite or undefined values rather than a warning.

A product of small factors is the whole representation

Writing the joint as a product of factors, each a scalar function of a small set of variables, is the general form that conditional independence produces. The factors need not be normalized individually; the joint is their product up to a constant, and the constant is the sum of all entries in the product. This is the same normalizing term discussed in Conjugate Priors and the Arithmetic of Posterior Updating, where it happens to have a closed form because the model was small enough. For a product of general factors it is a sum over a product space with the same exponential size as the raw table, and inference is exactly the problem of computing it without enumerating that space.

An explicit small example makes the arithmetic concrete. Three binary variables arranged in a chain $a \rightarrow b \rightarrow c$, with the conditional independencies $b \perp!!!\perp c \mid a$ and $a \perp!!!\perp c \mid b$, have a joint that factors into one marginal and two conditional tables.

P_A = {'0': 0.6, '1': 0.4}                 # 2 entries, 1 free parameter
P_B = {'0': {'0': 0.8, '1': 0.2},          # p(b | a = 0): 1 free parameter
       '1': {'0': 0.3, '1': 0.7}}          # p(b | a = 1): 1 free parameter
P_C = {'0': {'0': 0.9, '1': 0.1},          # p(c | b = 0)
       '1': {'0': 0.4, '1': 0.6}}          # p(c | b = 1)

def joint(a, b, c):
    # each factor reads at most one parent value; no factor has all three variables
    return P_A[a] * P_B[a][b] * P_C[b][c]

total = sum(joint(a, b, c) for a in '01' for b in '01' for c in '01')
print(total)                 # 1.0
print(joint('0', '0', '1'))  # 0.6 * 0.8 * 0.1 = 0.048

Five free parameters, obtained as one for $P_A$ plus one per row of $P_B$ and $P_C$, replace the seven needed for the unrestricted joint over three binary variables. The count is unimpressive at this size because $2^3 - 1 = 7$, and the gap between $n \cdot 2^k$ and $2^n - 1$ is what matters as $n$ grows.

Order decides the parent sets, and the parent sets decide the cost

The chain rule is valid in any order, but the factors it produces are not equally small. Choosing an order fixes which variables may serve as parents, and a variable placed late may end up conditioning on many predecessors even when the distribution itself contains few dependencies. A distribution whose variables are all marginally independent costs $n$ numbers in any order, and a uniformly dense one costs $2^n - 1$ in any order, but sparse distributions are order-sensitive: an order that orients a tree away from its leaves yields factors of size two, while an order that places a hub last can make one factor depend on every other variable.

The set of independencies a distribution satisfies is not arbitrary. It must satisfy the semi-graphoid properties: symmetry, decomposition from $X \perp!!!\perp (Y \cup W) \mid Z$ to $X \perp!!!\perp Y \mid Z$, weak union, and contraction. These axioms are what allow a distribution to be summarized by a graph at all, since a graph’s separation criterion also satisfies them, and it is the mismatch between what a factorization can express and what the axioms permit that produces the well-known exceptions. Independence of the marginal and independence of the conditional are separate statements: two variables can be marginally independent yet dependent given a common effect of both, and two variables can be dependent marginally yet independent given a common cause. A factorization that asserts the wrong one of those two is not repaired by more data.

What a factored joint cannot say

The most important limitation is that a factorization is a modeling commitment, not an estimate. If a factor asserts $p(c \mid a, b) = p(c \mid b)$, then no assignment of the factor’s entries can represent a dependence of $c$ on $a$ that the data exhibit. The model has probability zero for the pattern it cannot express, and adding observations adjusts the factor’s numbers without widening its scope. Model misfit of this kind is therefore permanent: the defect is in the structure, and detecting it requires either comparing structures or testing the implied independence directly.

Two further edge cases arise from the same source. Hard zeros inside a factor propagate to the joint, and can make the probability of an observed assignment zero, which in turn makes every conditional derived from the product undefined; a common fix is to smooth the factor rather than to let a structural zero stand. And a variable that is a deterministic function of its parent has a degenerate conditional distribution, which has no density with respect to the same base measure as its parent. Continuous formulations silently assume non-degenerate conditionals, so deterministic dependencies between continuous variables must be handled by reparameterization rather than by writing a spike into a table.

One class of structure sits between the two extremes and is not expressible by the factorization alone. A conditional distribution can be context specific: for certain parent values the child may ignore other parents entirely, as when one parent takes a value that fixes the child’s distribution regardless of the rest. A single table per node cannot record that, because the table enumerates all parent combinations and gives each combination its own free parameter. Rule-based or tree-structured encodings of the same conditional do record it, at the cost of a representation the inference procedure has to interpret; the compact canonical-form conditionals used for directed models are one instance, and they restrict the family of conditionals rather than the graph. The distinction is not cosmetic, because a context-specific independence that no algorithm can read out of the tables buys nothing at query time, even though the probability statements the model makes are unchanged.

The payoff of the factored form is that it names only the variables a factor needs, and the price is that queries must be answered by combining factors rather than by reading entries. Marginalizing one variable out of a product is a sum over that variable’s assignments for each configuration of the remaining variables, and the order in which such sums are performed decides whether the result is cheap or exponential; Exact Inference by Variable Elimination and the Cost of Treewidth works through that accounting. Where each factor is guaranteed to involve at most one parent beyond the child, the local independence assumptions also define a Markov blanket, the set of variables whose values make a given variable independent of everything else, and that blanket is what later algorithms sweep over instead of the full joint.