Probabilistic Reasoning and Bayesian Networks

An agent may see only part of its environment. A sensor can be noisy, and an action can have several outcomes. Probability lets the agent attach a degree of belief to each possibility and revise those beliefs when information arrives.

Worlds, events and variables

The sample space, $\mathrm{\Omega }$, lists every possible outcome. Its outcomes are mutually exclusive and exhaustive: exactly one occurs. An event is a set of these outcomes, such as "the bus is late." Its probability is the sum of the probabilities of its outcomes.

A random variable assigns a value to each outcome. Its domain lists the possible values. For example, $Weather$ has the domain $\{sun,cloud,rain\}$. Write variables with capital letters and values in lowercase. For Boolean $Rain$, $r$ means true and $\mathrm{\neg }r$ means false. The comma in $P(r,t)$ means "and."

Probabilities lie between 0 and 1, and the probabilities of all outcomes sum to 1. Complementary events satisfy $P(\mathrm{\neg }a)=1-P(a)$. A distribution lists the probability of each value of a variable; a prior describes belief before incorporating the evidence of interest.

Read a joint table

A joint distribution gives the probability of each combination of values. Here is a weather and bus model:

The six cells are the six possible worlds, and together they sum to 1. A row total is the probability of that weather, so a row need not sum to 1. For rain, $P(rain)=0.08+0.12=0.20$. The late column gives $P(late)=0.10+0.12+0.12=0.34$.

This operation is marginalization, or summing out. To keep $X$ and remove $Y$, use $P(x)={\sum }_{y}P(x,y)$. Add across every value of the variable being removed, including false values for Boolean variables.

Count an overlap once

The event "rain or late" includes every cell in the rain row or late column. Its probability is

The subtraction removes the overlap counted twice. In general, $P(a\vee b)=P(a)+P(b)-P(a,b)$. Simply adding the marginals would give 0.54 and count the rainy, late world twice.

Why full tables become expensive

A full joint table can answer any probability query about its variables, but its size grows quickly. Each additional Boolean variable doubles the number of worlds. With $n$ Boolean variables there are $2^n$ entries and $2^n-1$ free numbers, since the last entry is fixed by the total of 1. Thirty Boolean variables require 1,073,741,824 entries. Compact models will store local dependencies instead of listing every world explicitly.

A late bus changes which weather conditions seem likely. Conditional probability focuses on the worlds consistent with an observation, then measures their relative shares. The probability after taking evidence into account is a posterior.

Keep the denominator tied to the evidence

For evidence with positive probability,

In the weather and bus model, the late entries for sun, cloud and rain are 0.10, 0.12 and 0.12. Their total is 0.34. Thus $P(rain\mid late)=0.12\mathrm{/}0.34\approx 0.353$. Reversing the question gives $P(late\mid rain)=0.12\mathrm{/}0.20=0.6$. Both use the same joint cell, but each divides by the probability of its own evidence.

The whole conditional distribution is $P(Weather\mid late)\approx ⟨0.294,0.353,0.353⟩$. These entries sum to 1 because they describe alternative weather values under one fixed observation. The three likelihoods $P(late\mid sun)=0.2$, $P(late\mid cloud)=0.4$ and $P(late\mid rain)=0.6$ use different conditions and need not sum to 1.

Products and chains

Rearranging the definition gives the product rule:

Applying it repeatedly gives the chain rule:

Any variable order works. Independence is not needed for this identity; it will later let us shorten the condition lists.

Select, sum and normalize

For query variable $X$, evidence $e$ and hidden variables $Y$, enumeration uses

First select worlds matching the evidence. Next sum out all hidden variables, keeping a separate total for each query value. Finally divide these totals by their sum. The normalizing constant $\alpha$ is the reciprocal of that sum, which is $P(e)$.

Consider Boolean variables Flu ($F$), Fever ($V$) and Cough ($K$). Their full joint table is:

To find $P(F\mid v)$, retain fever rows and sum out cough. The totals are $0.056+0.024=0.08$ for flu and $0.018+0.072=0.09$ for no flu. Normalize by 0.17 to get $P(f\mid v)\approx 0.471$.

If cough is also observed, retain only the two fever-and-cough rows. Now $P(f\mid v,k)=0.056\mathrm{/}0.074\approx 0.757$. For fever without cough, $P(f\mid v,\mathrm{\neg }k)=0.024\mathrm{/}0.096=0.25$. Summing over cough would lose this additional observation. A raw total such as 0.08 is a joint probability, not the requested conditional probability.

An agent often knows how a cause produces an observation, but needs to reason in the other direction. A fault model may describe how often a damaged component triggers a warning. After the warning, the agent needs the probability of damage.

