M3-T3 — Independence and Conditional Independence

Learning objectives

After this lesson, you should be able to:

• State independence and conditional independence, and test them on a probability table.
• Explain why two readings of the same state are dependent, but independent once the state is known.
• Derive the multi-sensor update P(x | z₁, z₂) ∝ P(x) P(z₁ | x) P(z₂ | x), and state the assumption it needs.
• Recognise double counting, and estimate how many independent readings a set of correlated readings is worth.

The intuition

Two events are independent if learning one tells you nothing about the other. Two coin tosses are independent: knowing the first came up heads does not change your belief about the second. The robot's room and its light reading in the last lesson were not: seeing “bright” changed the belief about the room.

The idea that matters for robots is a subtler one. Suppose Rover's two range sensors both look at the same wall, which is either near or far. Each sensor is right 90% of the time. Are their readings independent?

• Not on their own. If the first says “near”, the wall is probably near, so the second probably says “near” too. Knowing one reading raises your expectation of the other.
• Yes, once the wall is known. If you are told that the wall is near, the first reading tells you nothing more about the second: each is just a separate 90% chance of being right. All the dependence between the readings flows through the shared cause.

The second property is called conditional independence given the state, and it is exactly the property a sensor model is supposed to have. The state (the wall) explains everything the readings share, and what is left over in each reading is its own noise.

The difference between the two diagrams is the difference between sound fusion and overconfidence. With two independent readings the evidence really does double: the chance of being wrong drops from 10% to 1.2%. If the second reading is just the first reading again (the same camera frame processed twice, or two filters that were both fed the same lidar scan), nothing new has been learned, but a filter that multiplies the likelihoods anyway reports 1.2% while the truth stays 10%. The robot believes it has twice the evidence it does.

Before multiplying two likelihoods, ask: given the true state, could one of these readings have influenced the other, or did both come from the same raw data? If so, they are not independent evidence.

Definitions

Independence $A \perp B$

Learning $B$ does not change the probability of $A$: $P(A \mid B) = P(A)$.

Conditional independence $A \perp B \mid C$

Once $C$ is known, learning $B$ does not change the probability of $A$: $P(A \mid B, C) = P(A \mid C)$. Two variables can be dependent marginally and independent given $C$, or the reverse.

Common cause

A variable $C$ that influences both $A$ and $B$. It makes them dependent, and conditioning on it removes the dependence.

Markov assumption

The state at the next step depends on the past only through the current state: the future is independent of the past given the present.

Double counting

Using the same piece of evidence more than once in an update.

Derivation: when readings multiply, and when they do not

Three equivalent statements of independence

1. $$P(A \mid B) = P(A)$$

   The definition: learning $B$ leaves the probability of $A$ unchanged.

2. $$\dfrac{P(A, B)}{P(B)} = P(A) \;\;\Longleftrightarrow\;\; P(A, B) = P(A)\,P(B)$$

   Substitute the definition of conditional probability and multiply by $P(B)$. The joint table factorizes into its margins.

3. $$P(B \mid A) = \dfrac{P(A, B)}{P(A)} = P(B)$$

   The relation is symmetric: if $B$ says nothing about $A$, then $A$ says nothing about $B$.

Why the multi-reading update multiplies likelihoods

1. $$P(x \mid z_1, z_2) \;\propto\; P(z_1, z_2 \mid x)\, P(x)$$

   Bayes’ rule with the pair of readings as the data. The evidence term is the same for every $x$ and is dropped until normalization.

2. $$P(z_1, z_2 \mid x) = P(z_1 \mid x)\, P(z_2 \mid z_1, x)$$

   The chain rule on the readings, for a fixed $x$.

3. $$P(z_2 \mid z_1, x) = P(z_2 \mid x)$$

   The assumption. Given the state, the first reading tells nothing about the second: conditional independence.

4. $$P(x \mid z_1, z_2) \;\propto\; P(x)\, P(z_1 \mid x)\, P(z_2 \mid x)$$

   Substitute. The result equals applying Bayes’ rule twice, once per reading, with each posterior serving as the prior for the next (the subject of the next lesson).

Dependent on their own, independent given the cause

Let the wall be near or far with probability ½ each, and let each reading be correct with probability $a = 0.9$ given the wall, independently of the other.

1. $$P(z_1 = \text{near}) = \tfrac12\, a + \tfrac12\,(1-a) = \tfrac12 = P(z_2 = \text{near})$$

   Total probability over the wall. Each reading alone is a fair coin.

2. $$P(z_1 = \text{near},\, z_2 = \text{near}) = \tfrac12\, a^2 + \tfrac12\,(1-a)^2 = 0.405 + 0.005 = 0.41$$

   Total probability again, using the conditional independence to multiply inside each term.

