Variable Elimination for Exact Inference

Given a graphical model over many variables, the naive way to compute a marginal probability — say, "what's the probability the market regime is 'crisis' given three observed signals?" — is to build the full joint distribution over every variable and sum out the ones you don't care about. That table grows exponentially with the number of variables, making it hopeless beyond a handful. Variable elimination avoids ever building it: because the joint distribution already factors into small local functions (one per clique in the graph), you can sum out one unwanted variable at a time, multiplying together only the factors that mention it, producing a smaller intermediate factor, and repeating until only the variables you want remain.

The trick that makes this efficient is elimination order: summing out variables in a good order keeps the intermediate factors small, while a bad order can make them balloon back toward the full joint table. Choosing a near-optimal order is itself a hard combinatorial problem in general, but for chain- or tree-structured graphs (like hidden Markov models) there's a natural order — eliminate from the ends inward — that keeps every intermediate factor small automatically.

For a three-variable chain $A \to B \to C$, eliminating $A$ first only requires multiplying the two factors mentioning $A$ and summing over $A$'s values, leaving a small factor over $B$ alone — never touching $C$ until the next step, and never forming the full $A,B,C$ table.