Reverse a conditional correctly

The two product-rule expressions for a joint probability give Bayes' rule:

Here $P(c)$ is the prior, $P(e\mid c)$ is the likelihood, and $P(c\mid e)$ is the posterior. The denominator includes every way the evidence can occur. For a Boolean cause, the law of total probability gives

For more than two cause values, include one term for each value. You can also compute a likelihood-times-prior score for each cause and normalize the scores.

Work through a rare-condition example

Suppose an illness affects 1% of a population. A test is positive for 90% of ill people and 5% of healthy people. The probability of a positive result is

The ill-and-positive probability is 0.009, so

Natural frequencies make the denominator easier to see. Among 10,000 people, 100 are ill and 90 of those test positive. Of 9,900 healthy people, 495 test positive. There are 585 positive results altogether; 90 belong to ill people.

The 90% sensitivity answers "How often does an ill person test positive?" It does not answer "How often is a positive person ill?" Base-rate neglect gives the prior too little weight. A rare condition starts with far fewer people, so false positives from the larger healthy group can outnumber true positives. If sensitivity and false-positive rate stay fixed, changing the prevalence still changes the posterior.

A negative result uses the complementary likelihoods:

Update again when new evidence arrives

The posterior from one observation becomes the prior for the next. If a second test result is conditionally independent of the first given illness status, another positive produces

Carry the unrounded first posterior when doing sequential arithmetic. Conditional independence matters: repeated readings from the same faulty sensor may share an error, so multiplying their likelihoods as independent evidence can overstate the update.

Background information stays in every relevant condition:

This lets an agent update within the population or situation it already knows about, using its current prior and the appropriate likelihoods.

Some observations change one another's probabilities; others add no information once a relevant condition is known. Independence identifies when a long probability expression can be replaced by smaller pieces.

Independence is a statement about every value

Events are independent when $P(a,b)=P(a)P(b)$. For variables, this equality must hold for every pair of values. One failed pair establishes dependence. In the weather table, $P(rain,late)=0.12$, whereas $P(rain)P(late)=0.20(0.34)=0.068$, so weather and bus status are dependent.

Mutually exclusive events with positive probabilities are dependent: learning that one occurred forces the other's probability to zero. Independent events can occur together. If $n$ Boolean variables are all mutually independent, only $n$ probabilities are needed, compared with $2^n-1$ for an unrestricted joint table.

Know what is being held fixed

Conditional independence, written $X\perp Y\mid Z$, means

The equality holds for every relevant value combination. Equivalently, learning $Y$ adds nothing about $X$ once $Z$ is known.

In the flu model, $P(k\mid v,f)=P(k\mid f)=0.7$ and $P(k\mid v,\mathrm{\neg }f)=P(k\mid \mathrm{\neg }f)=0.2$. Fever and cough are conditionally independent given flu status. Without that condition, they are dependent: $P(k)=0.25$, while $P(k\mid v)=0.074\mathrm{/}0.17\approx 0.435$. Fever changes belief about flu, which changes belief about cough.

Independence without evidence and independence given evidence are separate claims. Observing a common effect can even make two previously independent causes dependent.

Classify with naive Bayes

A naive Bayes model assumes that features are conditionally independent given a class. Its posterior is

A Boolean class with $n$ Boolean features needs $1+2n$ probabilities. The assumption can be imperfect and still support useful classification, but correlated features can lead to overconfident probabilities.

For spam, let $P(spam)=0.3$. The word "offer" appears with probability 0.4 in spam and 0.05 in nonspam, called ham. The word "winner" appears with probabilities 0.2 and 0.01. With both words present, the scores are $0.3(0.4)(0.2)=0.024$ for spam and $0.7(0.05)(0.01)=0.00035$ for ham. Normalizing gives $P(spam\mid o,w)\approx 0.986$.

Absence also supplies evidence. With "offer" present but "winner" absent, the scores become $0.3(0.4)(0.8)=0.096$ and $0.7(0.05)(0.99)=0.03465$, giving a spam posterior of about 0.735. Use the complement of the likelihood for an absent Boolean feature. A zero likelihood makes the entire class score zero, so a possible event should not receive a zero merely because it was missing from a small data sample.

A Bayesian network represents a joint distribution with a directed acyclic graph and local probability tables. Each node is a random variable. An arrow into a node identifies one of its parents; following arrows must never lead back to the starting node.

A commute model

Use five Boolean variables: Rain ($R$), Accident ($A$), heavy Traffic ($T$), being Late ($L$) and carrying an Umbrella ($U$). The arrows are $R\to T$, $A\to T$, $T\to L$ and $R\to U$. Rain and accident have prior probabilities $P(r)=0.2$ and $P(a)=0.1$.