3. $$0.41 \;\ne\; P(z_1 = \text{near})\,P(z_2 = \text{near}) = 0.25$$

   The readings are not independent: seeing one “near” raises the chance of the other from 0.5 to 0.82. They share a cause.

4. $$P(z_1 = \text{near},\, z_2 = \text{near} \mid x = \text{near}) = a^2 = 0.81 = a \cdot a$$

   Given the wall, they do factorize: conditionally independent.

What a copied reading does

If the second reading is a copy of the first, then $P(z_2 = z_1 \mid z_1, x) = 1$, not $P(z_2 \mid x)$. The correct update multiplies the posterior by 1 (nothing changes), while the naive product multiplies it by $P(z_2 \mid x)$ a second time. The posterior odds are then wrong by the likelihood ratio, here $0.9/0.1 = 9$.

The product of likelihoods rests on conditional independence given the state. When two readings share anything besides the state (the same raw data, the same correlated error, the same filter output), the product double counts it.

A worked example

A wall is near or far with equal prior probability. Each of two readings says the right thing with probability 0.9. Numbers below are checked by the program.

1. One reading. A single “near” gives $P(\text{near} \mid z_1) = 0.9$ (Bayes with equal priors). The chance that the robot is wrong is 10%.
2. Marginal dependence. $P(z_1 = z_2 = \text{near}) = 0.41$, while the product of the marginals is 0.25. The readings are dependent.
3. Given the wall, they are independent. $P(\text{both near} \mid \text{near}) = 0.81 = 0.9 \times 0.9$.
4. Two independent “near” readings. Multiply: $0.5 \times 0.81 / (0.5 \times 0.81 + 0.5 \times 0.01) = 0.9878$. The chance of being wrong falls to 1.2%.
5. Simulation. Over 50 000 simulated walls with two independent readings, the wall is near in 0.9878 of the cases in which both said “near”: the formula is right.
6. A copy, counted twice. Now the second reading is only a copy of the first. The naive product still claims 0.9878, but in the simulation the wall is near in only 0.8983 of the cases where both said “near”: the true figure is 0.90, the same as for one reading. The robot believes it is wrong 1.2% of the time and is wrong 10% of the time.
7. Partly correlated readings. If five consecutive frames have a correlation $\rho$ between their errors, they are worth $n_{\text{eff}} = n/(1 + (n-1)\rho)$ independent frames (proved in module 4). With $\rho = 0.5$ that is 1.67 frames, with $\rho = 0.8$ only 1.19.

from robotprob import Rng, posterior_binary

a = 0.9                              # each reading says the right thing with probability 0.9, given the wall
p_both_near = 0.5 * a * a + 0.5 * (1 - a) * (1 - a)
print('P(z1 = near)              =', 0.5 * a + 0.5 * (1 - a))
print('P(z1 = near, z2 = near)   =', round(p_both_near, 4), ' product of marginals =', 0.5 * 0.5)
print('given near: P(both near)  =', round(a * a, 4), ' = 0.9 * 0.9')
print('posterior, one reading    =', round(posterior_binary(0.5, a, 1 - a), 4))
print('posterior, two independent=', round(posterior_binary(0.5, a * a, (1 - a) ** 2), 4))

rng = Rng(21)                        # simulate the wall and the readings
indep = [0, 0]                       # [cases where both said near, of which the wall was near]
copy = [0, 0]
for _ in range(50000):
    near = rng.bernoulli(0.5)
    r1 = near if rng.bernoulli(a) else not near
    r2 = near if rng.bernoulli(a) else not near          # an independent second reading
    if r1 and r2:
        indep[0] += 1
        indep[1] += 1 if near else 0
    if r1:                                               # the copy says exactly what r1 said
        copy[0] += 1
        copy[1] += 1 if near else 0
print('independent readings: truth is near in', round(indep[1] / indep[0], 4), 'of the cases where both said near')
print('a copied reading:     truth is near in', round(copy[1] / copy[0], 4), 'of the cases where both said near')
print('naive product for the copy claims', round(posterior_binary(0.5, a * a, (1 - a) ** 2), 4))
for rho in (0.0, 0.5, 0.8, 1.0):
    print('5 frames, correlation', rho, ': equivalent independent frames =', round(5 / (1 + 4 * rho), 2))

