Exact Inference: Variable Elimination

Last lesson left the Bayes net storing the joint compactly, yet warned that querying it — “given the alarm, what is the chance of a burglary?” — means summing that joint over every variable you did not observe, a sum with exponentially many terms on a big net. Variable elimination is the routine that performs that sum exactly — no sampling, no approximation — by sweeping the unwanted variables out one at a time and, crucially, never expanding the whole joint in the first place.

It is slower than sampling on giant networks, but precise. For exam-sized nets of two to four nodes it is the right tool, and a single elimination step is usually all GATE asks you to perform. The same sum-product engine runs inside probabilistic-programming libraries and diagnosis systems whenever an exact answer is affordable — so the hand-trace you practise here is a scaled-down version of what those tools do.

The procedure

To compute P(Query | Evidence):

1. Write the joint as a product of CPT factors — one factor per node, from the Bayes-net factorisation.
2. Fix the evidence variables to their observed values.
3. Pick a hidden (non-query, non-evidence) variable and sum it out: replace every factor that contains it with one factor that is the sum over that variable’s values.
4. Repeat until only the query variable remains.
5. Normalise so the surviving distribution sums to 1.

The answer is exact (up to floating-point error). That is the headline property — VE is not a sampling method.

Worked example — eliminate one variable

A chain A → B → C. Given P(A=1) = 0.5, P(B=1 | A=1) = 0.7, P(B=1 | A=0) = 0.2, P(C=1 | B=1) = 0.9, P(C=1 | B=0) = 0.4. Find P(C=1) by summing out A and B.

The factorisation is P(A, B, C) = P(A) · P(B | A) · P(C | B), and we want P(C=1) = Σ_A Σ_B P(A) · P(B | A) · P(C=1 | B). Sum the variables out one at a time.

Step 1 — eliminate A. Collapse P(A) · P(B | A) into a single factor over B:

P(B=1) = P(B=1 | A=1)·P(A=1) + P(B=1 | A=0)·P(A=0)
       = 0.7 · 0.5            + 0.2 · 0.5
       = 0.35                 + 0.10              =  0.45

P(B=0) = 1 − 0.45  =  0.55

Step 2 — eliminate B. Combine that new P(B) with P(C=1 | B):

P(C=1) = P(C=1 | B=1)·P(B=1) + P(C=1 | B=0)·P(B=0)
       = 0.9 · 0.45           + 0.4 · 0.55
       = 0.405                + 0.220             =  0.625

So P(C=1) = 0.625 — exactly, no sampling involved, and above 0.5 just as the leaning CPTs suggested. Each elimination step is one weighted sum over the values of the variable being removed, and you never built the full three-variable joint.

How GATE asks this

Two patterns. MSQ: which of the listed methods compute exact posteriors on a Bayes net? Variable elimination yes; enumeration of the joint yes; rejection / likelihood-weighting / Gibbs no — they are sampling. NAT: perform one elimination step on a 3-node chain or v-structure and report the marginal. GATE DA 2025 ran an MSQ asking exactly this classification.

In one breath

Variable elimination computes an exact posterior on a Bayes net by writing the joint as a product of CPT factors, fixing the evidence, then summing out each hidden variable one at a time (replacing every factor that mentions it with the sum-over-its-values), and finally normalising — so it never expands the full 2ⁿ joint, the answer is exact up to floating-point, and it sits firmly on the exact side of the ledger (with full enumeration) opposite the approximate sampling methods.

Practice

A question to carry forward

Variable elimination is exact, and on a small net it is fast. But its cost has a hidden teeth. As you sum out variables on a large, tangled network, the intermediate factors can swell — combining a variable’s many neighbours into ever-wider tables — until the careful summing-out is no cheaper than the full joint it set out to avoid. On a dense net of fifty variables, “exact” can mean “will not finish this century.”

So when exactness becomes unaffordable, you strike a different bargain: give up the guarantee of the true answer in exchange for a good enough one, fast. Instead of computing the probability, you estimate it — by conjuring up thousands of random scenarios consistent with the net and simply counting how often the thing you care about happens. Here is the thread onward, and the chapter’s last step: how do you draw such samples from a Bayes net, what three classic recipes turn that counting into a posterior estimate — and what is the price you always pay for trading exact arithmetic for random draws?