Contents / Information Theory / Mutual Information and Relative Entropy

Chapter 2

Mutual Information and Relative Entropy

How much one variable says about another, how far one distribution sits from another, and the inequalities that tie the two together.

Introduction

How much one variable says about another, how far one distribution sits from another, and the inequalities that tie the two together.

2.1Mutual Information

Mutual information is the quantity that makes information theory a theory of communication rather than of storage alone. It measures how much observing one variable tells you about another, it is symmetric, and it is the maximand in the definition of channel capacity.

Definition 2.1 (Mutual information). For discrete random variables $X$ and $Y$ with joint pmf $p(x,y)$ and marginals $p(x)$ , $p(y)$ , the mutual information is

I(X;Y) = \sum_{x,y} p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}.

Proposition 2.2 (Equivalent forms).

I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X) = H(X)+H(Y)-H(X,Y) = D\bigl(p(x,y)\,\|\,p(x)p(y)\bigr),

and $I(X;X) = H(X)$ .

Proof. Split the logarithm in the definition: $\log_2\frac{p(x,y)}{p(x)p(y)} = \log_2\frac{p(x|y)}{p(x)} = -\log_2 p(x) + \log_2 p(x|y)$ . Averaging the two terms against $p(x,y)$ gives $H(X)$ and $-H(X|Y)$ respectively, proving the first form; exchanging the roles of $x$ and $y$ gives the second. Substituting the chain rule $H(X|Y)=H(X,Y)-H(Y)$ into the first gives the third. The fourth is the definition of relative entropy applied to the pair of distributions $p(x,y)$ and $p(x)p(y)$ on $\mathcal X\times\mathcal Y$ . Finally, $H(X|X)=0$ , so $I(X;X)=H(X)-0=H(X)$ .∎

Notation. The semicolon in $I(X;Y)$ separates the two sides of the information; the comma in $H(X,Y)$ joins variables into one. Thus $I(X;Y,Z)$ is the information that the pair $(Y,Z)$ carries about $X$ , whereas $I(X,Y;Z)$ is the information that $Z$ carries about the pair. The two are different quantities.

Intuition. Take the total description cost of the pair. Describing $X$ and $Y$ separately costs $H(X)+H(Y)$ ; describing them jointly costs $H(X,Y)$ . The saving is the redundancy between them — information that appears twice in the separate description and once in the joint one. That saving is $I(X;Y)$ .

Because entropy is self-information, $I(X;X) = H(X)$ : everything a variable knows about itself is everything it is.

The three entropies and the mutual information partition the joint entropy into three non-overlapping pieces, a decomposition worth keeping at hand.

| Quantity | In terms of the pieces | Meaning |

|---|---|---|

| $H(X\mid Y)$ | left piece | in $X$ only |

| $I(X;Y)$ | middle piece | shared |

| $H(Y\mid X)$ | right piece | in $Y$ only |

| $H(X)$ | left $+$ middle | all of $X$ |

| $H(Y)$ | middle $+$ right | all of $Y$ |

| $H(X,Y)$ | all three | the pair |

Example 2.3 (Two correlated bits). Let $p(0,0)=p(1,1)=0.4$ and $p(0,1)=p(1,0)=0.1$ . Compute $I(X;Y)$ two ways.

Solution. Both marginals are fair bits, so $H(X)=H(Y)=1$ . From the earlier calculation, $H(X,Y) \approx 1.722$ bits, so

I(X;Y) = 1 + 1 - 1.722 = 0.278 \text{ bits}.

By the divergence form, the product of marginals puts $0.25$ in each cell, so

I(X;Y) = 2(0.4)\log_2\frac{0.4}{0.25} + 2(0.1)\log_2\frac{0.1}{0.25} = 0.8(0.6781)+0.2(-1.3219) \approx 0.542 - 0.264 = 0.278.

The two routes agree. Sanity check: $0 < 0.278 < \min(H(X),H(Y)) = 1$ , as required for variables that are dependent but not deterministic functions of each other. □□

Exercises for §2.1 →

2.2Interpretation, and Information in the Presence of a Third Variable

