Reasoning Under Uncertainty in AI for GATE DA 2027: Bayesian Networks, Variable Elimination & Sampling

By Piyush Wairale — Instructor, BS Data Science program at IIT Madras · IIT Madras alumnus · 10,000+ GATE students mentored · Last updated: August 2026

The GATE DA syllabus for Artificial Intelligence lists reasoning under uncertainty with unusual precision: “conditional independence representation, exact inference through variable elimination, approximate inference through sampling.” That precision is a gift. Unlike broader subjects where you must guess what the examiner cares about, here the syllabus hands you the exam blueprint. Every question from this block — whether it is a 1-mark conceptual MCQ or a 2-mark numerical — comes from one of these three ideas. This article covers each of them in depth, in the order you should learn them, and connects them to the way GATE actually frames its questions. If you prefer learning by video, the full topic is taught free in the playlist below, and everything here is covered rigorously in the GATE DA Artificial Intelligence Course & Test Series.

Why “Reasoning Under Uncertainty” Exists at All

Classical logic — the propositional and predicate logic you study earlier in the AI syllabus — deals in certainties. A statement is true or false; a rule either fires or it doesn’t. But almost nothing an intelligent agent cares about in the real world is certain. A medical diagnosis system doesn’t know that a patient has a disease; it knows a test came back positive, and tests lie. A spam filter doesn’t know a mail is spam; it sees words that make spam more or less likely. The mathematical language for this is probability theory, and the engineering challenge is this: how do we represent a probability distribution over many variables compactly, and how do we answer questions about it efficiently?

To see why this is hard, consider the brute-force approach: write down the full joint distribution. If you have n binary random variables, the joint distribution is a table with 2ⁿ entries, and you need 2ⁿ − 1 independent numbers to specify it (the last is fixed because probabilities sum to 1). Five variables need 31 numbers — annoying but manageable. Twenty variables need 1,048,575 numbers. Fifty variables need more entries than you could store, let alone estimate from data. The joint distribution answers every possible query in principle, but it is exponentially expensive to write down, to learn, and to compute with.

Everything in this topic is a response to that blow-up. Conditional independence is the structural insight that lets us store the joint compactly. Variable elimination is the algorithm that lets us answer queries exactly without ever rebuilding the full table. Sampling is what we fall back on when even variable elimination is too expensive. Keep this storyline in mind — GATE conceptual questions often test whether you understand why each technique exists, not just how to run it.

Part 1: Conditional Independence Representation

What conditional independence means

Two random variables X and Y are independent if learning one tells you nothing about the other: P(X, Y) = P(X)·P(Y). Full independence is rare and boring. The workhorse concept is conditional independence: X and Y are conditionally independent given Z — written X ⟂ Y | Z — if, once you know Z, learning Y tells you nothing further about X:

P(X | Y, Z) = P(X | Z)    equivalently    P(X, Y | Z) = P(X | Z) · P(Y | Z)

Intuition: suppose a fever (X) and body ache (Y) are both caused by flu (Z). Fever and ache are clearly correlated — patients with fever are more likely to ache. But once the doctor knows the patient has flu, observing the fever adds nothing to her belief about the ache: the flu already explains both. The correlation between the symptoms flows entirely through the common cause. Conditional independence statements like this are what let us break a huge joint distribution into small local pieces.

Bayesian networks: the representation

A Bayesian network (belief network) is a directed acyclic graph (DAG) in which each node is a random variable and each node stores one small table: the conditional probability table (CPT) of that variable given its parents, P(X_i | Parents(X_i)). The network encodes a single global claim, the factorization of the joint distribution:

P(X₁, X₂, …, X_n) = ∏_i P(X_i | Parents(X_i))

The most famous example — and the one you should be able to reproduce from memory for the exam — is the burglary alarm network from Russell & Norvig. A house alarm (A) can be set off by a burglary (B) or an earthquake (E). Two neighbours, John (J) and Mary (M), may call you when they hear the alarm — each responds only to the alarm itself, not to the burglary or earthquake directly.