Traffic's conditional probability table (CPT) depends on both parents:

The remaining tables give $P(l\mid t)=0.6$, $P(l\mid \mathrm{\neg }t)=0.1$, $P(u\mid r)=0.9$ and $P(u\mid \mathrm{\neg }r)=0.2$. Each parent assignment selects a distribution over the child's values. For Boolean nodes, store only the true probability; the false probability is its complement. Thus $P(\mathrm{\neg }t\mid r,\mathrm{\neg }a)=0.3$.

Compute a complete world's probability

The network defines its joint distribution by

For rain, no accident, heavy traffic, lateness and an umbrella, select one entry from every node:

The factors respectively describe rain, no accident, traffic under those parent values, lateness under heavy traffic and umbrella use under rain. Omitting a node gives an incomplete product. Selecting 0.95 for traffic would describe an accident too, so it would mismatch the world being evaluated.

The formula follows from the chain rule in a topological order, with parents before children. The network's conditional independences shorten each condition from all preceding variables to just its parents.

Count parameters and distinguish marginals

A Boolean node with $k$ Boolean parents needs $2^k$ free probabilities. More generally, a node with $d$ values and $k$ parents each with $d$ values needs $(d-1)d^k$. The commute network needs $1+1+4+2+2=10$ numbers; a full joint over its five Boolean variables needs 31. Thirty Boolean nodes with at most five parents each need at most 960 numbers, compared with more than a billion for an unrestricted full joint.

A CPT entry answers a question with every parent fixed. To find a marginal, average over the missing parent values. Here

where the four terms weight the traffic rows by their parent probabilities. Similarly, $P(t\mid r)=0.1(0.95)+0.9(0.7)=0.725$. It is not the single row value 0.7.

Arrows often follow cause to effect because that makes the model compact and understandable. Formally they encode a factorization and independence claims. A reversed two-node graph can represent the same joint distribution with different tables; an arrow alone does not establish causation.

A useful network leaves out dependencies that are unnecessary while keeping those the distribution needs. Choosing few parents can save many table entries, but each omission commits the model to an independence claim.

Build the network in an order

Choose variables and their domains, then order the variables. For each variable, select a minimal set of earlier variables that makes it independent of the other earlier variables. Add arrows from these parents and fill its CPT using expert judgment or probabilities estimated from counts.

A cause-first order for the commute model produces four arrows and ten free probabilities. Another valid order is $L,T,U,R,A$, with parent sets $T:\{L\}$, $U:\{T\}$, $R:\{T,U\}$ and $A:\{T,R\}$. This uses six arrows and $1+2+2+4+4=13$ numbers. Given traffic, rain changes belief about an accident, so rain must remain among accident's parents in that order.

Any order can represent the distribution if each node receives enough parents. Giving every node all earlier nodes always works but offers no compression. A diagnostic order can also require probabilities that are harder to judge, such as rain given traffic and an umbrella. Omitting a needed parent forces a false independence; adding an unnecessary parent enlarges the table.

Two local independence rules

The local Markov property says a node is independent of its non-descendants given its parents. In the commute network, $L\perp \{R,A,U\}\mid T$ and $U\perp \{A,T,L\}\mid R$. Once traffic is known, the other variables add nothing about lateness.

A node's Markov blanket contains its parents, its children and its children's other parents. Given these variables, the node is independent of every variable outside the blanket. Rain's blanket is $\{T,U,A\}$: accident belongs because it is traffic's other parent. Traffic's blanket is $\{R,A,L\}$, and lateness has only $\{T\}$. The blanket allows local updates even when the full network is large.

Replace a large table with structure

A deterministic node is a fixed function of its parents, such as $Late=Traffic\vee Strike$. Its rows contain zeros and ones. A noisy-OR allows each true cause to fail independently. If cause $i$ has inhibition probability $q_i$, the effect is absent only if all active causes fail:

Suppose an accident fails to cause a jam with probability 0.2 and roadworks fail with probability 0.4. An accident alone gives a jam probability of 0.8; roadworks alone gives 0.6. When both occur, the no-jam probability is $0.2(0.4)=0.08$, so the jam probability is 0.92.

Plain noisy-OR gives no effect when no cause is active. A leak, represented as an always-present cause, allows the effect to arise from unlisted causes. The model uses one inhibition probability per cause instead of an unrestricted table with $2^k$ rows. This saving comes from independent causal failures; arbitrary interactions require a richer model.

d-separation finds conditional independences guaranteed by a network's graph. It considers paths without requiring arrows to point along the direction of travel. Arrowheads still matter because they determine how each middle node behaves.

