Back to the on-screen lesson · Print

Joint and conditional entropy

Entropy of a pair, the uncertainty that remains after conditioning, and the two extremes of independence and determinism.

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 compute the joint entropy of a pair of random variables and the conditional entropy of one given the other from a joint table, write the joint table of a noisy copy, recognise the two extremes of independence and functional dependence, and say why conditioning reduces entropy on average even though a particular observation can increase it.

2. What you already have

A joint probability table with its marginals and conditionals, the entropy of a single distribution, and the bounds an entropy obeys. This lesson computes the entropy of a pair and of one variable given the other from that same table.

3. Joint, conditional, subadditive

The joint entropy $H(X, Y)$ is the entropy of the pair. The conditional entropy $H(Y \mid X)$ is the average, over $x$, of the entropy of $Y$ given $X = x$. Conditioning reduces entropy names the inequality $H(Y \mid X) \le H(Y)$, and subadditivity names $H(X, Y) \le H(X) + H(Y)$.

4. Joint and conditional entropy

The joint entropy $H(X, Y) = -\sum_{x, y} p(x, y) \log_2 p(x, y)$ is simply the entropy of the pair $(X, Y)$ seen as one random variable. The conditional entropy $H(Y \mid X) = \sum_x p(x) H(Y \mid X = x) = -\sum_{x, y} p(x, y) \log_2 p(y \mid x)$ is the average uncertainty left in $Y$ once $X$ is known. Two extremes anchor the intuition: if $Y$ is a function of $X$ then $H(Y \mid X) = 0$ and $H(X, Y) = H(X)$; if $X$ and $Y$ are independent then $H(Y \mid X) = H(Y)$ and $H(X, Y) = H(X) + H(Y)$. In general conditioning reduces entropy, $H(Y \mid X) \le H(Y)$, proved from Gibbs' inequality, so $H(X, Y) \le H(X) + H(Y)$ (subadditivity) with equality only under independence. Note that a particular value can raise uncertainty, $H(Y \mid X = x) > H(Y)$ is possible, but the average over $x$ never does.

5. Working from a joint table

Everything about a pair of variables sits in the joint table $p(x, y)$, with the marginals $p(x)$ (row sums) and $p(y)$ (column sums) in the margins. Here is a fair bit $X$ copied with a flip probability of $0.1$:

Joint entropy reads the whole table, one term per nonzero cell:

Conditional entropy works row by row. Row $x = 0$, normalised by $p(x) = 0.5$, is the conditional distribution $(0.9, 0.1)$ with entropy $h(0.1) = 0.469$; row $x = 1$ gives the same. Averaging with the weights $p(x)$: $H(Y \mid X) = 0.5 \cdot 0.469 + 0.5 \cdot 0.469 = 0.469$ bits. Check with the chain rule: $H(X) + H(Y \mid X) = 1 + 0.469 = 1.469 = H(X, Y)$. The columns give $H(X \mid Y)$ the same way, and by symmetry of this table it is also $0.469$.

6. The two extremes, and why conditioning reduces entropy

The general inequality $H(Y \mid X) \le H(Y)$ is Gibbs' inequality in disguise: $$H(Y) - H(Y \mid X) = \sum_{x, y} p(x, y) \log_2 \frac{p(y \mid x)}{p(y)} = \sum_{x, y} p(x, y) \log_2 \frac{p(x, y)}{p(x)\, p(y)} = D\big(p(x, y) \,\|\, p(x) p(y)\big) \ge 0,$$ with equality exactly when $p(x, y) = p(x) p(y)$, that is, under independence. Adding $H(X)$ to both sides turns it into subadditivity, $H(X, Y) \le H(X) + H(Y)$. Note what the inequality does not say: conditioning on one particular value $X = x$ can raise the uncertainty about $Y$; only the average over $x$ is guaranteed to go down.

7. Solving the practice problems

1. Independent uniforms on $2^a$ and $2^b$ values: $H(X, Y) = H(X) + H(Y) = a + b$ bits.
2. $Y = X^2$ with $X$ uniform on $2^k$ values: $Y$ is a function of $X$, so $H(X, Y) = H(X) = k$ bits, whatever the function.
3. A fair bit flipped with probability $p$: $H(X, Y) = H(X) + H(Y \mid X) = 1 + h(p)$; take $h(p)$ from the table of lesson 1.
4. What is always true of $H(X, Y)$: $\max(H(X), H(Y)) \le H(X, Y) \le H(X) + H(Y)$. The upper end needs independence, the lower end needs one variable to determine the other.