The saving comes from the conditional independence assumptions baked into the graph: each variable is conditionally independent of its non-descendants given its parents. John’s call depends on the burglary only through the alarm — so P(J | A, B, E) = P(J | A), and a 2-number table suffices where the naive approach would need a table over four variables. GATE has repeatedly asked exactly this style of question: given a DAG over binary variables, how many parameters are needed? The rule is mechanical: for each binary node with k binary parents, count 2^k numbers; sum over nodes.

Reading independence from the graph: d-separation

The second exam-critical skill is going the other way: given the graph, decide whether X ⟂ Y | Z holds. The tool is d-separation, and it reduces to understanding three tiny structures — every path in every network is built from them:

A path between X and Y is blocked by evidence set Z if it contains a chain or fork whose middle node is in Z, or a collider whose middle node (and all of its descendants) is not in Z. X and Y are d-separated by Z — hence conditionally independent given Z — if every path between them is blocked. The collider rule is the counter-intuitive one, and precisely because it is counter-intuitive, it is GATE’s favourite. In the alarm network, Burglary and Earthquake are marginally independent: the only path between them runs through the collider at Alarm, which is blocked while A is unobserved. But observe the alarm and the path opens: B and E become dependent. If the alarm rang and you then learn there was an earthquake, your belief in a burglary drops — the earthquake explains away the alarm. This “explaining away” effect (also called intercausal reasoning) is one of the most repeated conceptual questions across GATE CS and DA papers.

Worked micro-example. In the alarm network, is J ⟂ M | A? The paths between J and M all pass through A (J ← A → M is a fork). Observing A blocks the fork, so yes: given the alarm state, John’s and Mary’s calls are independent. Is J ⟂ M with no evidence? No — the fork is open, and the calls are correlated through the alarm. Is B ⟂ E | A? No — A is a collider between them, and observing it opens the path. Practise ten of these and the pattern becomes automatic; the GATE DA AI notes PDF includes a drill sheet of d-separation exercises with answers.

Part 2: Exact Inference Through Variable Elimination

The query, and the naive way to answer it

Inference means computing a posterior: given evidence e, what is P(Q | e) for some query variable Q? In the alarm network the classic query is: both John and Mary called — what is the probability of a burglary? Formally, P(B | j, m). By the definition of conditional probability, P(B | j, m) = α·P(B, j, m), where α is a normalization constant, and P(B, j, m) is obtained by summing the joint over the hidden variables (those that are neither query nor evidence — here E and A):

P(B | j, m) = α · Σ_e Σ_a P(B) P(e) P(a | B, e) P(j | a) P(m | a)

The naive algorithm — inference by enumeration — just evaluates this nested sum term by term. It works, but it is wasteful: sub-expressions like P(j | a)·P(m | a) get recomputed for every value of e, even though they don’t depend on e at all. On large networks enumeration is exponential in the number of hidden variables, with massive repeated work.

The fix: factors, and summing out variables one at a time

Variable elimination (VE) is dynamic programming applied to that sum. The idea has two parts. First, represent each CPT (with evidence values plugged in) as a factor — just a table over its remaining variables. Second, instead of expanding the whole sum, repeatedly do:

1. Pick a hidden variable to eliminate (say A).
2. Multiply all factors that mention A into one product factor (pointwise multiplication over shared variables).
3. Sum out A from that product, producing a new, smaller factor that no longer mentions A.
4. Repeat until only the query variable remains; multiply what’s left and normalize.

The algebraic trick underneath is nothing more than distributivity — pushing each summation inwards past every factor that doesn’t involve the summed variable:

P(B | j, m) = α · P(B) Σ_e P(e) Σ_a P(a | B, e) P(j | a) P(m | a)

Fully worked example on the alarm network

