Entropy and KL divergence: Exercises — AI-ML deep dive

This is a self-testing page for Entropy and KL divergence. Every problem hides a full worked solution — try it first, then reveal. Levels climb from L1 Recognition to L5 Mastery. Each level ends with a trap that is easy to fall into, steel-manned so you see why the wrong path feels right.

Intuition Notation you will use on this page — earned first

Before symbols appear in problems, here is what each one is, in plain words:

$p (x)$ — the probability the random thing lands on outcome $x$ . A number between $0$ and $1$ ; all of them add to $1$ .
$lo g_{2}$ — asks "2 to what power gives this number?" We use base $2$ because we measure information in bits (yes/no answers). $lo g_{2} 8 = 3$ because $2^{3} = 8$ .
$ln$ (natural log, base $e \approx 2.718$ ) — same question, different base. Its unit is nats. Convert with $lo g_{2} x = ln x / ln 2$ .
$H (X) = - \sum_{x} p (x) lo g_{2} p (x)$ — entropy, the average number of bits of surprise per observation.
$D_{K L} (p ∥ q) = \sum_{x} p (x) lo g \frac{p ( x )}{q ( x )}$ — KL divergence, the extra bits wasted using model $q$ when truth is $p$ .
$H (p, q) = - \sum_{x} p (x) lo g q (x)$ — cross-entropy, code length under $q$ when truth is $p$ .

Level 1 — Recognition

Exercise 1.1 (L1)

A coin is fair: $p (H) = p (T) = 0.5$ . What is $H (X)$ in bits?

Recall Solution

What we do: plug into $H (X) = - \sum p lo g_{2} p$ . $H (X) = - [0.5 lo g_{2} 0.5 + 0.5 lo g_{2} 0.5]$ Why: $lo g_{2} 0.5 = - 1$ because $2^{- 1} = 0.5$ . $= - [0.5 (- 1) + 0.5 (- 1)] = 1 bit$ Answer: $1$ bit. One binary question ("heads?") settles it.

Exercise 1.2 (L1)

A variable is deterministic: $p (5) = 1$ and every other outcome has probability $0$ . What is $H (X)$ ?

Recall Solution

Only the $x = 5$ term survives (others use the convention $0 lo g 0 = 0$ ): $H (X) = - 1 \cdot lo g_{2} 1 = - 1 \cdot 0 = 0 bits$ Answer: $0$ bits. No surprise — you already know the outcome.

Exercise 1.3 (L1)

Which is true, and why? (a) $D_{K L} (p ∥ q) = D_{K L} (q ∥ p)$ always. (b) $D_{K L} (p ∥ q) \geq 0$ always.

Recall Solution

(a) is false — KL is asymmetric; the two arguments play different roles (which is "truth" vs "model"). (b) is true — by Gibbs' inequality, KL is never negative, and equals $0$ only when $p = q$ . Answer: (b).

Level 2 — Application

Exercise 2.1 (L2)

A biased coin has $p (H) = 0.9, p (T) = 0.1$ . Compute $H (X)$ in bits.

Recall Solution

$H (X) = - [0.9 lo g_{2} 0.9 + 0.1 lo g_{2} 0.1]$ $lo g_{2} 0.9 = - 0.152$ , $lo g_{2} 0.1 = - 3.322$ . $= - [0.9 (- 0.152) + 0.1 (- 3.322)] = 0.137 + 0.332 = 0.469 bits$ Answer: $\approx 0.469$ bits. Less uncertainty than the fair coin's $1$ bit — usually heads, so less to learn.

Exercise 2.2 (L2)

A fair 8-sided die: $p (x) = \frac{1}{8}$ for $x = 1, \dots, 8$ . Find $H (X)$ without summing eight terms.

Recall Solution

What we do: use the maximum-entropy shortcut. For a uniform distribution over $n$ outcomes, $H (X) = lo g_{2} n .$ Why: every term is $\frac{1}{n} lo g_{2} n$ , and there are $n$ of them, so they collapse to $lo g_{2} n$ . $H (X) = lo g_{2} 8 = 3 bits$ Answer: $3$ bits. Three yes/no questions (binary search) pin down one of eight faces.

Exercise 2.3 (L2)