In a communication setting $X$ is what was sent and $Y$ is what was received; $I(X;Y)$ is the number of bits per use that actually got through. The two extremes read off immediately from Proposition Equivalent forms: $I(X;Y)=0$ when $Y$ is independent of $X$ (nothing got through), and $I(X;Y)=H(X)$ when $H(X|Y)=0$ , i.e. $X$ is recoverable from $Y$ (everything got through).

Example 2.4 (Reading a channel's throughput). A source $X$ is uniform on $8$ symbols and the receiver's residual uncertainty is $H(X|Y)=0.8$ bits. How much information crosses per use, and what does Fano say about the decoder?

Solution. $H(X)=\log_2 8 = 3$ , so $I(X;Y)=3-0.8=2.2$ bits per use. Fano's inequality with $|\mathcal X|=8$ gives

P_e \ge \frac{H(X|Y)-1}{\log_2 8} = \frac{0.8-1}{3} < 0,

a vacuous bound — which is the right answer, since $0.8$ bits of residual uncertainty is consistent with a very good decoder. The sharp form $0.8 \le h_2(P_e)+P_e\log_2 7$ gives $P_e \gtrsim 0.15$ , a real constraint. □□

Once a third variable is in play, the natural object is mutual information computed inside each slice of that variable.

Definition 2.5 (Conditional mutual information).

I(X;Y\mid Z) = H(X\mid Z) - H(X\mid Y,Z) = \sum_{x,y,z} p(x,y,z)\log_2\frac{p(x,y\mid z)}{p(x\mid z)\,p(y\mid z)}.

By the conditioning principle, $I(X;Y|Z)\ge 0$ , with equality exactly when $X$ and $Y$ are conditionally independent given $Z$ .

Theorem 2.6 (Chain rule for mutual information).

I(X_1,\dots,X_n;\,Y) = \sum_{i=1}^n I\bigl(X_i;\,Y \mid X_1,\dots,X_{i-1}\bigr).

Proof. Write the left side as a difference of entropies and expand each by the chain rule:

I(X_{1:n};Y) = H(X_{1:n}) - H(X_{1:n}\mid Y) = \sum_{i=1}^n H(X_i\mid X_{<i}) - \sum_{i=1}^n H(X_i \mid X_{<i}, Y).

Pairing the sums term by term, the $i$ -th difference is $H(X_i\mid X_{<i}) - H(X_i\mid X_{<i},Y) = I(X_i;Y\mid X_{<i})$ by the definition of conditional mutual information.∎

Pitfall. Conditioning can increase mutual information. Let $X$ and $Y$ be independent fair bits and let $Z = X \oplus Y$ . Then $I(X;Y)=0$ , but given $Z$ the two bits determine each other, so $I(X;Y\mid Z) = 1$ bit. Conversely, conditioning on a common cause destroys mutual information. There is therefore no general inequality between $I(X;Y)$ and $I(X;Y\mid Z)$ — unlike entropy, where conditioning always reduces.

Intuition. The exclusive-or example is the canonical warning. Two unrelated facts can become perfectly correlated once you learn a constraint that couples them — knowing the parity of two unknown bits turns each into the other's answer key. The "Venn diagram" picture of information, which suggests $I(X;Y|Z) \le I(X;Y)$ , is unreliable precisely here: the three-variable analogue $I(X;Y)-I(X;Y|Z)$ can be negative.

Exercises for §2.2 →

2.3Non-negativity, Data Processing, and Convexity

Theorem 2.7 (Information inequality). $I(X;Y) \ge 0$ , with equality if and only if $X$ and $Y$ are independent.

Proof. By Proposition Equivalent forms, $I(X;Y) = D\bigl(p(x,y)\|p(x)p(y)\bigr)$ , and Gibbs' inequality gives $D \ge 0$ with equality iff the two distributions coincide — that is, iff $p(x,y)=p(x)p(y)$ for all $x,y$ .∎

This single inequality is what turns the identities of the chapter into bounds: subadditivity, conditioning reduces entropy, and the independence bound are all restatements of $I \ge 0$ .

Proposition 2.8 (Elementary properties). Mutual information is symmetric, $I(X;Y)=I(Y;X)$ ; satisfies $I(X;Y)\le \min\bigl(H(X),H(Y)\bigr)$ ; equals $H(X)$ when $Y$ determines $X$ ; and is unchanged by relabelling, $I(f(X);g(Y)) = I(X;Y)$ whenever $f$ and $g$ are injective on the respective supports.

Proof. Symmetry is visible in the definition, which is symmetric in $x$ and $y$ . The bound follows from $I(X;Y)=H(X)-H(X|Y) \le H(X)$ since $H(X|Y)\ge 0$ , and symmetrically for $H(Y)$ . If $H(X|Y)=0$ then $I(X;Y)=H(X)$ . Invariance under injections holds because an injective relabelling leaves the joint pmf's list of values unchanged.∎

The central structural theorem is that information cannot be created by processing. Recall that $X \to Y \to Z$ is a Markov chain when $Z$ is conditionally independent of $X$ given $Y$ , i.e. $p(z\mid y,x) = p(z\mid y)$ — the situation whenever $Z$ is computed from $Y$ alone, possibly with independent randomness.

Theorem 2.9 (Data processing inequality). If $X \to Y \to Z$ is a Markov chain, then

I(X;Z) \le I(X;Y), \qquad I(X;Z)\le I(Y;Z).

Equality in the first holds if and only if $X\to Z\to Y$ is also a Markov chain.

Proof. Expand $I(X;Y,Z)$ by the chain rule for mutual information in both orders:

I(X;Y,Z) = I(X;Z) + I(X;Y\mid Z) = I(X;Y) + I(X;Z\mid Y).

The Markov property says $X$ and $Z$ are conditionally independent given $Y$ , so $I(X;Z\mid Y)=0$ . Therefore

I(X;Z) + I(X;Y\mid Z) = I(X;Y),

and since $I(X;Y\mid Z)\ge 0$ we get $I(X;Z)\le I(X;Y)$ , with equality exactly when $I(X;Y|Z)=0$ , i.e. when $X$ and $Y$ are conditionally independent given $Z$ . The second inequality follows by applying the first to the reversed chain $Z\to Y\to X$ , which is also Markov.∎

Corollary 2.10 (Processing your own data does not help). For any function $g$ , $I\bigl(X; g(Y)\bigr)\le I(X;Y)$ . Also, conditioning on a downstream variable cannot help: if $X\to Y\to Z$ , then $I(X;Y\mid Z)\le I(X;Y)$ .

Proof. For the first, $X\to Y\to g(Y)$ is a Markov chain, so the data processing inequality applies. For the second, the displayed identity in the proof above rearranges to $I(X;Y\mid Z) = I(X;Y) - I(X;Z) \le I(X;Y)$ , since $I(X;Z)\ge0$ .∎

Intuition. No amount of cleverness applied to a received signal recovers information the channel destroyed. A denoiser, a decoder, a neural network — all are functions of $Y$ , and all sit downstream of the bottleneck. This is why the data processing inequality is the backbone of converse proofs: it lets you replace the whole receiver by the single number $I(X;Y)$ .

Example 2.11 (Two noisy hops). A fair bit $X$ passes through a binary symmetric channel with crossover $0.1$ to give $Y$ , then through a second independent such channel to give $Z$ . Verify the data processing inequality numerically.

Solution. For a fair input into a binary symmetric channel with crossover $p$ , the output is also a fair bit, so $I(X;Y)=H(Y)-H(Y|X) = 1 - h_2(p)$ . With $p=0.1$ , $h_2(0.1)\approx 0.469$ , so $I(X;Y)\approx 0.531$ bits.

The two hops compose into one channel that flips the bit exactly when precisely one of the two hops flips it, so the effective crossover is $p' = 0.1(0.9)+0.9(0.1)=0.18$ . Hence $I(X;Z) = 1-h_2(0.18) \approx 1-0.680 = 0.320$ bits.

Check: $0.320 \le 0.531$ . ✓ The inequality is strict, as it must be whenever the second hop is genuinely noisy. □□

Finally, mutual information has a convexity structure that underlies the computation of capacity and of rate–distortion functions.

Theorem 2.12 (Concavity and convexity of mutual information). Write $I(X;Y)$ as a function of the input distribution $p(x)$ and the channel $p(y|x)$ . Then

for fixed $p(y|x)$ , $I(X;Y)$ is a concave function of $p(x)$ ;
for fixed $p(x)$ , $I(X;Y)$ is a convex function of $p(y|x)$ .

Proof. (1) Write $I(X;Y) = H(Y) - H(Y|X)$ . With the channel fixed, $H(Y|X) = \sum_x p(x)H(Y|X=x)$ is linear in $p(x)$ . The output distribution $p(y) = \sum_x p(x)p(y|x)$ is also linear in $p(x)$ , and $H$ is concave in a distribution (Theorem Concavity of entropy), so $H(Y)$ is a concave function of $p(x)$ . A concave function minus a linear one is concave.

(2) Here we use the divergence form. Fix $p(x)$ and let $p_1(y|x), p_2(y|x)$ be two channels with output distributions $q_1, q_2$ ; for $\lambda\in[0,1]$ the mixed channel $p_\lambda = \lambda p_1 + (1-\lambda)p_2$ has output $q_\lambda = \lambda q_1+(1-\lambda)q_2$ . Then $I = D\bigl(p(x)p(y|x)\,\|\,p(x)q(y)\bigr)$ , and relative entropy is jointly convex in its pair of arguments (Theorem Convexity of relative entropy). Since both arguments are affine in the channel, the composition is convex.∎

Note. Claim (1) is why capacity $C=\max_{p(x)}I(X;Y)$ is a well-behaved optimisation: a concave function on the simplex has a unique maximum value, attainable by convex programming (the Blahut–Arimoto algorithm). Claim (2) says that mixing two channels is at least as bad as the mix of their informations — noise does not average favourably.

Exercises for §2.3 →

2.4Relative Entropy

Relative entropy, or Kullback–Leibler divergence, measures how far one distribution is from another. It is not a metric — it is asymmetric and violates the triangle inequality — but it is the correct notion of discrepancy for every question in this subject, because it is exactly the number of bits wasted by using the wrong model.

Definition 2.13 (Relative entropy (Kullback–Leibler divergence)). For probability mass functions $p$ and $q$ on a common alphabet $\mathcal X$ ,

D(p\,\|\,q) = \sum_{x} p(x)\log_2\frac{p(x)}{q(x)} = \mathbb{E}_{X\sim p}\Bigl[\log_2\frac{p(X)}{q(X)}\Bigr],

with the conventions $0\log\tfrac{0}{q} = 0$ and $p\log\tfrac{p}{0} = \infty$ for $p>0$ . Thus $D(p\|q) = \infty$ unless $p$ is absolutely continuous with respect to $q$ , i.e. $q(x)=0 \Rightarrow p(x)=0$ .

Intuition. You built a compressor believing the world follows $q$ . It actually follows $p$ . Then $D(p\|q)$ is the number of extra bits per symbol you spend — the fine for a wrong model, payable on every symbol forever. If your model assigns probability zero to something that actually happens, the fine is infinite, which is the information-theoretic statement of "never say never".

Pitfall. $D$ is not symmetric and the asymmetry is not a technicality; it changes what the divergence rewards. $D(p\|q)$ averages under $p$ , so it punishes a model $q$ that is too narrow (it must cover everything $p$ does). $D(q\|p)$ averages under $q$ and punishes a model that is too broad. In variational inference the choice between "forward" and "reverse" KL is exactly the choice between a mode-covering and a mode-seeking approximation.

Example 2.14 (A mismatched coin model). The true source is Bernoulli $(0.9)$ ; the model is a fair coin. Compute $D(p\|q)$ and $D(q\|p)$ .

Solution. Forward:

D(p\|q) = 0.9\log_2\frac{0.9}{0.5} + 0.1\log_2\frac{0.1}{0.5} = 0.9(0.8480) + 0.1(-2.3219) \approx 0.763 - 0.232 = 0.531 \text{ bits}.

Reverse:

D(q\|p) = 0.5\log_2\frac{0.5}{0.9} + 0.5\log_2\frac{0.5}{0.1} = 0.5(-0.8480)+0.5(2.3219) \approx -0.424 + 1.161 = 0.737 \text{ bits}.

The two differ, confirming asymmetry, and both are positive as Gibbs' inequality requires. Note also that there is a clean shortcut for the forward direction: $D(p\|q) = H(p,q)-H(p) = 1 - 0.469 = 0.531$ , since coding every outcome at $-\log_2 0.5 = 1$ bit gives cross-entropy exactly $1$ . □□

Exercises for §2.4 →

2.5Cross-Entropy and Excess Code Length

Definition 2.15 (Cross-entropy). The cross-entropy of $p$ relative to $q$ is

H(p,q) = -\sum_x p(x)\log_2 q(x),

the expected code length when the code lengths are the ideal lengths $-\log_2 q(x)$ for the model $q$ but the data are drawn from $p$ .

Notation. The symbol $H(p,q)$ for cross-entropy collides with $H(X,Y)$ for joint entropy. The arguments disambiguate: two distributions means cross-entropy, two random variables means joint entropy. Some authors write $H_q(p)$ or $\mathrm{CE}(p,q)$ to avoid the clash.

Theorem 2.16 (Relative entropy is excess code length).

H(p,q) = H(p) + D(p\,\|\,q), \qquad\text{equivalently}\qquad D(p\,\|\,q) = H(p,q) - H(p).

Proof. Insert $\log_2 p(x)$ twice:

H(p,q) = -\sum_x p(x)\log_2 q(x) = -\sum_x p(x)\log_2 p(x) + \sum_x p(x)\log_2\frac{p(x)}{q(x)} = H(p) + D(p\|q).

∎

Combined with the source coding theorem this is a complete operational reading of $D$ . Coding $p$ -distributed data with a code matched to $q$ costs $H(p,q)$ bits per symbol; the best possible is $H(p)$ ; the gap is $D(p\|q)$ , and Gibbs' inequality says the gap is never negative. This is also exactly the statement that maximum-likelihood fitting is divergence minimisation: since $H(p)$ does not depend on the model, minimising cross-entropy over $q$ minimises $D(p\|q)$ .

Intuition. Cross-entropy is what you actually pay; entropy is what you would pay with a perfect model; divergence is the surcharge. Training a classifier by minimising cross-entropy is, in these terms, buying down the surcharge on a code for the labels.

Example 2.17 (Reading the decomposition). The biased coin of the last example has $H(p) = 0.469$ bits. Confirm the excess-length identity against the fair-coin code.

Solution. Under the fair-coin model every outcome gets a $1$ -bit codeword, so $H(p,q) = 0.9(1)+0.1(1) = 1$ bit exactly. Then

D(p\|q) = H(p,q)-H(p) = 1 - 0.469 = 0.531 \text{ bits},

matching the direct computation. Interpretation: coding a million biased flips with a fair-coin code costs $1{,}000{,}000$ bits where $469{,}000$ would have sufficed — $531{,}000$ wasted bits, every one of them attributable to the model error. □□

Exercises for §2.5 →

2.6Gibbs, Log-Sum, Convexity, and Mutual Information

Theorem 2.18 (Gibbs' inequality / information inequality). For any distributions $p$ , $q$ on a common alphabet,

D(p\,\|\,q) \ge 0,

with equality if and only if $p(x)=q(x)$ for every $x$ .

Proof. Via Jensen. Let $S = \{x : p(x)>0\}$ . Since $\log_2$ is concave,

-D(p\|q) = \sum_{x\in S} p(x)\log_2\frac{q(x)}{p(x)} \le \log_2\sum_{x\in S}p(x)\frac{q(x)}{p(x)} = \log_2\sum_{x\in S}q(x) \le \log_2 1 = 0.

Strict concavity makes the first step an equality only when $q(x)/p(x)$ is constant on $S$ , and the second only when $q$ places no mass outside $S$ ; the two together force $q=p$ .

Via log-sum. Apply the log-sum inequality with $a_i = p(x_i)$ and $b_i = q(x_i)$ : the left side is $D(p\|q)$ and the right side is $1\cdot\log_2(1/1) = 0$ . The equality condition — constant ratio $p(x)/q(x)$ — again gives $p=q$ , since both sum to $1$ .∎

Corollary 2.19 (Uniform maximises entropy). For $X$ on a finite alphabet $\mathcal X$ and $u$ the uniform distribution,

D(p\,\|\,u) = \log_2|\mathcal X| - H(X) \ \ge 0.

This is a second, cleaner proof of the upper bound in Theorem Range of entropy, and it exhibits the "distance from uniform" as exactly the entropy deficit — a quantity engineers call the redundancy of the source.

Theorem 2.20 (Convexity of relative entropy). $D(p\,\|\,q)$ is jointly convex in the pair $(p,q)$ : for $\lambda \in [0,1]$ ,

D\bigl(\lambda p_1 + (1-\lambda)p_2 \,\big\|\, \lambda q_1 + (1-\lambda)q_2\bigr) \ \le\ \lambda D(p_1\|q_1) + (1-\lambda)D(p_2\|q_2).

Proof. Fix $x$ and apply the log-sum inequality to the two-term lists $a = (\lambda p_1(x), (1-\lambda)p_2(x))$ and $b = (\lambda q_1(x), (1-\lambda)q_2(x))$ :

\bigl(\lambda p_1(x)+(1-\lambda)p_2(x)\bigr)\log_2\frac{\lambda p_1(x)+(1-\lambda)p_2(x)}{\lambda q_1(x)+(1-\lambda)q_2(x)} \le \lambda p_1(x)\log_2\frac{p_1(x)}{q_1(x)} + (1-\lambda)p_2(x)\log_2\frac{p_2(x)}{q_2(x)},

where the constants $\lambda$ cancel inside each logarithm on the right. Summing over $x$ gives the claim.∎

Proposition 2.21 (Mutual information as a divergence).

I(X;Y) = D\bigl(p(x,y)\,\big\|\,p(x)p(y)\bigr),

so mutual information measures exactly how far the joint distribution sits from independence.

Proof. Immediate from the definitions: the summand $p(x,y)\log_2\frac{p(x,y)}{p(x)p(y)}$ is the divergence summand with the pair $(x,y)$ as the alphabet symbol.∎

Example 2.22 (Mutual information computed as a divergence). Take $p(0,0)=p(1,1)=0.4$ , $p(0,1)=p(1,0)=0.1$ again, and verify Proposition Mutual information as a divergence against the entropy route.

Solution. The marginals are fair bits, so $p(x)p(y) = 0.25$ in every cell. Then

D = 2(0.4)\log_2\frac{0.4}{0.25} + 2(0.1)\log_2\frac{0.1}{0.25} = 0.8(0.6781) + 0.2(-1.3219) \approx 0.5425 - 0.2644 = 0.278 \text{ bits}.

Via entropies: $H(X)=H(Y)=1$ and $H(X,Y)\approx 1.722$ , so $I = 2-1.722 = 0.278$ bits. ✓ Both routes agree, and when $X$ and $Y$ are independent the joint is the product, making both zero. □□

Relative entropy also conditions and chains, exactly as entropy does.

Definition 2.23 (Conditional relative entropy). For joint distributions $p(x,y)$ and $q(x,y)$ ,

D\bigl(p(y|x)\,\|\,q(y|x)\bigr) = \sum_x p(x)\sum_y p(y|x)\log_2\frac{p(y|x)}{q(y|x)}.

Theorem 2.24 (Chain rule for relative entropy).

D\bigl(p(x,y)\,\|\,q(x,y)\bigr) = D\bigl(p(x)\,\|\,q(x)\bigr) + D\bigl(p(y|x)\,\|\,q(y|x)\bigr).

Proof. Factor both joints and split the logarithm:

\sum_{x,y}p(x,y)\log_2\frac{p(x)p(y|x)}{q(x)q(y|x)} = \sum_{x,y}p(x,y)\log_2\frac{p(x)}{q(x)} + \sum_{x,y}p(x,y)\log_2\frac{p(y|x)}{q(y|x)},

and the first sum collapses to $D(p(x)\|q(x))$ because $\sum_y p(x,y)=p(x)$ .∎

Corollary 2.25 (Data processing for divergence). If $p$ and $q$ are pushed through the same channel $r(y|x)$ , producing $\tilde p(y) = \sum_x p(x)r(y|x)$ and $\tilde q$ likewise, then $D(\tilde p\,\|\,\tilde q) \le D(p\,\|\,q)$ .

Theorem 2.26 (Pinsker's inequality (quoted)). With total variation distance $\|p-q\|_{TV} = \tfrac12\sum_x |p(x)-q(x)|$ ,

\|p-q\|_{TV} \le \sqrt{\tfrac{\ln 2}{2}\,D(p\,\|\,q)}\,,

where $D$ is in bits. In particular, small divergence forces small total variation distance.

Note. We do not prove Pinsker's inequality here. The standard argument reduces to the binary case by the data processing inequality for divergence (Corollary Data processing for divergence, with the channel that reports whether $x$ lies in the set where $p>q$ ), and then verifies the two-point inequality $\,2(p-q)^2/\ln 2 \le d(p\|q)$ by calculus. The reduction is within reach; the calculus step is a short but unilluminating computation.

Intuition. Pinsker is the reason divergence deserves the name "divergence": it dominates a genuine metric, so $D(p_n\|q)\to 0$ implies $p_n \to q$ in the ordinary sense. The converse fails badly — two distributions can be within $10^{-9}$ in total variation and have infinite divergence, if one of them assigns probability zero where the other does not.

Exercises for §2.6 →

Common Mistakes

Thinking mutual information can be negative. $I(X;Y)\ge 0$ always. The three-way quantity $I(X;Y)-I(X;Y|Z)$ (the "interaction information") *can* be negative, which is why the Venn picture must be used with care.
**Expecting $I(X;Y\mid Z)\le I(X;Y)$ . ** False in general; the exclusive-or example above is the standard counterexample.
**Confusing $I(X;Y,Z)$ with $I(X,Y;Z)$ . ** The semicolon marks the split. Read it before computing.
**Reading $I(X;Y)=0$ as "no relationship of any kind".** It means exactly statistical independence — which is strong, not weak. There is no residual "higher-order dependence" hiding behind $I=0$ for a pair.
Inferring causation from mutual information. $I$ is symmetric; it cannot distinguish $X$ causing $Y$ from $Y$ causing $X$ from a common cause.
Believing a better decoder can beat the data processing inequality. Every decoder is a function of the received signal and is therefore bound by it.
**Treating $D$ as a distance.** It is asymmetric and fails the triangle inequality. Use it because of its coding meaning, not because it looks like a metric.
Ignoring support mismatch. If $q(x)=0$ while $p(x)>0$ then $D(p\|q)=\infty$ . In practice this is what makes unsmoothed maximum-likelihood language models blow up on unseen words.
**Confusing $D(p\|q)$ with $H(p)-H(q)$ . ** The difference of entropies can have either sign and is unrelated; $D$ involves the cross term $H(p,q)$ .
Forgetting which distribution supplies the weights. The expectation in $D(p\|q)$ is under $p$ . That is the entire source of the asymmetry.
Minimising the wrong direction. Maximum likelihood minimises $D(\hat p_{\text{data}}\|q)$ ; variational inference typically minimises $D(q\|p)$ . They have different optima and different failure modes.
**Reading small $D$ as "the distributions agree everywhere".** $D$ is an average; a rare event can be badly mismodelled with little effect on $D$ and a large effect on a tail estimate.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

← Entropy, Joint and Conditional Entropy Entropy Rates and the AEP →

Helpful?