Use the standard textbook numbers: P(b) = 0.001, P(e) = 0.002; P(a | b, e) = 0.95, P(a | b, ¬e) = 0.94, P(a | ¬b, e) = 0.29, P(a | ¬b, ¬e) = 0.001; P(j | a) = 0.90, P(j | ¬a) = 0.05; P(m | a) = 0.70, P(m | ¬a) = 0.01. Evidence: j and m are both true.

Step 1 — restrict evidence. Plugging in J = true and M = true turns P(J | A) and P(M | A) into factors over A alone: f_J(A) = [0.90, 0.05] and f_M(A) = [0.70, 0.01] (entries for a, ¬a).

Step 2 — eliminate A. Multiply the three factors that mention A — f(A | B, E), f_J(A), f_M(A) — and sum over A:

Step 3 — eliminate E. Multiply f₁(B, E) by P(E) and sum over E: f₂(b) = 0.002 × 0.598525 + 0.998 × 0.59223 ≈ 0.59224; f₂(¬b) = 0.002 × 0.183055 + 0.998 × 0.0011295 ≈ 0.0014935.

Step 4 — multiply by the prior and normalize. Unnormalized: P(b)·f₂(b) = 0.001 × 0.59224 = 0.00059224; P(¬b)·f₂(¬b) = 0.999 × 0.0014935 = 0.00149200. Normalizing: P(b | j, m) = 0.00059224 / (0.00059224 + 0.00149200) ≈ 0.284. So even with both neighbours calling, the burglary probability is only about 28.4% — the priors are that strong. This exact computation, or a two-to-three-variable miniature of it, is the canonical 2-mark numerical from this block.

Why elimination order matters

The cost of VE is dominated by the largest factor created along the way. Eliminating variables in a bad order can create factors over many variables (exponentially large tables); a good order keeps factors small. For polytrees (networks with no undirected cycles), VE runs in time linear in the network size. In general graphs, the best achievable largest-factor size is governed by a graph property called treewidth, and exact inference in arbitrary Bayesian networks is NP-hard. That single sentence — exact inference is NP-hard in general, hence approximate methods — is the bridge to Part 3, and a favourite 1-mark conceptual statement in exams. For GATE purposes remember: order affects efficiency, never correctness; any order gives the same posterior.

Part 3: Approximate Inference Through Sampling

When the network is too big or too densely connected for exact inference, we estimate posteriors by Monte Carlo sampling: generate many random complete assignments (“worlds”) from the distribution the network defines, and answer queries by counting. Sampling trades exactness for scalability — estimates converge to the true value as the number of samples N grows, at a rate of roughly 1/√N.

Prior (forward) sampling

The basic generator: visit variables in topological order (parents before children); sample each variable from its CPT given the already-sampled values of its parents. One pass produces one complete world; the probability of generating a particular world equals exactly its joint probability under the network — which is what makes counting valid. To estimate P(b), generate N samples and report the fraction with B = true. Simple, unbiased, and the foundation for everything else.

Rejection sampling

For conditional queries P(Q | e), the direct fix is rejection sampling: generate worlds by prior sampling, throw away every sample that contradicts the evidence, and estimate P(Q | e) as the fraction of surviving samples with the query value. It is correct — but brutally wasteful when evidence is unlikely. In the alarm network, the evidence “John and Mary both called” occurs in roughly 0.2% of random worlds; to keep 1,000 usable samples you must generate about 500,000. As the number of evidence variables grows, the acceptance rate falls exponentially. GATE loves this fact as an MCQ: the main drawback of rejection sampling is that it rejects too many samples when evidence probability is low.

Likelihood weighting

Likelihood weighting repairs the waste: never sample evidence variables at all — fix them to their observed values — and sample only the non-evidence variables, again in topological order. Because forcing evidence distorts the distribution, each sample carries a correction weight: the product of P(e_i | parents(e_i)) for every evidence variable, evaluated at that sample’s parent values. The posterior estimate is then a weighted count. Every sample is used, which makes likelihood weighting far more efficient than rejection sampling — though with many or downstream evidence variables, most weight can concentrate in a few samples, degrading accuracy. Beyond these, Gibbs sampling (an MCMC method that repeatedly resamples one non-evidence variable at a time conditioned on its Markov blanket) is the standard next step — know its one-line description for safety, but the GATE DA syllabus phrase “approximate inference through sampling” centres on the three algorithms above.