True label $p = [0, 1, 0]$ (class 2); model prediction $q = [0.1, 0.7, 0.2]$ . Compute the cross-entropy $H (p, q)$ in nats.

Recall Solution

$H (p, q) = - [0 \cdot ln 0.1 + 1 \cdot ln 0.7 + 0 \cdot ln 0.2] = - ln 0.7$ Why the zeros vanish: a one-hot label puts all weight on class 2, so only its term survives. $= - (- 0.357) = 0.357 nats$ Answer: $\approx 0.357$ nats. This is exactly the classification loss for this one example.

Level 3 — Analysis

Exercise 3.1 (L3)

True coin $p = (0.5, 0.5)$ , model $q = (0.7, 0.3)$ . Compute $D_{K L} (p ∥ q)$ in bits.

Recall Solution

$D_{K L} (p ∥ q) = 0.5 lo g_{2} \frac{0.5}{0.7} + 0.5 lo g_{2} \frac{0.5}{0.3}$ $lo g_{2} (0.5/0.7) = lo g_{2} 0.714 = - 0.485$ , $lo g_{2} (0.5/0.3) = lo g_{2} 1.667 = + 0.737$ . $= 0.5 (- 0.485) + 0.5 (0.737) = - 0.243 + 0.369 = 0.126 bits$ Answer: $\approx 0.126$ bits. The extra cost per flip of using model $q$ when truth is $p$ .

Exercise 3.2 (L3)

Same two coins, but compute the reverse $D_{K L} (q ∥ p)$ . Compare to Exercise 3.1.

Recall Solution

$D_{K L} (q ∥ p) = 0.7 lo g_{2} \frac{0.7}{0.5} + 0.3 lo g_{2} \frac{0.3}{0.5}$ $lo g_{2} 1.4 = 0.485$ , $lo g_{2} 0.6 = - 0.737$ . $= 0.7 (0.485) + 0.3 (- 0.737) = 0.340 - 0.221 = 0.119 bits$ Answer: $\approx 0.119$ bits. Different from $0.126$ — this is direct proof KL is asymmetric. Now the truth is $q$ and $p$ is the model; the weighting out front changed.

Exercise 3.3 (L3)

Verify the identity $D_{K L} (p ∥ q) = H (p, q) - H (p)$ numerically for $p = (0.5, 0.5)$ , $q = (0.7, 0.3)$ (use bits).

Recall Solution

$H (p) = 1$ bit (fair coin, Ex 1.1). $H (p, q) = - [0.5 lo g_{2} 0.7 + 0.5 lo g_{2} 0.3] = - [0.5 (- 0.515) + 0.5 (- 1.737)] = 0.257 + 0.868 = 1.126 bits$ Then $H (p, q) - H (p) = 1.126 - 1 = 0.126$ bits — matches Exercise 3.1. ✓ Answer: identity confirmed; $0.126$ bits both ways.

Level 4 — Synthesis

Exercise 4.1 (L4)

For a two-outcome distribution $p = (t, 1 - t)$ , the entropy is the binary entropy $H_{b} (t) = - t lo g_{2} t - (1 - t) lo g_{2} (1 - t)$ . Show it is maximized at $t = 0.5$ by finding where its derivative is zero.

Recall Solution

What we do: differentiate w.r.t. $t$ . Using natural log then converting, $\frac{d}{d t} H_{b} (t) = lo g_{2} \frac{1 - t}{t}$ . Why the derivative: the maximum of a smooth concave curve sits where its slope is $0$ . Set $lo g_{2} \frac{1 - t}{t} = 0 \Rightarrow \frac{1 - t}{t} = 1 \Rightarrow t = 0.5$ . What it looks like: the $\cap$ -shaped curve in the figure below peaks dead center at $t = 0.5$ , height $1$ bit, and drops to $0$ at both ends. Answer: $t = 0.5$ , giving $H_{b} = 1$ bit — the maximum.

Exercise 4.2 (L4)

Cross-entropy loss for one training example with true label class 2, $p = [0, 1, 0]$ . The model's logits give $q = [0.2, 0.5, 0.3]$ . Compute the loss in nats. Then say what happens to the loss as the model improves so $q (class 2) \to 1$ .