Three path patterns

In a chain, knowing the middle variable screens off the earlier variable. In $R\to T\to L$, rain adds nothing about lateness once traffic is known. In a fork, knowing the shared cause does the same: an umbrella adds nothing about traffic once rain is known.

A collider, or common effect, works in the opposite way. The path $R\to T\leftarrow A$ is blocked without evidence at traffic or its descendants. Observing traffic, or observing lateness downstream, opens the collider. Causes that were independent can then inform one another.

Explaining away

In the commute model, $P(a\mid r)=P(a)=0.1$. Heavy traffic increases the accident probability to about 0.235. Adding rain reduces it to $P(a\mid t,r)\approx 0.131$; adding no rain gives $P(a\mid t,\mathrm{\neg }r)\approx 0.308$. Rain accounts for some of the observed traffic, reducing the need for an accident as an explanation. This is explaining away.

Check every path

To test $X\perp Y\mid Z$:

1. List every undirected path between the query variables.
2. At each internal node, identify whether the path forms a collider or a non-collider.
3. Block a path if it has an observed non-collider, or a collider with neither itself nor any descendant observed.
4. Conclude d-separation only if every path is blocked.

For umbrella and accident, the only path is $U\leftarrow R\to T\leftarrow A$. With no evidence, traffic blocks it, so $U\perp A$. Given lateness, traffic's collider opens and rain remains unobserved, so the path becomes active. The numerical model gives $P(u\mid l)\approx 0.434$ but $P(u\mid a,l)\approx 0.356$.

If both lateness and rain are observed, traffic's collider is still open, but rain blocks the path as an observed non-collider. Therefore $U\perp A\mid L,R$. Opening one part of a path does not overcome a block elsewhere.

Umbrella and lateness have path $U\leftarrow R\to T\to L$. It is active without evidence and blocked by either rain or traffic. For example, $P(l\mid u,r)=P(l\mid r)=0.4625$.

Interpret the graph's guarantee

d-separation is sound: the independence holds for every distribution that follows the graph. An active path means independence is not guaranteed. Particular CPT values may still make the variables independent by coincidence. In a graph with several paths, inspecting one blocked path is insufficient; another path may remain active.

A network stores a joint distribution as local pieces. Exact inference combines those pieces to answer a query, adding over variables whose values remain unknown. Enumeration is the direct way to do this.

Separate the three variable roles

In $P(X\mid e)$, $X$ is the query variable and $e$ fixes the evidence. Every other variable is hidden. Substitute the network product into the general enumeration formula:

Compute an unnormalized total for every value of the query, then divide by their sum. Evidence values stay fixed in every product. Hidden variables range over their entire domains.

For the commute model, with arrows $R\to T\leftarrow A$, $T\to L$ and $R\to U$, the query $P(R\mid l)$ hides accident, traffic and umbrella. Each complete term uses $P(R)P(A)P(T\mid R,A)P(l\mid T)P(U\mid R)$.

Remove an irrelevant leaf

Umbrella has no observed descendant and is neither the query nor evidence. Summing its CPT over both values gives ${\sum }_{u^{\mathrm{\prime }}}P(u^{\mathrm{\prime }}\mid r)=1$ for each rain value. Its contribution disappears.

More generally, retain query variables, evidence variables and all their ancestors. Other variables can be removed by summing irrelevant leaves first, then working backward. This is a statement about their contribution to this query; an unobserved node can matter in a different query.

Evaluate the two rain totals

The commute tables give $P(r)=0.2$, $P(a)=0.1$, traffic probabilities 0.95, 0.7, 0.8 and 0.2 for parent combinations $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$, and lateness probabilities 0.6 with traffic and 0.1 without it.

For rain and an accident, sum the traffic alternatives: $0.95(0.6)+0.05(0.1)=0.575$. For rain without an accident, the result is $0.7(0.6)+0.3(0.1)=0.45$. Weight by accident probabilities, then by rain:

For no rain, the corresponding inner totals are 0.5 and 0.2, giving

Normalize by $0.0925+0.184=0.2765$. The answer is $P(R\mid l)\approx ⟨0.335,0.665⟩$ for true and false. Reporting 0.0925 would report the joint event, before conditioning.

Keep sums attached to their dependencies

A factor moves outside a sum only if none of its arguments depends on the summed variable. For example, $P(r)$ can move outside the accident sum; $P(t\mid r,a^{\mathrm{\prime }})$ cannot because accident is a parent argument.

If umbrella is observed, it no longer sums away. With $P(u\mid r)=0.9$ and $P(u\mid \mathrm{\neg }r)=0.2$, the new posterior is $0.08325\mathrm{/}(0.08325+0.0368)\approx 0.693$. Enumeration can run depth-first with little memory, but visits exponentially many hidden assignments and repeats partial calculations.

