Dependence measured in bits
Two variables can each be uncertain while revealing something about one another. Mutual information quantifies this dependence through a comparison between their joint distribution and the product of their marginals. It is symmetric, unlike the underlying relative entropy, and it is not by itself a measure of causal influence.
Definition 9.2.1
(Mutual information)
Let have finite domains and use logarithms base two. Write for a joint probability and for its marginals. In sums, omit zero-probability terms, equivalently taking . Whenever , both marginals are positive, so the ratio below is defined. The mutual information is
This is the relative entropy in bits.
Definition 9.2.2
(Entropy and conditional entropy)
For finite random variables define
Conditional probabilities are needed only for with positive probability.
Theorem 9.2.3
(Nonnegativity and independence)
For finite random variables , , with equality exactly when for all , that is, when and are independent.
Proof
(Mutual information is a relative entropy)
The sum defining is the relative entropy of the joint distribution with respect to the product distribution on the alphabet of pairs, computed in base two. Both are probability distributions there, and is positive wherever is. The Gibbs inequality of the unit on cross-entropy and relative entropy gives nonnegativity, and equality exactly when . Changing the base of the logarithm only multiplies by the positive constant . The statement uses the full joint distribution, not merely zero correlation.
Proposition 9.2.4
(Mutual information as a reduction of uncertainty)
For finite random variables ,
Proof
(Splitting the logarithm of the ratio)
For write . Weight by and sum. The first part gives . In the second part, summing over gives , so it gives . Exchanging the roles of and gives the other expression.
Thus observing reduces the average uncertainty about by bits. An individual observation can behave differently; the identity averages over outcomes.
Conditional information and the chain rule
Definition 9.2.5
(Conditional mutual information)
For each with , form the conditional joint distribution and its conditional marginals. Define
Every summand is nonnegative. The result is zero exactly when and are independent conditional on each positive-probability value of .
Applying the identity above inside each value of and averaging gives .
Theorem 9.2.6
(Chain rule for mutual information)
For finite random variables ,
No independence assumption is needed.
Proof
(Telescoping conditional entropies)
Applying the unconditional identity to the joint variable gives . Write this as . The first bracket is and the second is : the middle terms cancel. Exchanging the roles of and gives the second expression.
Processing cannot add information about the input
Definition 9.2.7
(Markov chain)
The variables form a Markov chain if and are independent conditional on , that is, , for each with positive probability.
Theorem 9.2.8
(Data-processing inequality)
If is a Markov chain, then . Equality holds exactly when , equivalently when and are conditionally independent given each positive-probability value of .
Proof
(Two orders of the chain rule)
The Markov condition says every conditional relative entropy in is zero, so . The chain rule then gives . Expanding the same quantity in the other order gives . Hence
because a conditional mutual information is nonnegative. The gap is exactly , which gives the equality statement.
Proof X-ray
Where the Markov condition enters
The proof computes one quantity, , in two orders. The order is where the Markov hypothesis is used: it makes the second term zero, so adding to tells us nothing further about . The order needs no hypothesis, and the only fact used there is that a conditional mutual information is an average of relative entropies and hence nonnegative. The inequality is therefore exactly the discarded term . Dropping the Markov condition breaks only the first order, and the counterexample below shows that the conclusion can then fail.
This data-processing inequality concerns a specified joint distribution satisfying that conditional-independence condition. It does not say every function of preserves all information, nor that the arrow notation alone proves a causal relationship.
Counterexample mode
Without the Markov condition, extra variables can add information
Consider the claim that whenever is built from together with other variables. Let be independent fair bits and . Take , and . Then by independence. Given , the bit determines , so the conditional joint distribution puts probability on two cells with uniform marginals, and its relative entropy with respect to the product of marginals is . Hence . Since is a fair bit independent of , the chain rule gives . So carries one full bit about while carries none. The sequence is not a Markov chain: given , the bit determines .
Worked examples
Worked example 9.2.9
(Two noisy stages)
Let be a fair bit. Let be mutually independent, with . Set and , where is addition modulo two. The variables satisfy . Both and are fair, and
where . The effective error arises when exactly one of is one: . The first identity follows from and ; the second follows because is independent of and has Bernoulli parameter , giving . Numerically and bits. The inequality guarantees that the second channel has not increased information about .
Worked example 9.2.10
(A joint table with a zero cell)
Let , , , . The marginals are and . Omitting the zero cell,
As a check, , while , because forces and gives a fair bit. So , in agreement.
Worked example 9.2.11
(A lossy function and a lossless one)
Let be uniform on and , so bits. Put . Given , the variable is uniform on two values, so and . The gap is , as the equality condition predicts. Put instead , a bijective relabeling. Then and , so equality holds. The extreme case of a constant gives .
Common mistakes
Common mistake
(Zero correlation is not independence)
Let be uniform on and . Then and , so the correlation is zero. But is a function of , so and bits. Independence requires the whole joint distribution to factor.
Common mistake
(Mutual information is an average, not a guarantee for each observation)
Let with , let whenever , and let . Then and , so the observation raises the uncertainty about from bits to one bit. Observing (probability ) settles . On average , so bits is positive. The reduction is only an average over outcomes.
Exercises
Quick check
(If is a deterministic copy of a fair bit , find . What happens if is instead an independent fair bit?)
Use .
Solution · Answer
For a copy, , so bit. If is an independent fair bit, the joint distribution equals the product of the marginals, so every ratio in the definition is one and .
Quick check
(In the noisy-stage example, explain why has probability and why the two noises must have the stated independence for that calculation.)
The sum is one exactly when one noise bit is one and the other is zero.
Solution · Answer
exactly when one of the two bits is one and the other is zero. With independence the probability is ; without it the joint probabilities of the two events would not be products. The noise must also be independent of , so that behaves as a channel with error and .
Quick check
(When is a constant, compare with and explain the inequality without assuming and are independent.)
What is for a constant ?
Solution · Answer
A constant gives , so . Mutual information is nonnegative, so whatever the dependence between and . This is the data-processing inequality in a trivial case: is a Markov chain because a constant is independent of everything.