Recall Solution

$H (p, q) = - ln q_{2} = - ln 0.5 = 0.693 nats$ Limiting behaviour: as $q_{2} \to 1$ , $- ln q_{2} \to - ln 1 = 0$ — the loss vanishes. As $q_{2} \to 0$ , $- ln q_{2} \to + \infty$ — an infinitely confident wrong prediction is infinitely penalized (matches the KL convention: $p > 0, q = 0 \Rightarrow \infty$ ). Answer: $0.693$ nats; loss $\to 0$ as the model gets the right class certain, $\to \infty$ if it drives the true class to zero.

Level 5 — Mastery

Exercise 5.1 (L5)

A source emits symbols ${A, B, C, D}$ with true probabilities $p = (0.5, 0.25, 0.125, 0.125)$ . (a) Find $H (p)$ in bits. (b) You compress using a code built for the uniform model $q = (0.25, 0.25, 0.25, 0.25)$ . Find the average bits used, $H (p, q)$ . (c) Find the wasted bits $D_{K L} (p ∥ q)$ and confirm $H (p, q) = H (p) + D_{K L} (p ∥ q)$ .

Recall Solution

(a) The probabilities are powers of $2$ , so surprisals are clean integers: $H (p) = - [0.5 lo g_{2} 0.5 + 0.25 lo g_{2} 0.25 + 0.125 lo g_{2} 0.125 + 0.125 lo g_{2} 0.125]$ $= - [0.5 (- 1) + 0.25 (- 2) + 0.125 (- 3) + 0.125 (- 3)] = 0.5 + 0.5 + 0.375 + 0.375 = 1.75 bits$ (b) Under $q$ , each symbol costs $- lo g_{2} 0.25 = 2$ bits, so average $= 2$ bits regardless of $p$ : $H (p, q) = - \sum_{x} p (x) lo g_{2} 0.25 = 2 \sum_{x} p (x) = 2 bits$ (c) Wasted: $D_{K L} (p ∥ q) = H (p, q) - H (p) = 2 - 1.75 = 0.25 bits$ Check the identity: $H (p) + D_{K L} = 1.75 + 0.25 = 2 = H (p, q)$ . ✓ Answer: $H (p) = 1.75$ , $H (p, q) = 2$ , $D_{K L} = 0.25$ bits. The uniform code wastes a quarter bit per symbol because it ignores that $A$ is common.

Exercise 5.2 (L5)

Mixture / connective reasoning. Define the mixture $m = \frac{1}{2} (p + q)$ and the Jensen–Shannon quantity $JSD (p, q) = \frac{1}{2} D_{K L} (p ∥ m) + \frac{1}{2} D_{K L} (q ∥ m)$ . For $p = (1, 0)$ and $q = (0, 1)$ , compute JSD in bits.

Recall Solution

Mixture: $m = (0.5, 0.5)$ . First KL: $D_{K L} (p ∥ m) = 1 \cdot lo g_{2} \frac{1}{0.5} + 0 \cdot (\dots) = lo g_{2} 2 = 1$ bit (the $q$ -side term has $p = 0$ weight → $0$ ). Second KL: by symmetry $D_{K L} (q ∥ m) = 1$ bit. $JSD = \frac{1}{2} (1) + \frac{1}{2} (1) = 1 bit$ Answer: $JSD = 1$ bit — the maximum, correctly finite even though $D_{K L} (p ∥ q) = \infty$ here (since $q = 0$ where $p > 0$ ). This is exactly why Jensen-Shannon Divergence is preferred as a symmetric, always-finite alternative, and how KL enters the Evidence Lower Bound (ELBO) and Variational Autoencoders.

Recall Quick self-check (cloze)

Uniform entropy over $n$ outcomes ::: $lo g_{2} n$ KL is zero exactly when ::: $p = q$ everywhere Cross-entropy minus entropy equals ::: $D_{K L} (p ∥ q)$ Binary entropy peaks at $t =$ ::: $0.5$ , giving $1$ bit A confident wrong prediction ( $q \to 0$ where $p > 0$ ) makes the loss ::: $\to \infty$

See also: Mutual Information, Maximum Entropy Principle, Cross-Entropy Loss, Information Gain, F-divergences.