Enumeration repeats work because many complete worlds share the same partial calculation. Variable elimination (VE) stores these partial results as factors and reuses them. It computes the same exact posterior in a different arithmetic order.

Factors, joins and evidence

A factor maps assignments of its variables to nonnegative numbers. CPTs are starting factors, but intermediate factors need not sum to 1. Apply evidence by retaining the observed value. For lateness evidence, $P(l\mid T)$ is a factor over traffic with entries 0.6 and 0.1.

Joining factors multiplies matching entries and uses the union of their variable sets. Joining $P(A)$ and $P(T\mid R,A)$ gives a factor over rain, accident and traffic. Summing out accident adds entries that differ only in accident's value.

For each hidden variable, join every factor containing it, sum it out, and replace those factors with the result. Keep factors that do not mention it. At the end, join the remaining factors and normalize over the query values.

Eliminate accident, then traffic

For $P(R\mid l)$, remove the unobserved umbrella leaf. Start with $P(R)$, $P(A)$, $P(T\mid R,A)$ and $P(l\mid T)$. Eliminating accident gives

Its true-traffic values are $f_1(r,t)=0.1(0.95)+0.9(0.7)=0.725$ and $f_1(\mathrm{\neg }r,t)=0.1(0.8)+0.9(0.2)=0.26$. The false-traffic values are 0.275 and 0.74.

Now eliminate traffic:

This gives $f_2(r)=0.725(0.6)+0.275(0.1)=0.4625$ and $f_2(\mathrm{\neg }r)=0.26(0.6)+0.74(0.1)=0.23$. Multiplying by the rain prior gives $⟨0.0925,0.184⟩$. Divide by 0.2765 to get $⟨0.335,0.665⟩$.

Eliminating traffic first also works. The factor $g(R,A)={\sum }_{t^{\mathrm{\prime }}}P(t^{\mathrm{\prime }}\mid R,A)P(l\mid t^{\mathrm{\prime }})$ has entries 0.575, 0.45, 0.5 and 0.2. Weighting by the accident prior then produces the same two lateness likelihoods.

Choose an order that keeps factors small

A factor over $k$ variables with $d$ values has $d^k$ entries. The largest intermediate scope usually dominates the cost. Suppose hidden $Z$ points to Boolean variables $X_1,\dots ,X_n$, each with an observed child $Y_i$, and the query is $X_n$. Eliminating $Z$ first joins a table over $Z,X_1,\dots ,X_n$, then leaves $2^n$ entries. Eliminating the other $X_i$ first instead reduces each branch to a factor over $Z$; the largest joined scope is just $Z,X_i$, with four entries.

A polytree has at most one undirected path between any two nodes. With a good order, inference is linear in total CPT size. General exact inference and finding the optimal elimination order are NP-hard. A practical heuristic chooses a variable creating a small next factor. Keep the query variable until normalization. Multiplying a whole factor by a positive constant leaves the normalized answer unchanged.

When exact sums are too expensive, an agent can simulate assignments and estimate probabilities from their frequencies. Sampling produces an approximation whose quality depends on how much useful information the draws contain.

Turn a random number into a value

Draw a uniform number $u$ from $[0,1)$. Split that interval into pieces with lengths equal to the probabilities. For weather probabilities $⟨0.5,0.3,0.2⟩$, sun occupies $[0,0.5)$, cloud $[0.5,0.8)$ and rain $[0.8,1)$. A draw of 0.63 gives cloud. For a Boolean variable, choose true if the draw is less than its true probability.

Sample parents before children

Prior sampling visits variables in topological order. Each node is sampled from the CPT row selected by its parents' sampled values. The word "prior" refers to drawing from the network before conditioning the sample population on query evidence.

In the commute model, use order $R,A,T,L,U$ and draws 0.13, 0.57, 0.40, 0.81 and 0.35:

1. Rain is true because $0.13<0.2$.
2. Accident is false because $0.57\ge 0.1$.
3. Traffic is true because $0.40<P(t\mid r,\mathrm{\neg }a)=0.7$.
4. Late is false because $0.81\ge P(l\mid t)=0.6$.
5. Umbrella is true because $0.35<P(u\mid r)=0.9$.

The assignment is $(r,\mathrm{\neg }a,t,\mathrm{\neg }l,u)$. Its generation probability is $0.2(0.9)(0.7)(0.4)(0.9)=0.04536$, exactly its probability under the network's joint distribution. Sampling a child before its parents would leave the needed CPT row undecided.

Estimate probabilities from counts

