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.