Back to the on-screen lesson ·
The two-circle diagram, the identities it encodes, the bounds it makes obvious, and the one analogy that fails.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to fill in every region of the entropy diagram from any three independent quantities, name each region by the entropy it stands for, prove that mutual information is never negative by recognising it as a relative entropy, bound it above by the smaller of the two entropies, and explain with a three-variable example why conditioning can raise mutual information rather than lower it.
Mutual information as the uncertainty one variable removes about another, the chain rule, and Gibbs' inequality. This lesson assembles them into one picture and reads every identity and bound off it.
An identity here is an exact relation between the entropies of a pair; a bound says how large or small a quantity can be. The conditional mutual information $I(X; Y \mid Z)$ is what $Y$ still says about $X$ once $Z$ is known, and the chain rule for mutual information is $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$.
All the relations between $H(X)$, $H(Y)$, $H(X, Y)$, $H(X \mid Y)$, $H(Y \mid X)$ and $I(X; Y)$ are the arithmetic of two overlapping regions: $I$ is the overlap, the conditional entropies are the crescents, the joint entropy is the union. Hence symmetry $I(X; Y) = I(Y; X)$, the three formulas for $I$, and the bounds $$0 \le I(X; Y) \le \min(H(X), H(Y)),$$ with the upper bound attained when one variable is a function of the other. Conditional mutual information $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)$ and the chain rule $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$ extend the picture to three variables; beware that $I(X; Y \mid Z)$ can be larger or smaller than $I(X; Y)$, so there is no 'conditioning reduces mutual information'. These identities are how you move between whatever quantities a problem gives and whatever it asks.
Another way: picture
The two-circle diagram labelled in full: left crescent $H(X \mid Y)$, overlap $I(X; Y)$, right crescent $H(Y \mid X)$; left circle $H(X)$, right circle $H(Y)$, union $H(X, Y)$. Adding a third circle for $Z$ gives $I(X; Y \mid Z)$ as the part of the overlap outside $Z$.
Another way: steps
Given $H(X) = 4$, $H(Y) = 3$ and $H(X, Y) = 5$ bits, every region follows by addition and subtraction. Start with the overlap, then the crescents, then check that the pieces add up to the union.
| Region | Formula | Value |
|---|---|---|
| overlap $I(X; Y)$ | $H(X) + H(Y) - H(X, Y) = 4 + 3 - 5$ | $2$ |
| left crescent $H(X \mid Y)$ | $H(X) - I = 4 - 2$ | $2$ |
| right crescent $H(Y \mid X)$ | $H(Y) - I = 3 - 2$ | $1$ |
| check: union | $2 + 2 + 1$ | $5 = H(X, Y)$ |
Sanity checks that catch most slips: $I \ge 0$; $I \le \min(H(X), H(Y))$; both crescents $\ge 0$; and $H(X, Y) \ge \max(H(X), H(Y))$. Here $I = 2 \le 3$, and the upper bound $\min(H(X), H(Y))$ would be reached only if $Y$ were a function of $X$, which would empty the right crescent.
Conditional mutual information is mutual information computed inside the world where $Z$ is known: $I(X; Y \mid Z) = H(X \mid Z) - H(X \mid Y, Z)$, an average over $z$ of ordinary mutual informations, so it is nonnegative. The chain rule $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$ says that what the pair $(Y, Z)$ tells you about $X$ is what $Y$ tells you plus what $Z$ adds once $Y$ is known. Unlike entropy, conditioning can go either way for mutual information. The classic example:
| Quantity | $X, Y$ independent fair bits, $Z = X \oplus Y$ | Why |
|---|---|---|
| $I(X; Y)$ | $0$ | independent |
| $I(X; Z)$ | $0$ | $Z$ is a fair bit whatever $X$ is |
| $I(X; Y \mid Z)$ | $1$ | given $Z$, $Y = X \oplus Z$ is determined by $X$ |
| $I(X; Y, Z)$ | $1$ | $= I(X; Z) + I(X; Y \mid Z) = 0 + 1$; the pair $(Y, Z)$ reveals $X$ |
Conditioning on $Z$ raised the mutual information from $0$ to $1$. The opposite happens in a Markov chain $X \to Y \to Z$, where $I(X; Z \mid Y) = 0$ even though $I(X; Z)$ may be large; lesson 6 builds the data processing inequality on exactly that.
Common mistakes
The first error is subtracting the wrong crescent: $H(X) - H(Y \mid X)$ is not a named quantity, while $H(X) - H(X \mid Y)$ is $I$. The second is taking the maximum instead of the minimum for the largest possible $I$; the overlap cannot exceed the smaller circle. The third, and the one that survives longest, is assuming $I(X; Y \mid Z) \le I(X; Y)$ by analogy with conditioning reduces entropy: it fails for $Z = X \oplus Y$, where conditioning creates a dependence out of nothing. The two-circle picture is a genuine aid for two variables and starts to mislead at three, where the 'region' common to all three can be negative.
Given $H(X) = 3$, $H(Y) = 2$, $H(X, Y) = 4$: overlap $I = 3 + 2 - 4 = 1$.
Inclusion-exclusion.
Crescents: $H(X \mid Y) = 3 - 1 = 2$ and $H(Y \mid X) = 2 - 1 = 1$; check $2 + 1 + 1 = 4 = H(X, Y)$.
The three regions add to the union.
$X, Y$ independent fair bits and $Z = X \oplus Y$: $I(X; Y) = 0$.
But given $Z$, $Y = X \oplus Z$ is determined by $X$: $I(X; Y \mid Z) = H(X \mid Z) = 1 > 0$.
No monotonicity for conditional mutual information.
$H(X) = 5$ bits before seeing $Y$, $H(X \mid Y) = 2$ bits after.
$I(X; Y) = 5 - 2 = 3$ bits: observing $Y$ removed three of the five bits.
The left crescent is $2$, the overlap $3$.
So $H(Y) \ge 3$: the right circle must contain the overlap.
The overlap lies inside both circles, so $I \le \min(2, 7) = 2$.
$I = 2$ happens when $H(X \mid Y) = 0$: $X$ is a function of $Y$, for instance the two low bits of a seven-bit $Y$.
Then $H(Y \mid X) = 5$ and $H(X, Y) = 7$: the small circle sits entirely inside the big one.
$I = H(Y) - H(Y \mid X) = 3 - 1 = 2$.
$H(X \mid Y) = H(X) - I = 4 - 2 = 2$.
$H(X) = 6$, $H(Y) = 5$ and $H(X, Y) = 10$ bits. Fill in $I(X; Y)$, $H(X \mid Y)$ and $H(Y \mid X)$.
| Bits | |
|---|---|
| $I(X; Y)$ | |
| $H(X \mid Y)$ | |
| $H(Y \mid X)$ |
Build the proof that $I(X; Y) \ge 0$, with equality exactly when $X$ and $Y$ are independent.
This task has no paper form; do it on a device.
In the two-circle diagram with the left circle $H(X)$ and the right circle $H(Y)$, match each region to the quantity it stands for.
| $I(X; Y)$ | $H(X \mid Y)$ | $H(Y \mid X)$ | $H(X, Y)$ | |
|---|---|---|---|---|
| The overlap of the two circles | ||||
| The left circle outside the right one | ||||
| The right circle outside the left one | ||||
| Everything inside either circle |
$H(X) = 3$ and $H(Y) = 9$ bits. What is the largest value $I(X; Y)$ can take?
Answer:
An engineer must decide whether a proposed sensor is worth fitting. The quantity of interest $X$ has $H(X) = 6$ bits and the sensor's reading $Y$ has $H(Y) = 2$ bits; how the two are related is not yet known. Give the set of values $I(X; Y)$ could take, as an interval in bits.
This task has no paper form; do it on a device.
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Is $I(X; Y \mid Z) \le I(X; Y)$ true for all random variables $X$, $Y$, $Z$?
You can move freely around the entropy diagram and bound mutual information from the marginals alone. Say in your own words why $I(X; Y \mid Z)$ can exceed $I(X; Y)$, and give the example that shows it. Next: what happens to information when data are processed, and the inequality that forbids gaining any.
13. Your turn: $H(X) = 4$, $H(Y \mid X) = 1$, $H(Y) = 3$; find $I(X; Y)$ and $H(X \mid Y)$, step 2