Joint and conditional entropy, the chain rule

Before this lesson: lesson 01 (surprisal, entropy, $0 \le H \le \log K$, the lemma $\ln t \le t - 1$); joint, marginal and conditional distributions and independence (Probability 04). Time: about 55 minutes, plus the notebook.

---

Why this matters #

An autoregressive model, such as a large language model, writes the probability of a sequence as a product of next-token probabilities: $p(x_1, \dots, x_T) = \prod_t p(x_t \mid x_{<t})$. Its loss adds one conditional surprisal per token. The chain rule of this lesson is the same statement for entropies. The conditional entropy $H(Y \mid X)$ is the noise that no model can remove: the expected log-loss of any classifier that predicts $Y$ from $X$ is at least $H(Y \mid X)$ (lesson 04). Decision trees choose splits by the drop $H(Y) - H(Y \mid \text{split})$, and active learning and Bayesian experimental design choose measurements by the expected drop in entropy. That drop is the mutual information, previewed at the end of section 3 and treated in lesson 07.

1. Predict first #

2. The picture #

A pair is one random variable #

The pair $(X, Y)$ is itself a random variable. Its values are pairs $(x, y)$, and its entropy is the joint entropy $H(X, Y)$. Take $X$ a fair coin.

• Independent coins. If $Y$ is a second fair coin, independent of $X$, the four pairs $(\text{H}, \text{H}), (\text{H}, \text{T}), (\text{T}, \text{H}), (\text{T}, \text{T})$ are equally likely. So $H(X, Y) = \log_2 4 = 2$ bits.
• A copy. If $Y = X$, only $(\text{H}, \text{H})$ and $(\text{T}, \text{T})$ can happen, each with probability $\frac12$. So $H(X, Y) = 1$ bit.

Dependence lowers the joint entropy: once you know $X$, a copy $Y$ adds no new uncertainty.

The question game for a pair #

To find the pair, first find $x$. This takes $H(X)$ questions on average. Then find $y$ while knowing $x$. This takes the entropy of $Y$ given this $x$, which we write $H(Y \mid X = x)$. On average over $x$, it takes $H(Y \mid X)$ questions. In total:

This is the chain rule. Independent coins: $2 = 1 + 1$. A copy: $1 = 1 + 0$, because $x$ tells you $y$.

Interactive figure: loading…

Rows of the joint table #

Write the joint distribution as a table: one row for each value $x$, one column for each value $y$. The sky and rain example (all numbers are probabilities):

$p(x, y)$	dry	drizzle	rain	$p(x)$
clear	$1/2$	$0$	$0$	$1/2$
cloudy	$1/8$	$1/8$	$1/4$	$1/2$
$p(y)$	$5/8$	$1/8$	$1/4$	$1$

Follow four steps.

1. Row sums give the marginal $p(x)$. Column sums give the marginal $p(y)$.
2. Divide each row by its sum $p(x)$. This gives the conditional distribution $p(y \mid x)$: the distribution of the rain when you know the sky. Clear: $(1, 0, 0)$. Cloudy: $(\frac14, \frac14, \frac12)$.
3. Take the entropy of each row. $H(Y \mid X = \text{clear}) = 0$ bits and $H(Y \mid X = \text{cloudy}) = 1.5$ bits.
4. Average the row entropies, with the weights $p(x)$. This is the conditional entropy: $H(Y \mid X) = \frac12 \cdot 0 + \frac12 \cdot 1.5 = 0.75$ bits.

Compare with $H(Y) = 1.299$ bits, the entropy of the bottom row. The cloudy row has more entropy than $H(Y)$, but the average $0.75$ is less.

Interactive figure: loading…

Why the average cannot exceed $H(Y)$. The bottom row is a mixture of the rows: $p(y) = \sum_x p(x)\, p(y \mid x)$. Mixing distributions blurs them, and a blurred distribution is harder to guess than its parts on average. Section 3 proves this.

3. Definitions and main results #

