Back to the on-screen lesson · Print

The chain rule for entropy

Why $H(X, Y) = H(X) + H(Y \mid X)$, how it extends to any number of variables, and how it finds whichever entropy is awkward to compute directly.

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.

1. What you will learn

By the end of this lesson you will be able to derive the chain rule $H(X, Y) = H(X) + H(Y \mid X)$ from the product rule for probabilities, rearrange it into each of its forms, extend it to several variables with one conditional term each, use it to find whichever entropy a problem leaves out, including the information a function of a variable forgets, and bracket a joint entropy when only the marginals are known.

2. What you already have

Joint and conditional entropy from a table, and the product rule $p(x, y) = p(x)\,p(y \mid x)$ for probabilities. This lesson takes the logarithm of that product rule and averages it, and the result is the identity you will use more than any other in the course.

3. Chain rule, crescent, residue

The chain rule is $H(X, Y) = H(X) + H(Y \mid X)$, and its extension adds one conditional term per variable. In the two-circle picture each conditional entropy is a crescent, the part of one circle outside the other. The information lost by a function is $H(X \mid f(X)) = H(X) - H(f(X))$, the residue of $X$ that $f$ forgets.

4. The chain rule

The chain rule $$H(X, Y) = H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$$ follows from $p(x, y) = p(x) p(y \mid x)$ by taking logarithms and averaging: describing the pair costs describing $X$, then describing $Y$ knowing $X$. It extends to any number of variables, $H(X_1, \ldots, X_n) = \sum_i H(X_i \mid X_1, \ldots, X_{i-1})$, and it is the workhorse for computing: whenever one term is awkward from the definition, compute the other two and subtract. Combined with conditioning reduces entropy it gives $H(X_1, \ldots, X_n) \le \sum_i H(X_i)$. Two consequences you will use constantly: $H(X \mid Y) = H(X, Y) - H(Y)$, and if $Y = f(X)$ then $H(X \mid f(X)) = H(X) - H(f(X))$, the information lost by applying $f$. The same rule for mutual information, $I(X; Y, Z) = I(X; Y) + I(X; Z \mid Y)$, appears in the next unit.

5. The chain rule as bookkeeping

Six quantities describe a pair of variables, and the diagram keeps them straight: two circles, their union, the two crescents and the overlap. The chain rule is the statement that the union is a circle plus the other crescent.

Any three of the six that are not all on one side of the picture determine the rest. The identities you will use most: $H(X, Y) = H(X) + H(Y \mid X)$, $H(Y \mid X) = H(X, Y) - H(X)$, and $H(X \mid Y) = H(X) - I(X; Y)$ once mutual information appears in lesson 5.

6. Three variables and the general chain

With three variables the rule peels them off one at a time: $$H(X, Y, Z) = H(X) + H(Y \mid X) + H(Z \mid X, Y),$$ and the order is yours to choose, since the joint entropy does not depend on it. Each conditional term is at most the unconditional one, so $H(X_1, \ldots, X_n) \le \sum_i H(X_i)$, with equality exactly when the variables are mutually independent. Here is the bookkeeping for a triple:

7. Solving the practice problems

1. Given $H(X)$ and $H(Y \mid X)$: add, $H(X, Y) = H(X) + H(Y \mid X)$. A conditional entropy given as a fraction like $\tfrac{5}{2}$ is just $2.5$ bits.
2. Given $H(X, Y)$ and $H(X)$: subtract, $H(Y \mid X) = H(X, Y) - H(X)$; the result can never be negative or exceed $H(Y)$.
3. $H(X \mid Y)$ for $Y = X \bmod 2^j$, $X$ uniform on $2^{j + m}$ values: $H(X \mid Y) = H(X) - H(Y) = (j + m) - j = m$ bits, because $H(X, Y) = H(X)$ when $Y$ is a function of $X$.
4. Three variables: $H(X, Y) = H(X) + H(Y \mid X)$, then $H(X, Y, Z) = H(X, Y) + H(Z \mid X, Y)$.

Common mistakes

• Subtracting in the wrong order and getting a negative conditional entropy.
• Using $H(X \mid Y)$ where $H(Y \mid X)$ is wanted: the two crescents differ unless $H(X) = H(Y)$.
• Conditioning on $Z$ alone in the three-variable chain: the last term is $H(Z \mid X, Y)$, given both earlier variables.

8. Where this usually goes wrong