Common mistakes

• Adding $H(X)$ and $H(Y)$ when the variables are dependent: for $Y = X^2$ that doubles the answer.
• Multiplying entropies. Probabilities multiply under independence; entropies add.
• Forgetting the $1$ bit of $X$ itself in the noisy copy and answering $h(p)$ for $H(X, Y)$.

8. Where this usually goes wrong

The first error is adding $H(X)$ and $H(Y)$ when the variables are dependent; for $Y = X^2$ that doubles the answer, because the pair has no more outcomes than $X$ alone. The second is multiplying entropies: probabilities multiply under independence, entropies add. The third is reading 'conditioning reduces entropy' as a statement about each observation; one value of $X$ can leave $Y$ more uncertain than before, and it is the average over $x$ that never rises. And the two crescents are different quantities: $H(X \mid Y)$ and $H(Y \mid X)$ agree only when $H(X) = H(Y)$.

9. A noisy copy

1. $X$ uniform on $\{0, 1\}$, $Y = X$ with probability $0.9$, flipped otherwise. Given $X = x$, $Y$ is a coin with bias $0.1$: $H(Y \mid X = x) = h(0.1) = 0.469$ for both $x$.

   Row by row.

2. Average over $x$: $H(Y \mid X) = 0.469$ bits; the joint table has cells $0.45, 0.05, 0.05, 0.45$ and $H(X, Y) = 1.469$ bits.

   $H(Y \mid X) < H(Y) = 1$: conditioning reduced entropy.

10. Conditioning on a value can raise uncertainty

1. Let $X \in \{0, 1\}$ with $p(0) = 0.9$; when $X = 0$, $Y = 0$ surely; when $X = 1$, $Y$ is a fair bit. Then $H(Y \mid X = 1) = 1$ while $H(Y) = h(0.05) = 0.286$.

   One value raised the uncertainty.

2. But on average $H(Y \mid X) = 0.9 \cdot 0 + 0.1 \cdot 1 = 0.1 \le 0.286$: the inequality is about the average.

11. Two independent dice with $4$ and $8$ faces

1. $H(X) = \log_2 4 = 2$ and $H(Y) = \log_2 8 = 3$ bits.

2. Independence: $H(Y \mid X) = H(Y) = 3$.

   Knowing the first die says nothing about the second.

3. $H(X, Y) = 2 + 3 = 5$ bits: the pair is uniform on $32$ outcomes, and $\log_2 32 = 5$ agrees.

12. A fair bit through a $0.2$ flip

1. $H(X) = 1$ bit.

2. Given $X$, $Y$ is a coin with bias $0.2$: $H(Y \mid X) = h(0.2) = 0.722$.

3. $H(X, Y) = 1 + 0.722 = 1.722$ bits.

   Directly from the table $(0.4, 0.1, 0.1, 0.4)$: $0.8 \cdot 1.322 + 0.2 \cdot 3.322 = 1.058 + 0.664 = 1.722$.

13. Your turn: $X, Y$ independent fair dice with $8$ faces

1. $H(Y \mid X) = H(Y) = 3$ bits: $X$ says nothing about $Y$.

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

   $H(X, Y) = 3 + 3 = 6$ bits, the uniform on $64$ pairs.

14. Guided practice

Match each situation to the value of the quantity named in it.

15. Guided practice

$X$ is uniform on $4$ values and $Y$ is uniform on $2$ values, independent of $X$. Fill in the four entropies, in bits.

16. Practice

$X$ is a fair bit and $Y$ equals $X$ except that it is flipped with probability $1/2$. Write the joint probability table $p(x, y)$, with $x$ down the rows and $y$ across the columns, both in the order $0, 1$.

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

17. Practice

Select every statement that holds for all random variables $X$ and $Y$.

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

18. Somewhere new

A recommendation service logs one entry per click as a pair (user, item). There are $32$ users and $4$ items, every pair is equally likely, and the user and the item of a click are independent. An analyst is told the item of one entry. How many bits of uncertainty remain about which user clicked?

Answer:

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 $8$ values and $Y = X^2$. What is $H(X, Y)$ in bits?

Answer:

21. What you can do now

You can compute joint and conditional entropies and place a joint distribution between its two extremes. Say in your own words why one particular observation can raise the uncertainty about a variable while observation on average cannot. Next: the chain rule that ties joint and conditional entropy together.

Working for the steps left to you

13. Your turn: $X, Y$ independent fair dice with $8$ faces, step 2