$X$ takes values in a finite set $\mathcal{X}$, and $Y$ in a finite set $\mathcal{Y}$. The joint distribution is $p(x, y) = P(X = x, Y = y)$. The marginals are $p(x) = \sum_y p(x, y)$ and $p(y) = \sum_x p(x, y)$. For $p(x) > 0$, the conditional distribution is $p(y \mid x) = p(x, y) / p(x)$. As in lesson 01, $\log$ is the natural log unless a base is written, and $0 \log 0 = 0$.

Definitions #

• Joint entropy:

It is the entropy of the pair seen as one variable with $|\mathcal{X}| \cdot |\mathcal{Y}|$ values.

• Entropy of $Y$ given one value $X = x$ (for $p(x) > 0$): the entropy of row $x$,

• Conditional entropy: the average of the row entropies, weighted by $p(x)$,

The two sums are equal because $p(x)\, p(y \mid x) = p(x, y)$. Rows with $p(x) = 0$ have weight 0 and are left out.

Three facts follow directly.

• $H(Y \mid X)$ is one number, not a function of $x$. It averages over $x$.
• $H(Y \mid X) \ge 0$, because every row entropy is $\ge 0$.
• $H(Y \mid X) = 0$ if and only if every row with $p(x) > 0$ is one-hot, that is, $Y = g(X)$ for some function $g$: knowing $X$ removes all uncertainty about $Y$.

The chain rule #

Theorem 1 (chain rule).

Proof.

1. Take a pair $(x, y)$ with $p(x, y) > 0$. Then $p(x) \ge p(x, y) > 0$, and the product rule gives $p(x, y) = p(x)\, p(y \mid x)$.
2. Take $-\log$ of both sides. The log of a product is a sum: $-\log p(x, y) = -\log p(x) - \log p(y \mid x)$. In words: the surprisal of the pair is the surprisal of $x$ plus the surprisal of $y$ given $x$.
3. Take the expectation over $(X, Y) \sim p$. Pairs with $p(x, y) = 0$ have weight 0. The left side becomes $H(X, Y)$, and the last term becomes $H(Y \mid X)$.
4. The middle term depends only on $x$. Sum over $y$ first: $\sum_{x, y} p(x, y) (-\log p(x)) = -\sum_x \big(\sum_y p(x, y)\big) \log p(x) = -\sum_x p(x) \log p(x) = H(X)$.
5. Exchange the roles of $X$ and $Y$ for the second form. $\blacksquare$

Conditional entropy is not symmetric. Subtract the two forms of the chain rule: $H(Y \mid X) - H(X \mid Y) = H(Y) - H(X)$. So $H(Y \mid X) \ne H(X \mid Y)$ whenever $H(X) \ne H(Y)$.

Theorem 2 (chain rule for $n$ variables).

where the term for $i = 1$ is $H(X_1)$, and $H(X_i \mid X_1, \dots, X_{i-1})$ conditions on the vector $(X_1, \dots, X_{i-1})$ seen as one variable.

Proof.

1. Apply the product rule $n - 1$ times. Wherever the left side is positive, $p(x_1, \dots, x_n) = p(x_1)\, p(x_2 \mid x_1) \cdots p(x_n \mid x_1, \dots, x_{n-1})$.
2. Take $-\log$: the surprisal of the sequence is the sum of $n$ conditional surprisals $-\log p(x_i \mid x_1, \dots, x_{i-1})$.
3. Take expectations. By linearity, term $i$ becomes $H(X_i \mid X_1, \dots, X_{i-1})$. $\blacksquare$

Every order of the variables gives the same total, but the single terms change. An autoregressive model uses the order of the text; the total is the same for any order.

Conditioning reduces entropy, on average #

Theorem 3. $H(Y \mid X) \le H(Y)$, with equality if and only if $X$ and $Y$ are independent.

Proof. We use the lemma of lesson 01: $\ln t \le t - 1$ for $t > 0$, with equality only at $t = 1$. Work in nats and let $S = \{(x, y) : p(x, y) > 0\}$.

1. For $(x, y) \in S$, both $p(x) > 0$ and $p(y) > 0$. Write both entropies as sums over $S$: $H(Y) = -\sum_{S} p(x, y) \ln p(y)$ (sum over $x$ first) and $H(Y \mid X) = -\sum_S p(x, y) \ln p(y \mid x)$.
2. Subtract, and use $p(y \mid x) = p(x, y) / p(x)$:

3. Apply the lemma with $t = \frac{p(x) p(y)}{p(x, y)}$ to every term:

because the products $p(x) p(y)$ over all pairs sum to 1, so over $S$ they sum to at most 1.

4. Equality. Step 3 is tight only if $p(x) p(y) = p(x, y)$ on $S$, and $p(x) p(y) = 0$ outside $S$ (where $p(x, y) = 0$). Together: $p(x, y) = p(x)\, p(y)$ for all pairs, which is independence. Conversely, independence gives $p(y \mid x) = p(y)$, and the two entropies are equal. $\blacksquare$

The quantity $\sum p(x, y) \log \frac{p(x, y)}{p(x) p(y)} = H(Y) - H(Y \mid X)$ appears again: it is the KL divergence between the joint distribution and the product of the marginals (lesson 03), and it is the mutual information $I(X;Y)$ (lesson 07).

Only on average. Theorem 3 bounds the weighted average of the row entropies. One row can have more entropy than the marginal. In the weather table, $H(Y \mid X = \text{cloudy}) = 1.5$ bits $> H(Y) = 1.299$ bits: a cloudy sky makes the rain less predictable than it was before you looked. The certain row "clear $\Rightarrow$ dry" pulls the average down to $0.75$ bits. MacKay puts it this way: data do not increase uncertainty, on average.

The mixture view and the concavity of entropy

The proof above shows a more general fact. For distributions $p_1, \dots, p_m$ on the same set and weights $\lambda_k \ge 0$ with $\sum_k \lambda_k = 1$, entropy is concave: $H\big(\sum_k \lambda_k p_k\big) \ge \sum_k \lambda_k H(p_k)$. Take $p_k$ = row $k$ of the table and $\lambda_k = p(x_k)$: the mixture is $p(y)$, and the inequality is $H(Y) \ge H(Y \mid X)$. Lesson 03 proves concavity with Jensen's inequality for the concave function $-t \log t$. The law of total variance has the same shape: $\mathbb{E}[\operatorname{Var}(Y \mid X)] \le \operatorname{Var}(Y)$, while one $\operatorname{Var}(Y \mid X = x)$ can be larger than $\operatorname{Var}(Y)$.

Consequences #

• Bounds on the joint entropy. $\max(H(X), H(Y)) \le H(X, Y) \le H(X) + H(Y)$.
  • Left: the chain rule and $H(Y \mid X) \ge 0$. $H(X, Y) = H(X)$ exactly when $Y$ is a function of $X$.
  • Right (subadditivity): the chain rule and Theorem 3. Equality exactly when $X$ and $Y$ are independent.
  • For $n$ variables, Theorem 2 and $H(X_i \mid X_1, \dots, X_{i-1}) \le H(X_i)$ give $H(X_1, \dots, X_n) \le \sum_i H(X_i)$.
• A function cannot add entropy. For any function $g$, write the chain rule in both orders for the pair $(X, g(X))$: $H(X) + H(g(X) \mid X) = H(g(X)) + H(X \mid g(X))$. Since $H(g(X) \mid X) = 0$, we get $H(g(X)) = H(X) - H(X \mid g(X)) \le H(X)$, with equality exactly when $g$ is one-to-one on the values that $X$ takes. Merging categories or binning data can only lower the entropy.

The two-bar diagram and a preview of mutual information #

The chain rule in both orders gives $H(X) + H(Y \mid X) = H(Y) + H(X \mid Y)$. Rearranged:

This number is the mutual information: the uncertainty about $Y$ that learning $X$ removes, on average, and the same amount the other way around. By Theorem 3 it is $\ge 0$, and it is 0 exactly for independent variables. The joint entropy splits into three pieces (MacKay, Figure 8.1):

Interactive figure: loading…

Lesson 07 studies $I(X;Y)$ in full.

Three variables: the Venn picture fails

For two variables the bar picture is exact. With three variables it is tempting to draw three overlapping circles, but the centre region, $I(X;Y) - I(X;Y \mid Z)$, can be negative. Example (MacKay, exercise 8.8): $X$ and $Y$ are independent fair bits and $Z = X \oplus Y$ (XOR). Then $I(X;Y) = 0$, but given $Z$, knowing $X$ tells you $Y$ exactly: $I(X;Y \mid Z) = 1$ bit. The centre would have area $0 - 1 = -1$ bit. Use the chain rule, not the picture, for three or more variables.