The fraction of prior samples with lateness estimates $P(l)$, which is 0.2765 in this model. The estimator is consistent: as the number of independent draws grows, it converges to the true probability. A larger run can still fluctuate. Typical independent-sample error scales as $1\mathrm{/}\sqrt{N}$, so four times as many samples roughly halves the error; twice as many does not.

Condition with rejection sampling

Rejection sampling generates prior assignments and discards those that contradict the evidence. Count query values only among the retained assignments. For example, suppose 280 of 1,000 assignments have lateness and 94 of those also have rain. Then $P(r\mid l)\approx 94\mathrm{/}280\approx 0.336$. Dividing by 1,000 would estimate the joint event rain-and-lateness instead.

A sample may be abandoned as soon as it conflicts with an observation, saving the remaining simulation work. The expected retained fraction is still $P(e)$. Lateness alone retains about 28%; lateness with an umbrella retains about 12%, since $P(l,u)=0.12005$. Many observations can make the evidence combination rare even when each observation is ordinary on its own. If no samples survive, the conditional estimate is undefined and more useful sampling is needed.

Rejection sampling spends time creating assignments it cannot use. Likelihood weighting keeps every evidence variable fixed and compensates with a weight. Samples whose hidden values make the evidence likely contribute more.

Build a weighted assignment

Start each sample with weight 1. Visit nodes in topological order. Sample a non-evidence node using its parents' current values. At an evidence node, retain its observed value and multiply the weight by that value's CPT probability:

Only evidence probabilities enter this weight. The probabilities of the sampled nodes already govern how frequently their assignments are generated. Multiplying those probabilities into the weight would count them twice.

Two samples in the commute model

For $P(R\mid l,u)$, keep lateness and umbrella true. Sample rain, accident and traffic. The traffic probabilities for $(r,a),(r,\mathrm{\neg }a),(\mathrm{\neg }r,a),(\mathrm{\neg }r,\mathrm{\neg }a)$ are 0.95, 0.7, 0.8 and 0.2, with priors $P(r)=0.2$ and $P(a)=0.1$.

Using draws 0.13, 0.57 and 0.40 gives rain, no accident and heavy traffic. The fixed lateness contributes $P(l\mid t)=0.6$; the fixed umbrella contributes $P(u\mid r)=0.9$. The sample's weight is $0.6(0.9)=0.54$.

Draws 0.66, 0.05 and 0.92 instead give no rain, an accident and no heavy traffic. The evidence likelihoods are now $P(l\mid \mathrm{\neg }t)=0.1$ and $P(u\mid \mathrm{\neg }r)=0.2$, so the weight is 0.02. Both samples match the evidence because those values were fixed, yet their contributions differ greatly.

Normalize weights, not sample counts

Estimate a query probability by

The two-sample rain estimate is $0.54\mathrm{/}(0.54+0.02)\approx 0.964$. That is far from the exact posterior of about 0.693; two draws are too few to represent the relevant hidden assignments. With many draws, the weighted ratio converges to the posterior. Dividing 0.54 by two would not produce a conditional probability estimate.

The correction works because multiplying the sampling probability by the evidence weight recovers the full joint product. Normalizing removes the shared evidence probability and leaves the conditional distribution.

Recognize concentrated weights

Fixed evidence affects how its descendants are sampled, since they use that evidence in their parent rows. Upstream variables are still drawn without feedback from downstream observations. If rare evidence sits at leaf nodes, most upstream assignments may explain it poorly. Their weights are tiny, and a few assignments can dominate the result.

Likelihood weighting often uses computation more efficiently than rejection sampling, but "no rejected samples" does not mean equally informative samples. A long run with highly uneven weights can still give an unstable estimate. Inspect which assignments carry the total weight when comparing results across runs.

Gibbs sampling keeps a complete assignment and changes one non-evidence variable at a time. Each change is drawn from the variable's conditional distribution given the current values of all other variables. The sequence forms a Markov chain Monte Carlo, or MCMC, sampler.

Start a chain and keep evidence fixed

Set evidence to its observed values and initialize the remaining variables. With deterministic zeros, start from an evidence-compatible assignment with positive joint probability. Choose a non-evidence variable to update, calculate a probability for each of its possible values, normalize, and draw the new value. All other values stay in place for that step. Repeating this process allows evidence to affect upstream as well as downstream beliefs.

Only the selected node's Markov blanket is needed: its parents, children and children's other parents. Factors outside that blanket do not change when the selected value changes, so they cancel in normalization. The local formula is

Children keep their current values while each candidate value of the selected parent is tried. Their CPT entries can therefore change even though the children themselves are not resampled.

Update rain in the commute model