P(z1 = near)              = 0.5
P(z1 = near, z2 = near)   = 0.41  product of marginals = 0.25
given near: P(both near)  = 0.81  = 0.9 * 0.9
posterior, one reading    = 0.9
posterior, two independent= 0.9878
independent readings: truth is near in 0.9878 of the cases where both said near
a copied reading:     truth is near in 0.8983 of the cases where both said near
naive product for the copy claims 0.9878
5 frames, correlation 0.0 : equivalent independent frames = 5.0
5 frames, correlation 0.5 : equivalent independent frames = 1.67
5 frames, correlation 0.8 : equivalent independent frames = 1.19
5 frames, correlation 1.0 : equivalent independent frames = 1.0

In robotics

Several sensors, one state

A robot with wheel odometry, an IMU and a lidar fuses them by multiplying their likelihoods (or, for Gaussians, by the Kalman update). That is legitimate only if the sensors' errors are independent given the state. They often are not: the IMU and the wheel encoders both react to a bump, a lidar and a camera mounted on the same vibrating mast share vibration noise, and two position estimates that were each built from the same GPS are not independent at all. UAV estimators therefore monitor their innovations for exactly this sign of trouble (Normalized Estimation Error Squared).

Loops that feed an estimate back to itself

A classic double-counting bug: filter A estimates the pose from odometry and lidar; filter B takes A's pose as a measurement and adds a camera; A then takes B's output as an input. The lidar information circulates in the loop and is counted again at every pass, and the covariance shrinks without any new data. Federated and decentralized fusion schemes exist for the purpose of avoiding it. The rule of thumb: each piece of raw data may enter the estimate exactly once.

Consecutive frames are not independent frames

Successive camera frames or lidar scans share their lighting, glare, occluders and calibration error. Counting a 30 Hz stream as 30 independent looks per second overstates the evidence, often by an order of magnitude. Detection voting (M2-T1: Discrete Random Variables and Probability Mass Functions), the log-odds update of an occupancy grid (M10-T1: Occupancy Grids and the Binary Bayes Filter) and the averaging of readings all rely on independence, and all are used with a safety margin or with measurements thinned out in time.

The Markov assumption and the state

A localizer that tracks only position cannot be Markov if the robot's velocity matters: the next position depends on the past (how fast it was going), not only on the current position. The cure is to put the missing quantity in the state. A great deal of filter design is deciding what the state must contain so that the assumption holds (M5-T1: State, Controls, Measurements and the Markov Assumption).

Occupancy grids assume independent cells

An occupancy grid map estimates each cell separately and multiplies the cells' probabilities as if they were independent, although a wall makes neighbouring cells strongly dependent. It is a deliberate approximation that makes mapping tractable, and its consequences are discussed in Occupancy Grid Mapping and M10-T1: Occupancy Grids and the Binary Bayes Filter.

Common misconceptions

Key takeaways

1. Independence means P(A, B) = P(A) P(B): learning one says nothing about the other. Conditional independence given C means the same once C is known.
2. Two readings of one state are dependent on their own and conditionally independent given the state. A good sensor model leaves the shared part to the state and keeps only private noise.
3. Under conditional independence, evidence multiplies: P(x | z₁, …, zₙ) ∝ P(x) Π P(zᵢ | x). Normalize at the end.
4. Double counting, using the same evidence twice (a copy, a feedback loop, correlated frames), makes a filter overconfident: it claims a 1.2% error rate and delivers 10%.
5. Correlated readings are worth n / (1 + (n − 1)ρ) independent ones. Space measurements out, model the correlation, or inflate the noise.

References and further reading

Each source is marked free or paid. Free to read does not mean free to reuse: the course resources page lists every source with its licence.

• J. Tsitsiklis and P. Jaillet, MIT RES.6-012 Introduction to Probability , lecture 3 (independence). Free videos and notes, licence CC BY-NC-SA 4.0.
• J. Blitzstein and J. Hwang, Introduction to Probability, 2nd edition, CRC Press, 2019 , chapter 2 (independence and conditional independence). Free to read online; the book is copyrighted.
• S. Thrun, W. Burgard and D. Fox, Probabilistic Robotics, MIT Press, 2005, section 2.4.4 (the Markov assumption and the assumptions of the Bayes filter). Paid book.
• C. Piech, Probability for Computer Scientists (Stanford CS109 course reader) , part 1 (independence) and part 4 (naive Bayes). Free to read online.

Knowledge check

Three questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

With conditional independence in hand, the update with several readings is just repeated multiplication. The next lesson turns that into a recursive procedure: update after every reading, and let each posterior be the next prior.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T2: Bayes' Rule: Prior, Likelihood and Posterior

  Derive Bayes' rule, name its four parts, and compute a posterior for a detector with false positives and missed detections.

Other courses on this site treat neighbouring topics from their own angle:

• SLAM M2-T5: Bayesian Estimation
• UAV M3-T3: Bayesian estimation
• Physical AI: Belief under uncertainty