Exact vs. Approximate: The One-Table Summary

How GATE Actually Tests This Block

• Parameter counting: given a DAG over binary variables, compute the number of independent CPT entries. Mechanical marks if you know the 2^k-per-node rule.
• d-separation / independence: “Which of the following independence statements hold in the network?” Draw the three canonical structures in the margin and check each path. Watch for the collider trap and explaining away.
• Small numerical inference: a 3–4 node network with CPTs given; compute a posterior by hand. This is variable elimination in miniature — practise the alarm computation above until it takes you under four minutes.
• Sampling concepts: which algorithm wastes samples, what likelihood weights equal, why approximate inference is needed at all (NP-hardness of exact inference), and the 1/√N convergence behaviour.
• Bayes’ theorem crossovers: this block overlaps heavily with Probability & Statistics — a diagnosis-style Bayes question can be asked from either section, which effectively doubles this topic’s weightage.

A 10-Day Plan to Finish This Topic

1. Days 1–2: conditional probability, chain rule, Bayes’ theorem refresher; the joint-distribution blow-up argument.
2. Days 3–4: Bayesian network semantics — factorization, parameter counting, building the alarm network from its story.
3. Days 5–6: the three canonical structures and d-separation; do at least 15 independence-checking drills; internalize explaining away.
4. Days 7–8: variable elimination — reproduce the P(B | j, m) computation on paper twice without notes; then vary the query and evidence.
5. Day 9: the three sampling algorithms; be able to state each in three lines and name its weakness.
6. Day 10: PYQs from GATE DA and GATE CS on Bayesian reasoning, plus a timed sectional test.

FAQs on Reasoning Under Uncertainty for GATE DA

How many marks does reasoning under uncertainty carry in GATE DA?

Within the AI section (typically 8–10 marks), reasoning under uncertainty is usually good for 2–4 marks — and Bayes-theorem-style questions can additionally appear under Probability & Statistics, making this one of the best-value topics in the paper.

Do I need to memorize the variable elimination algorithm formally?

You need to be able to execute it on a small network: restrict evidence, multiply factors sharing a variable, sum the variable out, normalize at the end. GATE tests the computation and the concepts (order affects cost not correctness; largest factor dominates cost), not pseudocode recall.

Is Gibbs sampling in the GATE DA syllabus?

The syllabus says “approximate inference through sampling”, which centres on prior sampling, rejection sampling and likelihood weighting. Know Gibbs sampling at the definition level (resample one variable at a time given its Markov blanket) — it costs you two minutes and covers the edge case.

What is “explaining away” in one line?

When two independent causes share an observed effect, confirming one cause lowers the probability of the other — observing the collider makes previously independent parents dependent. In the alarm network: alarm rang, earthquake confirmed ⇒ burglary becomes less likely.

Which book should I use for this topic?

Russell & Norvig, “Artificial Intelligence: A Modern Approach” — the chapters on probabilistic reasoning and Bayesian networks map one-to-one onto the GATE DA syllabus. Pair it with the full GATE DA book list and the notes PDF above for revision.

Reasoning under uncertainty rewards exactly the kind of preparation GATE DA favours: a small, precisely defined syllabus, one canonical example network, three algorithms, and question patterns that repeat. Learn the alarm network cold, drill d-separation until the collider rule feels natural, work the variable elimination example until it is mechanical, and be able to rank the sampling algorithms by their weaknesses. Do that, and this block becomes guaranteed marks. For the wider AI section strategy, see the GATE DA Syllabus 2027 breakdown and the 6-month preparation plan.