Continuous variables, briefly

For densities, $h(X, Y) = \mathbb{E}[-\log p(X, Y)]$ and $h(Y \mid X) = \mathbb{E}[-\log p(Y \mid X)]$ are differential entropies (lesson 06). The chain rule (same proof) and $h(Y \mid X) \le h(Y)$ (same proof, with integrals) still hold. Everything that used $H \ge 0$ fails: $h(Y \mid X)$ can be negative, and $h(X, Y)$ can be smaller than $h(X)$. Example: $(X, Y)$ standard bivariate Gaussian with correlation $\rho$. For every $x$, $Y \mid X = x \sim \mathcal{N}(\rho x, 1 - \rho^2)$, so $h(Y \mid X) = \frac12 \ln\big(2\pi e (1 - \rho^2)\big)$ nats. For $\rho = 0.99$ this is $-0.540$ nats, so $h(X, Y) = h(X) + h(Y \mid X) < h(X)$.

Answers to section 1. (1) (a) $2$ bits; (b) $1$ bit. (2) Yes for one value: in the weather table, $H(Y \mid X = \text{cloudy}) = 1.5$ bits $> H(Y) = 1.299$ bits. No on average: $H(Y \mid X) \le H(Y)$ (Theorem 3). (3) No to both: $H(X) \le H(X, Y) \le H(X) + H(Y)$.

4. Worked example #

Take the sky and rain table of section 2. All values are in bits.

1. Joint entropy. The nonzero entries $\frac12, \frac18, \frac18, \frac14$ have surprisals 1, 3, 3, 2 bits. $H(X, Y) = \frac12 \cdot 1 + \frac18 \cdot 3 + \frac18 \cdot 3 + \frac14 \cdot 2 = 0.5 + 0.375 + 0.375 + 0.5 = 1.75$ bits.
2. Marginal entropies. $p(x) = (\frac12, \frac12)$, so $H(X) = 1$ bit. $p(y) = (\frac58, \frac18, \frac14)$, so $H(Y) = \frac58 \log_2 \frac85 + \frac18 \cdot 3 + \frac14 \cdot 2 = 0.424 + 0.375 + 0.5 = 1.299$ bits.
3. Rows. Clear: $p(y \mid \text{clear}) = (1, 0, 0)$, so $H(Y \mid X = \text{clear}) = 0$. Cloudy: $p(y \mid \text{cloudy}) = (\frac14, \frac14, \frac12)$, so $H(Y \mid X = \text{cloudy}) = \frac14 \cdot 2 + \frac14 \cdot 2 + \frac12 \cdot 1 = 1.5$ bits.
4. Conditional entropy. $H(Y \mid X) = \frac12 \cdot 0 + \frac12 \cdot 1.5 = 0.75$ bits. Check with the chain rule: $H(X) + H(Y \mid X) = 1 + 0.75 = 1.75 = H(X, Y)$. ✓
5. Columns. Divide each column by its sum $p(y)$. Dry: $p(x \mid \text{dry}) = (\frac{1/2}{5/8}, \frac{1/8}{5/8}) = (\frac45, \frac15)$, so $H(X \mid Y = \text{dry}) = H_b(0.2) = 0.722$ bits. Drizzle and rain both mean "cloudy" for sure: entropy 0. So $H(X \mid Y) = \frac58 \cdot 0.722 + \frac18 \cdot 0 + \frac14 \cdot 0 = 0.451$ bits. Chain rule: $H(Y) + H(X \mid Y) = 1.299 + 0.451 = 1.75$. ✓
6. One value against the average. $H(Y \mid X = \text{cloudy}) = 1.5 > H(Y) = 1.299$, but $H(Y \mid X) = 0.75 < 1.299$.
7. Not symmetric. $H(Y \mid X) = 0.75 \ne H(X \mid Y) = 0.451$. The difference is $0.299 = H(Y) - H(X)$. ✓
8. What $X$ tells about $Y$. $H(Y) - H(Y \mid X) = 1.299 - 0.75 = 0.549$ and $H(X) - H(X \mid Y) = 1 - 0.451 = 0.549$. ✓ This is $I(X;Y)$. A decision tree that predicts the rain and splits on the sky has an information gain of $0.549$ bits.