Keep lateness and umbrella true. Suppose the current hidden state is no rain, no accident and heavy traffic. Rain's blanket is traffic, umbrella and accident. For rain true, the local score is

For rain false, the score is $0.8(0.2)(0.2)=0.032$. Normalizing gives $P(r\mid \text{blanket})=0.126\mathrm{/}0.158\approx 0.797$. A uniform draw of 0.40 therefore changes rain to true. Lateness's factor is absent from this update because traffic stays fixed and that factor is constant across the two rain candidates.

Update traffic with the new rain value

Traffic's blanket is rain, accident and lateness. Its two scores are $0.7(0.6)=0.42$ for heavy traffic and $0.3(0.1)=0.03$ for no heavy traffic. Thus its true probability is $0.42\mathrm{/}0.45\approx 0.933$. For an accident update with rain and heavy traffic fixed, the true probability is $0.095\mathrm{/}(0.095+0.63)\approx 0.131$.

Count states and allow time to mix

After each update, the full assignment can count as a sample, including a step that leaves the selected value unchanged. Discard an initial burn-in period to reduce the influence of initialization. A long-run rain frequency approaches about 0.693 for this query when the chain converges.

Adjacent states share nearly all their values and are correlated. They carry less independent information than the same number of independent draws. With all CPT entries strictly between 0 and 1, suitable repeated updates can reach every state and converge to the posterior. Deterministic constraints can trap a single-variable chain; nearly deterministic relationships can make it move very slowly.

Prior sampling draws from the joint; rejection filters those draws; likelihood weighting fixes evidence and weights assignments; Gibbs repeatedly updates a fixed-evidence state. Conditioning only on parents would turn a Gibbs update into the wrong local distribution by omitting children's evidence.

Probabilities describe what may happen; utilities describe how desirable the outcomes are. A utility function assigns higher numbers to preferred outcomes. An uncertain action is a lottery, listing outcomes and their probabilities.

Average utility across possible outcomes

The expected utility of an action is

Multiply each outcome's utility by its probability and add. Maximum expected utility (MEU) chooses the action with the largest result. The outcome with the highest individual utility need not belong to the best action, and the most likely outcome alone does not determine the choice. A sound decision can still produce a bad outcome through chance.

Why coherent preferences support MEU

Utility theory uses these rationality requirements:

• Orderability: any two lotteries can be compared, allowing indifference.
• Transitivity: preferring A to B and B to C entails preferring A to C.
• Continuity: an intermediate outcome can be matched by a lottery between better and worse outcomes.
• Substitutability: an indifferent outcome or lottery can replace another within a larger lottery.
• Monotonicity: between lotteries with the same better and worse outcomes, prefer the larger probability of the better outcome.
• Decomposability: a lottery over lotteries reduces to its final outcome probabilities.

The von Neumann–Morgenstern result represents preferences satisfying these requirements by expected utility. Cyclic preferences violate transitivity. If an agent pays a small amount to move from B to A, A to C and C to B, repeated trades return it to its original position while draining its money. This is the "money pump" problem.

Money and utility can rank lotteries differently

Compare a sure payment of 400 with a 50% chance of 1,000 and a 50% chance of zero. Expected money favors the lottery, whose mean is 500. For $U(x)=\sqrt{x}$, however, the lottery's expected utility is $0.5\sqrt{1000}+0.5\sqrt{0}\approx 15.81$, while the sure payment gives 20. This agent chooses 400.

The certainty equivalent is the sure amount with the lottery's utility. Here it is $(0.5\sqrt{1000}{)}^2=250$. The difference between expected money and the certainty equivalent is the risk premium, 250 in this example.

With concave utility, a sure mean amount is at least as desirable as the lottery with that mean. Strict concavity makes that preference strict for a nontrivial lottery. A sufficiently favorable risky option can still beat a less valuable sure amount.

Change scales without changing preferences

Replacing utility by $U^{\mathrm{\prime }}(s)=kU(s)+c$ with $k>0$ preserves every expected-utility comparison. Each expectation receives the same positive scaling and shift. A general increasing transformation preserves rankings of certain outcomes but can change rankings of lotteries.

When comparing several desirable attributes, an option at least as good on every attribute and better on at least one dominates the other. With preferences that value those improvements, the dominated option can be removed without specifying exact attribute weights.

A decision network, also called an influence diagram, combines a probability model with choices and preferences. Solving it requires both inference about uncertain states and comparison of the actions available to the agent.

Read the three node types

Chance nodes, usually ovals, have probability tables. Decision nodes, usually rectangles, represent actions the agent controls. Utility nodes, usually diamonds, assign utility to combinations of parent values. An arrow into a decision node identifies information available when the choice is made. It is not an ordinary conditional-probability dependency.