The first error is subtracting in the wrong order and getting a negative conditional entropy; $H(Y \mid X)$ is the joint entropy minus $H(X)$, and it can never be below $0$ or above $H(Y)$. The second is using $H(X \mid Y)$ where $H(Y \mid X)$ is wanted; the two crescents differ unless $H(X) = H(Y)$. The third, in the three-variable chain, is conditioning the last term on $Z$ alone or on one earlier variable; it is $H(Z \mid X, Y)$, given everything before it. And the rule is an identity, not an inequality: it never needs independence, which is only the special case where the conditional term equals the plain one.

9. Proving the chain rule

1. $p(x, y) = p(x) p(y \mid x)$, so $-\log_2 p(x, y) = -\log_2 p(x) - \log_2 p(y \mid x)$.

   Logarithm of a product.

2. Average both sides over $p(x, y)$: the left is $H(X, Y)$, the right is $H(X) + H(Y \mid X)$.

   Expectation is linear.

10. Information lost by a function

1. $X$ uniform on $\{1, \ldots, 16\}$, $Y = X \bmod 4$: $H(X) = 4$, $H(Y) = 2$, and $H(X, Y) = H(X) = 4$ since $Y$ is a function of $X$.

   Three quantities from the setup.

2. $H(X \mid Y) = H(X, Y) - H(Y) = 4 - 2 = 2$ bits: the residue leaves four equally likely candidates.

   Chain rule the other way round.

11. Solving for a conditional entropy

1. $H(X, Y) = 5$ bits and $H(X) = 3$ bits.

2. Chain rule: $5 = 3 + H(Y \mid X)$.

3. $H(Y \mid X) = 2$ bits: after seeing $X$, two bits of $Y$ remain unexplained.

   $H(Y)$ must be at least $2$, so if the problem gave $H(Y) = 1$ the data would be inconsistent.

12. Information lost by $X \bmod 8$ on $\{1, \ldots, 64\}$

1. $H(X) = 6$ bits; $Y = X \bmod 8$ is uniform on $8$ residues, $H(Y) = 3$.

2. $Y$ is a function of $X$, so $H(X, Y) = H(X) = 6$.

3. $H(X \mid Y) = H(X, Y) - H(Y) = 6 - 3 = 3$ bits: given the residue, $8$ values remain equally likely.

13. Your turn: $H(X) = 3$, $H(Y) = 2$, $H(X, Y) = 4$; find $H(Y \mid X)$ and $H(X \mid Y)$

1. $H(Y \mid X) = 4 - 3 = 1$ bit.

2. Your turn: work this step out. Its working is at the end of the packet.

   $H(X \mid Y) = 4 - 2 = 2$ bits; both are below the unconditional entropies, as they must be.

14. Guided practice

Match each entropy to the expression the chain rule gives for it.

15. Guided practice

Build the proof of the chain rule $H(X, Y) = H(X) + H(Y \mid X)$.

This task has no paper form; do it on a device.

16. Practice

$H(X) = 5$, $H(Y \mid X) = 3$ and $H(Y) = 4$ bits. Fill in $H(X, Y)$ and $H(X \mid Y)$.

17. Practice

$H(X) = 2$, $H(Y \mid X) = 1$ and $H(Z \mid X, Y) = 3$ bits. Fill in $H(X, Y)$ and $H(X, Y, Z)$.

H(X, Y) = _p, H(X, Y, Z) = _t

18. Somewhere new

Two sensors on a machine produce readings $X$ and $Y$ with $H(X) = 2$ and $H(Y) = 3$ bits, and nothing is known about how they are related. Give the set of values that $H(X, Y)$, the entropy of one paired reading, can take, as an interval.

This task has no paper form; do it on a device.

19. Lesson test

Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.

20. Test question

$X$ is uniform on $\{1, \ldots, 32\}$ and $Y = X \bmod 2$. What is $H(X \mid Y)$ in bits?

Answer:

21. What you can do now

You can move between joint, marginal and conditional entropies with the chain rule and extend it to any number of variables. Say in your own words what the last term of the three-variable chain rule is conditioned on, and why. This closes the unit on entropy; next comes relative entropy, the distance-like quantity behind Gibbs' inequality.

Working for the steps left to you

13. Your turn: $H(X) = 3$, $H(Y) = 2$, $H(X, Y) = 4$; find $H(Y \mid X)$ and $H(X \mid Y)$, step 2