In nats, multiply by $\ln 2 = 0.693$: $H(X, Y) = 1.213$ nats and $H(Y \mid X) = 0.520$ nats.

5. In code #

NumPy and SciPy check the worked example; scikit-learn gives a second route through the mutual information. scipy.stats.entropy normalizes its input, so a row of the table gives $H(Y \mid X = x)$ directly.

import numpy as np
from scipy.stats import entropy
from sklearn.metrics import mutual_info_score

# rows x = (clear, cloudy), columns y = (dry, drizzle, rain)
pxy = np.array([[1/2, 0,   0  ],
                [1/8, 1/8, 1/4]])
px, py = pxy.sum(axis=1), pxy.sum(axis=0)
H_XY = entropy(pxy.ravel(), base=2)          # the pair as one variable with 6 values
H_X, H_Y = entropy(px, base=2), entropy(py, base=2)
print(H_XY, H_X, round(H_Y, 4))              # 1.75 1.0 1.2988

# H(Y|X): average of the row entropies, weighted by p(x)
row_H = np.array([entropy(r, base=2) for r in pxy])   # scipy normalizes each row
H_YgX = np.sum(px * row_H)
print(row_H, H_YgX, H_XY - H_X)              # [0.  1.5] 0.75 0.75

# H(X|Y): the same with columns
col_H = np.array([entropy(c, base=2) for c in pxy.T])
print(col_H.round(4), round(np.sum(py * col_H), 4), round(H_XY - H_Y, 4))
# [0.7219 0.     0.    ] 0.4512 0.4512

# I(X;Y) = H(Y) - H(Y|X); sklearn computes it in nats from counts
I_bits = mutual_info_score(None, None, contingency=8 * pxy) / np.log(2)
print(round(H_Y - H_YgX, 4), round(I_bits, 4))   # 0.5488 0.5488

# random 2 x 3 tables: one row can be above H(Y), the average never is
rng = np.random.default_rng(0)
row_above = avg_above = 0
for _ in range(10_000):
    t = rng.dirichlet(np.ones(6)).reshape(2, 3)
    HY = entropy(t.sum(axis=0))
    row_above += max(entropy(r) for r in t) > HY
    avg_above += np.sum(t.sum(axis=1) * [entropy(r) for r in t]) > HY + 1e-12
print(row_above / 10_000, avg_above)         # 0.5062 0

In about half of the random $2 \times 3$ tables, one row has more entropy than the marginal; the average never does. When you write the row normalization yourself, skip rows with $p(x) = 0$ instead of computing $0/0$.

6. Where it shows up #

• Autoregressive models. A language model writes $\log p(x_1, \dots, x_T) = \sum_t \log p(x_t \mid x_{<t})$: Theorem 2 for single outcomes. In expectation, the entropy of a sequence is the sum of the per-token conditional entropies $H(X_t \mid X_{<t})$. The training loss is the average conditional surprisal per token, and its exponential (in nats) is the perplexity (the LLMs track, in preparation). Probabilistic weather emulators that roll out one time step at a time use the same factorization over time.
• The lowest possible loss of a classifier. For any model $q(y \mid x)$, $\mathbb{E}[-\log q(Y \mid X)] \ge H(Y \mid X)$, with equality only for $q(y \mid x) = p(y \mid x)$ (lesson 04). The floor is the label noise that remains given the input (aleatoric uncertainty). It is not 0, and it is not $H(Y)$.
• Decision trees. The information gain of a split $S$ is $H(Y) - H(Y \mid S)$, where $H(Y \mid S)$ is the entropy of the labels in each child, weighted by the fraction of samples in the child. Theorem 3 says it is never negative (the decision-tree lesson of the ML fundamentals track, in preparation).
• Experimental design and active learning. For a parameter $\theta$ and a measurement $Y$, the expected entropy after the measurement is $H(\theta \mid Y) \le H(\theta)$. One measurement can increase the uncertainty about $\theta$; on average it cannot. The expected drop $H(\theta) - H(\theta \mid Y) = I(\theta; Y)$ is the expected information gain, used by BALD in active learning and by Bayesian design of experiments and sensor networks.
• ML for science. A model that predicts an observed quantity $Y$ (for example, the strength of ground shaking) from inputs $X$ (magnitude, distance, site) has an irreducible spread: its conditional entropy $H(Y \mid X)$. Adding inputs cannot raise it, $H(Y \mid X, Z) \le H(Y \mid X)$ (check yourself 5). A good generative model of $Y$ given $X$ should reproduce this spread, not collapse to one value.