For an outdoor event, rain influences a forecast and the event's utility. The action also influences utility. The forecast points into the decision when it is observed before the organizer chooses. There is no arrow from the action to rain: moving indoors does not change the weather.

Solve without a forecast

Suppose $P(rain)=0.3$, and use this utility table:

The expected utilities are $EU(outdoors)=0.7(100)+0.3(0)=70$ and $EU(indoors)=0.7(60)+0.3(70)=63$. Without further information, choose outdoors and the MEU is 70. The decision node receives a chosen value, not a probability table to average over actions.

Incorporate a forecast

Let $P(wet\mid rain)=0.8$ and $P(wet\mid \mathrm{\neg }rain)=0.1$. The wet forecast probability is $0.8(0.3)+0.1(0.7)=0.31$. Bayes' rule gives $P(rain\mid wet)=0.24\mathrm{/}0.31\approx 0.774$. A dry forecast gives $P(rain\mid dry)=0.06\mathrm{/}0.69\approx 0.087$.

With a wet forecast, outdoors has expected utility about 22.6 and indoors about 67.7, so choose indoors. With a dry forecast, outdoors gives about 91.3 and indoors about 60.9, so choose outdoors. Use the posterior after an observation; retaining the prior would discard the information the forecast supplies.

The resulting policy is "Choose indoors after wet; choose outdoors after dry." A policy maps observations to actions, so it can be specified before the observation arrives. An action is the single choice made once its information is available.

Find where the choice changes

Let $p$ be the current probability of rain. Then $EU(outdoors)=100(1-p)$ and $EU(indoors)=60(1-p)+70p=60+10p$. Equating them gives $40=110p$, or $p=4\mathrm{/}11\approx 0.364$. Below this threshold choose outdoors; above it choose indoors; at the threshold the actions tie.

To solve another decision network, fix the current evidence, consider each action in turn, infer the chance distribution relevant to utility, and calculate its expected utility. If an action changes an uncertain outcome, include that action's effects in the probability model before comparing expectations. Finally select the best action separately for each possible observation that the policy will receive.

An observation is valuable when it helps the agent choose a better action. The value of perfect information (VPI) measures the expected improvement from learning a variable's value before acting. "Perfect" describes access to that variable's actual value; the variable can itself be an imperfect forecast of something else.

Optimize within each possible observation

Given current evidence $e$, the value of observing $E^{\mathrm{\prime }}$ is

First find the best expected utility of deciding now. Next, for every possible observation, update the probabilities and choose the best action for that observation. Average these optimized utilities using the observation probabilities. Subtract the current MEU. Choosing one action first and then averaging would miss the ability to adapt the action.

Value the forecast and the weather

For the event model, choosing outdoors without a forecast gives MEU 70. Wet forecasts occur with probability 0.31 and lead to indoors, with MEU about 67.74. Dry forecasts occur with probability 0.69 and lead to outdoors, with MEU about 91.30. Carrying exact values gives

Thus $VPI(F)=84-70=14$ utility units. A cost expressed as a utility loss below 14 makes obtaining the forecast worthwhile; at 14 the agent is indifferent. A money price must first be evaluated on the agent's utility scale.

Knowing the weather itself is more useful. Rain leads to indoors with utility 70; no rain leads to outdoors with utility 100. The average is $0.3(70)+0.7(100)=91$, so $VPI(Rain)=91-70=21$.

Why information has nonnegative expected value

The agent can always ignore free information and keep its original action. Optimizing after observing can therefore never reduce expected utility before the observation is known. If the same action is best for every possible result, information has zero value. Information independent of all utility-relevant chance variables, given current evidence, also has zero value in this decision model.

A particular result can still be unwelcome. After a wet forecast, MEU is about 67.7, below the earlier 70. Nonnegativity concerns the average over all results before seeing them.

Combine information without double counting

VPI is generally nonadditive. The forecast alone is worth 14 and the weather alone 21, yet learning both is worth 21 because the forecast adds nothing after weather is known.

After wet, learning weather adds about 9.03; after dry, it adds about 6.09. Before seeing the forecast, the expected extra value is $0.31(9.03)+0.69(6.09)\approx 7$. Hence the joint gain is $14+7=21$, equal to learning weather first and then adding zero. The total is order-independent when all observations precede the action, with each later gain evaluated using the earlier information.

An information-gathering agent may repeatedly choose the observation with the greatest positive VPI minus cost, then act when none remains worthwhile. This myopic strategy evaluates one observation at a time. Two observations can be useful together even when neither alone changes the best action, so greedy selection can miss a valuable pair.