7. Common mistakes #

• Reading Theorem 3 for each value. $H(Y \mid X = x) > H(Y)$ is possible. Only the average $H(Y \mid X)$ is bounded by $H(Y)$.
• Equal weights for the rows. $H(Y \mid X)$ weights row $x$ by $p(x)$, not by $1/|\mathcal{X}|$.
• Dividing by the wrong marginal. $-\sum p(x, y) \log \frac{p(x, y)}{p(x)}$ is $H(Y \mid X)$: divide by the marginal of the variable you condition on. Dividing by $p(y)$ gives $H(X \mid Y)$.
• Assuming symmetry. $H(Y \mid X) \ne H(X \mid Y)$ in general; they differ by $H(Y) - H(X)$.
• Mixing up the two extremes. $H(Y \mid X) = 0$ means $Y$ is a function of $X$; $H(Y \mid X) = H(Y)$ means independence.
• Trusting the Venn diagram for three variables. The centre region can be negative (XOR example).

8. Check yourself #

1. $X$ is a fair bit. Give $H(X, Y)$ and $H(Y \mid X)$ in bits when (a) $Y = X$, and (b) $Y$ is an independent fair bit.
   Answer

   (a) $H(X, Y) = 1$ and $H(Y \mid X) = 0$. (b) $H(X, Y) = 2$ and $H(Y \mid X) = 1 = H(Y)$.
2. $D$ is a fair die and $X$ is its parity (even or odd). Give $H(D)$, $H(X)$, $H(X \mid D)$, $H(D \mid X)$ and $H(D, X)$ in bits.
   Answer

   $H(D) = \log_2 6 = 2.585$; $H(X) = 1$; $H(X \mid D) = 0$ ($X$ is a function of $D$); $H(D \mid X) = \log_2 3 = 1.585$ (three equally likely faces remain); $H(D, X) = H(D) + 0 = H(X) + H(D \mid X) = 1 + 1.585 = 2.585$.
3. In the weather table, is there a value $y$ with $H(X \mid Y = y) > H(X)$?
   Answer

   No. $H(X \mid Y = y)$ is $0.722$, $0$ and $0$. No column could exceed $H(X)$ here: $X$ is binary and uniform, so $H(X) = 1$ bit is already the maximum $\log_2 2$.
4. $X_1, X_2$ are independent fair bits and $X_3 = X_1 \oplus X_2$ (XOR). Use the chain rule to compute $H(X_1, X_2, X_3)$. Compare it with $\sum_i H(X_i)$ and with $H(X_i, X_j)$ for each pair.
   Answer

   $H(X_1) + H(X_2 \mid X_1) + H(X_3 \mid X_1, X_2) = 1 + 1 + 0 = 2$ bits. $\sum_i H(X_i) = 3$ bits, so subadditivity is strict. Every pair is independent and uniform on 4 values: $H(X_i, X_j) = 2$ bits. Any two of the three bits fix the third.
5. Prove $H(Y \mid X, Z) \le H(Y \mid X)$. When is it an equality?
   Answer

   $H(Y \mid X, Z) = \sum_x p(x)\, H(Y \mid Z, X = x)$, where $H(Y \mid Z, X = x)$ is the conditional entropy under the distribution $p(y, z \mid x)$. For each $x$ with $p(x) > 0$, Theorem 3 applied to $p(y, z \mid x)$ gives $H(Y \mid Z, X = x) \le H(Y \mid X = x)$. Average with the weights $p(x)$. Equality holds exactly when $Y$ and $Z$ are independent given $X = x$, for every $x$ with $p(x) > 0$.
6. A classifier predicts a label $Y$ from an input $X$. The labels are noisy: for every input, the correct label is flipped to the other class with probability $0.1$. What is the smallest possible average log-loss in bits?
   Answer

   $H(Y \mid X)$. For every $x$, the row $p(y \mid x)$ is $(0.9, 0.1)$ or $(0.1, 0.9)$, with entropy $H_b(0.1) = 0.469$ bits. So $H(Y \mid X) = 0.469$ bits ($0.325$ nats), whatever the distribution of $X$. No model can reach a lower average loss.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Define the conditional entropy $H(Y \mid X)$ as an average.

   Show answer

2. State the chain rule for two variables.

   Show answer

3. State the chain rule for $n$ variables.

   Show answer

4. Why does the chain rule hold? (one line)

   Show answer

5. What does $H(Y \mid X) = 0$ mean?

   Show answer

6. Does conditioning always reduce entropy?

   Show answer

7. Give the bounds on $H(X, Y)$ in terms of $H(X)$ and $H(Y)$.

   Show answer

8. Write $I(X;Y)$ as a difference of entropies.

   Show answer

9. $X$ is a fair coin and $Y = X$. Compute $H(X, Y)$ and $H(Y \mid X)$.

   Show answer

10. How is $H(Y \mid X)$ related to the loss of a classifier?

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "Does more data always reduce uncertainty?" — On average, yes: $H(Y \mid X) \le H(Y)$. Not for every outcome: a surprising observation can raise the entropy.
• "What is the lowest cross-entropy loss a classifier can reach?" — $H(Y \mid X)$, reached by the true $p(y \mid x)$. It is 0 only if the label is a function of the input.
• "How does the chain rule relate to autoregressive models?" — $\log p(x_{1:T}) = \sum_t \log p(x_t \mid x_{<t})$; in expectation, $H(X_{1:T}) = \sum_t H(X_t \mid X_{<t})$. Every order gives the same total; the single terms differ.
• "Why is the information gain of a decision-tree split never negative?" — It is $H(Y) - H(Y \mid S) \ge 0$: the parent distribution is a mixture of the children, and entropy is concave.
• "Is $H(Y \mid X) = H(X \mid Y)$?" — No. They differ by $H(Y) - H(X)$. Mutual information is the symmetric quantity.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. Write marginals and conditional_table for a joint table (a row with $p(x) = 0$ stays zero).
2. Write conditional_entropy(pxy) from the definition, and check it against the chain rule.
3. Search random $2 \times 3$ tables for one where a row entropy exceeds $H(Y)$, and check that the average never does.
4. Check the chain rule for three variables on a random $2 \times 2 \times 2$ table, in two orders.
5. Compute the information gain of a split at the root of a decision tree on a small data set.

11. Watch and read #

Lecture 6: Noisy Channel Coding (I): Inference and Information Measures for Noisy ChannelsDavid MacKay · Information Theory, Pattern Recognition and Neural Networks (channel Jakob Foerster) · 55 min

Joint and conditional entropy, mutual information and the two-bar picture for a noisy channel.

Information Theory, Lecture 1: Defining Entropy and Information - Oxford Mathematics 3rd Yr LectureOxford Mathematics · 54 min

A university lecture that defines entropy, joint and conditional entropy, with the proofs.

Mutual Information, Clearly Explained!!!StatQuest with Josh Starmer · 16 min

A slow, concrete preview of mutual information, the shared part of the two-bar diagram.

• David MacKay, Information Theory, Inference, and Learning Algorithms, free PDF: §8.1 (definitions, the chain rule, Figure 8.1) and exercises 8.2 (one value against the average), 8.6 (a $4 \times 4$ table, with solution) and 8.8 (why the Venn diagram misleads).
• Kevin Murphy, Probabilistic Machine Learning: An Introduction, free PDF: §6.1.3 (joint entropy) and §6.1.4 (conditional entropy, the "on average" remark and the chain rule for $n$ variables).
• The dit Python library, Basic Shannon measures: joint and conditional entropy with code.
• Cover and Thomas, Elements of Information Theory (2nd edition), §2.2, §2.5 and Theorem 2.6.5. The standard textbook (not free).