Mutual information and the data processing inequality

Before this lesson: lesson 02 (joint and conditional entropy, the chain rule, the two-bar diagram), lesson 03 (KL divergence, Gibbs' inequality) and lesson 06 (differential entropy, the Gaussian, invariance of KL). Joint and conditional distributions from probability lesson 04 and the multivariate Gaussian from probability lesson 05. Time: about 75 minutes, plus the notebook.

---

Why this matters #

• Feature selection and decision trees. mutual_info_classif in scikit-learn ranks features by their mutual information with the label. The "information gain" of a decision-tree split is the mutual information between the split and the label.
• Representation learning. Contrastive methods (CPC, SimCLR, CLIP) maximize a lower bound on the mutual information between two views of the data (lesson 08). The data processing inequality limits what any encoder can keep.
• Bayesian experimental design. The expected information gain of an experiment is the mutual information between the unknown parameters and the measurement. Choose the sensor location or the simulation that maximizes it.
• Simulation-based inference. A summary statistic $s(y)$ of simulator output can only lose information about the parameters. It loses nothing exactly when it is sufficient.
• Communication. The capacity of a noisy channel, the largest rate of reliable communication, is a maximum of mutual information.

In this track $\log$ is the natural logarithm and gives nats; $\log_2$ gives bits. Tables in this lesson are in bits; Gaussian formulas are in nats. $H_b(p) = -p\log_2 p - (1 - p)\log_2(1 - p)$ is the binary entropy in bits (lesson 01).

1. Predict first #

2. The picture #

2.1 Two bits and a noisy channel #

Let $X$ be a fair bit. Three cases:

• Copy, $Y = X$. Learning $Y$ tells you $X$ exactly: 1 bit of information.
• Independent, $Y$ is a separate fair coin. Learning $Y$ tells you nothing: 0 bits.
• Noisy copy. $Y$ equals $X$ with probability $1 - \varepsilon$ and $1 - X$ with probability $\varepsilon$. This is the binary symmetric channel BSC($\varepsilon$).

For the noisy copy, count the uncertainty about $Y$ in two steps.

1. $Y$ is a fair bit too (each value is reached with probability $\frac12$), so $H(Y) = 1$ bit.
2. If you know $X$, the only uncertainty left is whether the channel flipped the bit: $H(Y \mid X) = H_b(\varepsilon)$.
3. The information is the uncertainty that knowing $X$ removes: $I(X;Y) = H(Y) - H(Y \mid X) = 1 - H_b(\varepsilon)$.

For $\varepsilon = 0.2$: $H_b(0.2) = 0.722$, so $I = 1 - 0.722 = 0.278$ bits. A channel that is right 80% of the time carries much less than 0.8 bits per use.

Interactive figure: loading…

2.2 How far the joint is from independence #

The two-bar picture in the widget is the picture of lesson 02: the mutual information is the overlap of $H(X)$ and $H(Y)$. A second picture compares two tables:

• the real joint table $p(x, y)$;
• the table you would get if $X$ and $Y$ were independent but had the same marginals: $p(x)\,p(y)$.

For each cell, the pointwise mutual information is

It is positive when the pair $(x, y)$ occurs more often than under independence, and negative when it occurs less often. The mutual information is the average pmi under the joint:

Some pmi values can be negative, but the average is never negative: it is a KL divergence (lesson 03).

Interactive figure: loading…

3. Definitions and main results #

3.1 Mutual information #

For discrete random variables $X, Y$ with joint distribution $p(x, y)$ and marginals $p(x)$, $p(y)$, the mutual information is

For densities, replace the sums by integrals. We write a semicolon, $I(X;Y)$, because the two arguments are two groups of variables: $I(X; Y, Z)$ is the information between $X$ and the pair $(Y, Z)$.

Theorem 1 (identities and bounds).

• (a) $I(X;Y) = H(X) - H(X \mid Y) = H(Y) - H(Y \mid X) = H(X) + H(Y) - H(X, Y)$.
• (b) $I(X;Y) \ge 0$, with equality if and only if $X$ and $Y$ are independent.
• (c) $I(X;Y) = I(Y;X)$ and $I(X;X) = H(X)$. For discrete variables, $I(X;Y) \le \min\big(H(X), H(Y)\big)$.

Proof.

1. (a) Write the pmi as $\log\frac{p(x \mid y)}{p(x)} = -\log p(x) - \big(-\log p(x \mid y)\big)$. Take the mean under $p(x, y)$: the first part gives $H(X)$, the second $H(X \mid Y)$. So $I = H(X) - H(X \mid Y)$. Exchange the roles of $X$ and $Y$ for the second form. The chain rule $H(X, Y) = H(Y) + H(X \mid Y)$ (lesson 02) gives the third.
2. (b) $I$ is a KL divergence, so Gibbs' inequality gives $I \ge 0$, with equality only if $p(x, y) = p(x)p(y)$ for every $x, y$: independence.
3. (c) Symmetry is clear from the KL form. With $Y = X$, $H(X \mid X) = 0$, so $I(X;X) = H(X)$. Discrete conditional entropies are $\ge 0$, so $I = H(X) - H(X \mid Y) \le H(X)$, and in the same way $I \le H(Y)$. $\blacksquare$

For continuous variables, (a) and (b) still hold, with differential entropies. The bound (c) fails: differential entropies can be negative, and $I(X;X) = \infty$ for a continuous $X$ (a real number carries infinitely many bits about itself).

3.2 Conditional mutual information and the chain rule #

The conditional mutual information is the mutual information inside each slice $Z = z$, averaged over $z$:

It is 0 if and only if $X$ and $Y$ are independent given $Z$. Add and subtract $H(X \mid Z)$ to get the chain rule for mutual information:

Conditioning can increase mutual information. Let $X$ and $Y$ be independent fair bits and $Z = X \oplus Y$ (XOR). Then $I(X;Y) = 0$. But once you know $Z$, knowing $X$ tells you $Y$ exactly: $I(X;Y \mid Z) = 1$ bit. This is why the three-circle Venn picture fails for three variables (lesson 02).

3.3 Mutual information of Gaussians #

Theorem 2 (Gaussian mutual information). Let $(X, Y)$ be jointly Gaussian with positive definite covariance $\Sigma = \begin{pmatrix} \Sigma_{XX} & \Sigma_{XY} \\ \Sigma_{YX} & \Sigma_{YY} \end{pmatrix}$. Then

For two scalars with correlation $\rho$: $I(X;Y) = -\frac12\log(1 - \rho^2)$.

Proof.

1. Use $I = h(X) + h(Y) - h(X, Y)$ (Theorem 1a with differential entropies).
2. A $k$-dimensional Gaussian has $h = \frac12\log((2\pi e)^k\det\Sigma)$ (lesson 06). The factors $(2\pi e)^{d_X}(2\pi e)^{d_Y}/(2\pi e)^{d_X + d_Y} = 1$ cancel, and the log-dets give the formula.
3. Scalars: $\det\Sigma = \sigma_X^2\sigma_Y^2 - \rho^2\sigma_X^2\sigma_Y^2 = \sigma_X^2\sigma_Y^2(1 - \rho^2)$, so $I = \frac12\log\frac{\sigma_X^2\sigma_Y^2}{\sigma_X^2\sigma_Y^2(1 - \rho^2)} = -\frac12\log(1 - \rho^2)$. $\blacksquare$

A check with the other form. Given $X = x$, $Y$ is Gaussian with variance $\sigma_Y^2(1 - \rho^2)$, for every $x$. So $I = h(Y) - h(Y \mid X) = \frac12\log\frac{\sigma_Y^2}{\sigma_Y^2(1 - \rho^2)}$ ✓. The mutual information depends only on $\rho$, not on the scales. At $\rho = 0.9$ it is $0.830$ nats ($1.198$ bits); as $\rho \to \pm 1$ it goes to infinity.

Mutual information sees nonlinear dependence. Correlation measures only linear dependence. Let $X$ be uniform on $\{-1, 0, 1\}$ and $Y = X^2$. Then $\operatorname{Cov}(X, Y) = \mathbb{E}[X^3] - \mathbb{E}[X]\,\mathbb{E}[X^2] = 0 - 0 = 0$: the correlation is 0. But $Y$ is a function of $X$, so $H(Y \mid X) = 0$ and $I(X;Y) = H(Y) = H(\frac13, \frac23) = 0.918$ bits. The formula $-\frac12\log(1 - \rho^2)$ is the mutual information only for jointly Gaussian variables.

3.4 Invariance under invertible maps #

Theorem 3. Let $f$ and $g$ be invertible maps (for densities: smooth, with smooth inverses). Then $I(f(X); g(Y)) = I(X;Y)$.

Proof (densities).

1. Let $U = f(X)$ and $V = g(Y)$. By the change of variables, at $x = f^{-1}(u)$ and $y = g^{-1}(v)$: $p_{UV}(u, v) = \frac{p_{XY}(x, y)}{|\det J_f(x)|\,|\det J_g(y)|}$, $p_U(u) = \frac{p_X(x)}{|\det J_f(x)|}$ and $p_V(v) = \frac{p_Y(y)}{|\det J_g(y)|}$.
2. In the ratio $\frac{p_{UV}}{p_U\,p_V}$ the Jacobian factors cancel, so $\operatorname{pmi}_{UV}(u, v) = \operatorname{pmi}_{XY}(x, y)$ at every point.
3. Take the mean: $I(U;V) = I(X;Y)$. $\blacksquare$

For discrete variables an invertible map is a relabelling, which changes nothing. In contrast, the differential entropy changes, $h(f(X)) = h(X) + \mathbb{E}[\log|\det J_f(X)|]$ (lesson 06), and the correlation changes under nonlinear maps. Mutual information describes only the dependence, not the coordinates. This makes it the right quantity for continuous data with arbitrary units.

Interactive figure: loading…

3.5 The data processing inequality #

$X \to Y \to Z$ is a Markov chain if $p(x, y, z) = p(x)\,p(y \mid x)\,p(z \mid y)$: $Z$ is produced from $Y$ alone, without looking at $X$. Equivalently, $X$ and $Z$ are independent given $Y$: $I(X;Z \mid Y) = 0$. Every function $Z = g(Y)$, and every random processing of $Y$ with its own independent noise, gives a Markov chain.

Theorem 4 (data processing inequality, DPI). If $X \to Y \to Z$ is a Markov chain, then

Equality holds if and only if $I(X;Y \mid Z) = 0$: once $Z$ is known, $Y$ tells nothing more about $X$.

Proof.

1. Markov property: $I(X;Z \mid Y) = 0$.
2. Apply the chain rule for $I(X; Y, Z)$ in two orders: $I(X; Y, Z) = I(X;Z) + I(X;Y \mid Z) = I(X;Y) + I(X;Z \mid Y)$.
3. With step 1, $I(X;Y) = I(X;Z) + I(X;Y \mid Z)$.
4. Conditional mutual information is $\ge 0$, so $I(X;Y) \ge I(X;Z)$, with equality exactly when $I(X;Y \mid Z) = 0$. $\blacksquare$

Two channels in a row. $X$ is a fair bit, $Y$ = BSC(0.2) of $X$, and $Z$ = BSC(0.2) of $Y$. $Z$ differs from $X$ when exactly one of the two channels flips: probability $0.2 \cdot 0.8 + 0.8 \cdot 0.2 = 0.32$. So $Z$ is BSC(0.32) of $X$, and $I(X;Z) = 1 - H_b(0.32) = 1 - 0.904 = 0.096$ bits, much less than $I(X;Y) = 0.278$ bits.

Interactive figure: loading…

Corollaries.

• $I(X; g(Y)) \le I(X;Y)$ for every function $g$: computing a feature cannot add information.
• A Markov chain also runs backwards, $Z \to Y \to X$, so the DPI also gives $I(X;Z) \le I(Y;Z)$.
• A second proof of Theorem 3: for an invertible $f$, both $Y \to X \to f(X)$ and $Y \to f(X) \to X$ are Markov chains, so the DPI gives $\le$ in both directions.

Sufficient statistics. Let $\theta$ be a parameter with a prior, $Y$ the data and $T = T(Y)$ a statistic. $\theta \to Y \to T$ is a Markov chain, so $I(\theta; T) \le I(\theta; Y)$. The statistic $T$ is sufficient for $\theta$ when $p(y \mid t, \theta)$ does not depend on $\theta$ (Fisher's definition). Then $\theta \to T \to Y$ is also a Markov chain, and $I(\theta; T) = I(\theta; Y)$ for every prior. Example: $n$ coin flips with bias $\theta$, and $T$ = the number of heads. Given $T = t$, every sequence with $t$ heads has probability $1/\binom{n}{t}$, whatever $\theta$ is. So the count keeps all the information about $\theta$, and the order of the flips adds nothing.

The DPI for KL divergence, and why deterministic encoders break $I(X;Z)$

DPI for KL. Send two input distributions $P$ and $Q$ through the same channel $K(y \mid x)$, giving output distributions $PK$ and $QK$. Then $\mathrm{KL}(PK\,\|\,QK) \le \mathrm{KL}(P\,\|\,Q)$.

1. Form the joints $P_{XY}(x, y) = P(x)K(y \mid x)$ and $Q_{XY}(x, y) = Q(x)K(y \mid x)$. In their log-ratio the channel cancels, so $\mathrm{KL}(P_{XY}\,\|\,Q_{XY}) = \mathrm{KL}(P\,\|\,Q)$.
2. Factor the same joints through the output: $\mathrm{KL}(P_{XY}\,\|\,Q_{XY}) = \mathrm{KL}(PK\,\|\,QK) + \mathbb{E}_{y \sim PK}\big[\mathrm{KL}(P_{X \mid y}\,\|\,Q_{X \mid y})\big] \ge \mathrm{KL}(PK\,\|\,QK)$. $\blacksquare$

The DPI for mutual information is the special case $P = p(x, y)$ and $Q = p(x)p(y)$ with the channel acting on $y$. The same holds for every f-divergence (lesson 08).

Deterministic encoders. Let $X$ be continuous and $Z = f(X)$ with $f$ injective and smooth. Then $I(X;Z) = \infty$: knowing $X$ gives $Z$ exactly, and a real number carries infinitely many bits. So "the encoder compresses the input", measured by $I(X;Z)$, means nothing for a deterministic network on continuous inputs. It needs noise in the encoder ($Z = f(X) + \sigma\varepsilon$) or a discrete $Z$. This point matters in the information-bottleneck debate about deep networks (lesson 10).

3.6 Estimating mutual information from samples #

In practice we have $N$ samples, not the joint distribution. The simplest estimator is the plug-in estimator: count the pairs, form the empirical table $\hat p(x, y)$, and compute $\hat I = I(\hat p)$. For independent or weakly dependent variables it is biased upward:

1. $\hat I \ge 0$ always. If the true value is 0, every error is upward: a finite sample always shows some spurious dependence.
2. More precisely, each plug-in entropy is biased down, $\mathbb{E}[\hat H] \approx H - \frac{K - 1}{2N}$ nats for $K$ cells with positive probability and $N \gg K$ (the Miller–Madow correction). In $\hat I = \hat H(X) + \hat H(Y) - \hat H(X, Y)$ the joint entropy has the most cells, so it has the most bias. For independent $X, Y$ with $K_X$ and $K_Y$ values, the bias of $\hat I$ is about

The bias is not always upward. For $Y = X$, the joint table has only $K_X$ positive cells, so $\hat I = \hat H(X)$, which is biased down by $\frac{K_X - 1}{2N}$.

Test before you trust. A small positive $\hat I$ is not evidence of dependence. Compare it with a permutation baseline: shuffle $Y$ many times (this destroys any dependence but keeps both marginals), recompute $\hat I$ each time, and see where the real value falls. $2N\hat I$ is the G-test statistic of classical statistics; under independence it is approximately $\chi^2$ with $(K_X - 1)(K_Y - 1)$ degrees of freedom, whose mean gives the bias formula above.

Interactive figure: loading…

For continuous data you must also choose bins, and the answer depends on them. The $k$-nearest-neighbour (KSG) estimator of Kraskov, Stögbauer and Grassberger avoids bins and is used by mutual_info_regression and mutual_info_classif in scikit-learn; it is still biased in high dimensions. For high-dimensional data such as images, tables and neighbours fail, and we need the variational bounds of lesson 08.

3.7 Channel capacity, in one paragraph #

A channel is a conditional distribution $p(y \mid x)$. Its capacity is $C = \max_{p(x)} I(X;Y)$, the largest mutual information over all input distributions. Shannon's channel coding theorem says that reliable communication is possible at every rate below $C$ bits per channel use, and impossible above it. For the BSC, $I = H_b\big(a(1 - \varepsilon) + (1 - a)\varepsilon\big) - H_b(\varepsilon)$ for input $P(X = 1) = a$; it is largest at $a = \frac12$, so $C = 1 - H_b(\varepsilon)$. For $\varepsilon = 0.1$, $C = 0.531$ bits per use (MacKay, chapters 9–10).

Answers to section 1. (1) $1 - H_b(0.2) = 0.278$ bits: much less than 0.8 bits. (2) No. $X \to Y \to Z$ and then any processing of $Z$ is still a Markov chain from $X$, so the DPI gives $I(X; \text{result}) \le I(X;Z) \le I(X;Y)$. For two BSC(0.2) in a row, $I(X;Z) = 0.096$ bits. (3) The correlation is 0, but $I(X;Y) = H(Y) = 0.918$ bits: $Y$ is a function of $X$.

4. Worked example #

(a) A forecast table, three ways. $X$: heavy rain observed (1) or not (0). $Y$: heavy rain forecast (1) or not (0).

$p(x, y)$	$Y = 0$	$Y = 1$	$p(x)$
$X = 0$	0.70	0.10	0.80
$X = 1$	0.05	0.15	0.20
$p(y)$	0.75	0.25

In bits:

• From $X$. $H(X) = H_b(0.2) = 0.722$. The columns give $p(x \mid y)$: $H(X \mid Y = 0) = H_b(\frac{0.05}{0.75}) = H_b(0.0667) = 0.353$ and $H(X \mid Y = 1) = H_b(\frac{0.15}{0.25}) = H_b(0.6) = 0.971$. So $H(X \mid Y) = 0.75 \cdot 0.353 + 0.25 \cdot 0.971 = 0.508$ and $I = 0.722 - 0.508 = 0.214$.
• From $Y$. $H(Y) = H_b(0.25) = 0.811$. The rows give $H(Y \mid X) = 0.8\,H_b(\frac{0.10}{0.80}) + 0.2\,H_b(\frac{0.15}{0.20}) = 0.8 \cdot 0.544 + 0.2 \cdot 0.811 = 0.597$, and $I = 0.811 - 0.597 = 0.214$ ✓.
• KL form. The pmi values $\log_2\frac{p(x, y)}{p(x)p(y)}$ are $\log_2\frac{0.70}{0.60} = 0.222$, $\log_2\frac{0.10}{0.20} = -1$, $\log_2\frac{0.05}{0.15} = -1.585$ and $\log_2\frac{0.15}{0.05} = 1.585$. Weighted by $p(x, y)$: $0.1557 - 0.1000 - 0.0792 + 0.2377 = 0.2142$ ✓. Two pmi values are negative; the average is not.

A forecast of rain makes you less sure about the outcome for that one value ($H(X \mid Y = 1) = 0.971 > H(X) = 0.722$), but on average the forecast helps.

(b) Gaussians. For $\rho = 0.8$: $I = -\frac12\log(1 - 0.64) = -\frac12\log 0.36 = 0.511$ nats $= 0.737$ bits. For $\rho = 0.9$: $-\frac12\log 0.19 = 0.830$ nats. Five independent pairs with $\rho = 0.8$ (so $X, Y \in \mathbb{R}^5$) have $I = 5 \cdot 0.511 = 2.554$ nats: mutual information adds over independent pairs, because the covariance is block diagonal and the determinants multiply.

(c) Two channels in a row. $X$ fair, $Y$ = BSC(0.2) of $X$, $Z$ = BSC(0.2) of $Y$:

• $I(X;Y) = 1 - H_b(0.2) = 1 - 0.722 = 0.278$ bits;
• $Z$ = BSC(0.32) of $X$, so $I(X;Z) = 1 - H_b(0.32) = 1 - 0.904 = 0.096$ bits $\le I(X;Y)$ ✓;
• $I(Y;Z) = 0.278$ bits, so $I(X;Z) \le I(Y;Z)$ holds too.

(d) A sufficient statistic. $\theta$ is $0.2$ or $0.8$ with probability $\frac12$ each, and $Y$ is three flips of a coin with bias $\theta$. Exact computation over the $2 \times 8$ joint table (notebook): $I(\theta; Y) = 0.594$ bits; with $T$ = the number of heads, $I(\theta; T) = 0.594$ bits (nothing lost); with only the first flip, $I(\theta; Y_1) = 1 - H_b(0.2) = 0.278$ bits.

(e) Plug-in bias. Independent $X, Y$ with 4 values each and $N = 500$: $\mathbb{E}[\hat I] \approx 3 \cdot 3/(2 \cdot 500) = 0.009$ nats, although the true value is 0.

5. In code #

SciPy computes entropies and KL divergences; scikit-learn has the plug-in estimator (mutual_info_score, in nats) and the kNN estimator (mutual_info_regression).

import numpy as np
from scipy.stats import entropy, multivariate_normal
from sklearn.metrics import mutual_info_score
from sklearn.feature_selection import mutual_info_regression

# (a) MI of the forecast table, three ways (bits)
pxy = np.array([[0.70, 0.10],
                [0.05, 0.15]])
px, py = pxy.sum(axis=1), pxy.sum(axis=0)
H = lambda t: entropy(np.ravel(t), base=2)
print(H(px) + H(py) - H(pxy))                                            # 0.2142
print(entropy(pxy.ravel(), np.outer(px, py).ravel(), base=2))           # 0.2142, the KL form
print(mutual_info_score(None, None, contingency=100 * pxy) / np.log(2))  # 0.2142 (sklearn wants counts, gives nats)

# (b) Gaussian MI from entropies: h(X) + h(Y) - h(X, Y)
C = np.array([[1.0, 0.9], [0.9, 1.0]])
h = lambda S: multivariate_normal(cov=S).entropy()
print(h(C[:1, :1]) + h(C[1:, 1:]) - h(C), -0.5 * np.log(1 - 0.9**2))    # 0.8304 0.8304

# (c) DPI: a joint table times a channel matrix p(z | y) gives p(x, z)
K = np.array([[0.8, 0.2], [0.2, 0.8]])        # BSC(0.2); each row sums to 1
pxy2 = np.diag([0.5, 0.5]) @ K                 # X fair, Y = BSC(X)
pxz = pxy2 @ K                                 # Z = BSC(Y)
for t in (pxy2, pxz):
    print(entropy(t.ravel(), np.outer(t.sum(1), t.sum(0)).ravel(), base=2))   # 0.2781, then 0.0956

# (d) Plug-in bias for independent X, Y with 4 values each and N = 500 (nats)
rng = np.random.default_rng(0)
est = [mutual_info_score(rng.integers(0, 4, 500), rng.integers(0, 4, 500)) for _ in range(2000)]
print(np.mean(est), 3 * 3 / (2 * 500))         # 0.0089 0.009

# (e) Invariance: x -> x^3 and y -> exp(y) change the correlation, not the MI
x, y = rng.multivariate_normal([0, 0], C, size=5000).T
print(np.corrcoef(x, y)[0, 1], np.corrcoef(x**3, np.exp(y))[0, 1])     # 0.903 0.668
ksg = lambda a, b: mutual_info_regression(a[:, None], b, random_state=0)[0]   # kNN (KSG) estimator, nats
print(ksg(x, y), ksg(x**3, np.exp(y)))        # 0.860 0.823: both near the true 0.830

The kNN estimate is not exactly invariant (distances change under the maps); the true mutual information is. mutual_info_score(labels_x, labels_y) builds the table of counts for you; pass contingency= when you already have one.

6. Where it shows up #

• Feature selection. SelectKBest(mutual_info_classif) keeps the features with the largest estimated mutual information with the label, nonlinear dependence included. Compare the scores with a permutation baseline; small scores of independent features are not zero.
• Decision trees. The information gain of a split $S$ is $H(Y) - H(Y \mid S) = I(Y;S)$, the mutual information between the split and the label (the decision-tree lesson of the ML fundamentals track, in preparation).
• Representations and the DPI. For a label $Y$, an input $X$ and a representation $Z = \operatorname{enc}(X)$, the chain $Y \to X \to Z$ is Markov, so $I(Y;Z) \le I(Y;X)$: an encoder can keep label information or lose it, never create it. It can make the information easier to use for a simple classifier: the DPI is about information, not usable information. Keeping $I(Y;Z)$ while dropping the rest of $X$ is the information bottleneck (lesson 10).
• Contrastive learning. InfoNCE (CPC, SimCLR, CLIP) is a lower bound on the mutual information between two views; lesson 08 derives it.
• Bayesian experimental design. The expected information gain of a design $d$ is $I(\theta; Y \mid d)$. For a linear-Gaussian model it is $\frac12\log\frac{\det\Sigma_{\text{prior}}}{\det\Sigma_{\text{post}}}$, the Gaussian mutual information of section 3.3.
• Simulation-based inference. Neural summary statistics are often trained to maximize a bound on $I(\theta; s(Y))$. The DPI caps them at $I(\theta; Y)$, and sufficiency is the equality case.
• Dependence between scientific fields. The mutual information between a ground-motion amplitude and a site parameter is the same for the amplitude and its logarithm, unlike the correlation. A histogram estimate between two climate indices needs a permutation baseline.

7. Common mistakes #

• "Correlation 0 means independent." For $X$ uniform on $\{-1, 0, 1\}$ and $Y = X^2$, the correlation is 0 but $I = 0.918$ bits. Only for jointly Gaussian variables does $\rho = 0$ imply independence.
• Using $-\frac12\log(1 - \rho^2)$ on non-Gaussian data. It is the mutual information only for jointly Gaussian variables; on other data it uses only the linear part of the dependence.
• Applying the DPI without a Markov chain. $Z$ must depend on $X$ only through $Y$. And conditioning on a third variable can increase mutual information (the XOR example).
• Treating mutual information like entropy for continuous data. $h$ changes with the units; mutual information does not. Continuous mutual information can be infinite ($I(X;X) = \infty$); discrete mutual information is at most $\min(H(X), H(Y))$.
• Trusting a small plug-in estimate. For independent variables it is about $(K_X - 1)(K_Y - 1)/(2N)$ nats, not 0. Use a permutation test.
• Confusing information with usable information. The DPI does not say that preprocessing is useless. It says it cannot add information; it can still make the information easier to extract.

8. Check yourself #

1. $X$ is uniform on $\{-1, 0, 1\}$ and $Y = X^2$. Compute $\operatorname{Corr}(X, Y)$ and $I(X;Y)$ in bits.
   Answer

   $\operatorname{Cov}(X, X^2) = \mathbb{E}[X^3] - \mathbb{E}[X]\,\mathbb{E}[X^2] = 0$, so the correlation is 0. $Y$ is a function of $X$, so $H(Y \mid X) = 0$ and $I = H(Y) = H(\frac13, \frac23) = 0.918$ bits.
2. $(X, Y)$ is jointly Gaussian with $\rho = 0.6$. Give $I(X;Y)$. What happens to $I$ and to $h(X)$ if you replace $X$ by $e^X$?
   Answer

   $I = -\frac12\log 0.64 = 0.223$ nats. $I$ does not change ($e^x$ is invertible). $h(e^X) = h(X) + \mathbb{E}[X]$, because the log-Jacobian of $e^x$ is $x$.
3. $X \to Y \to Z$ is a Markov chain. Prove $I(X;Z) \le I(Y;Z)$.
   Answer

   The chain also runs backwards, $Z \to Y \to X$ ($X$ and $Z$ are independent given $Y$, which is symmetric). The DPI for this chain gives $I(Z;X) \le I(Z;Y)$, and mutual information is symmetric.
4. $X$ and $Y$ are independent with 10 values each, and $N = 1000$. You measure $\hat I = 0.045$ nats. Is that evidence of dependence?
   Answer

   No. The expected value under independence is $9 \cdot 9/2000 = 0.0405$ nats. $2N\hat I = 90$, against a $\chi^2_{81}$ null with mean 81 and standard deviation $12.7$, gives $p \approx 0.23$. A permutation test gives the same message.
5. Give $I(X;X)$ for a discrete $X$ and for a continuous $X$.
   Answer

   Discrete: $I(X;X) = H(X) - H(X \mid X) = H(X)$. Continuous: $\infty$, because knowing $X$ removes an infinite amount of uncertainty about a real number ($h(X \mid X) = -\infty$).
6. What is the capacity of BSC(0.2), and which input distribution reaches it?
   Answer

   $C = 1 - H_b(0.2) = 0.278$ bits per use, reached by the uniform input $P(X = 1) = \frac12$, which makes $H(Y)$ as large as possible (1 bit).

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. Write the mutual information $I(X;Y)$ as a difference of entropies.

   Show answer

2. Write the mutual information as a KL divergence.

   Show answer

3. What is $I(X;Y)$ for a fair bit $X$ sent through BSC($\varepsilon$)?

   Show answer

4. What is the mutual information of two jointly Gaussian scalars with correlation $\rho$?

   Show answer

5. What is $I(X;X)$ for a discrete $X$?

   Show answer

6. State the data processing inequality and its condition.

   Show answer

7. Why does the data processing inequality hold?

   Show answer

8. How does mutual information change under invertible maps $f(X)$, $g(Y)$?

   Show answer

9. What is the expected plug-in mutual information of independent variables with $K_X$ and $K_Y$ values and $N$ samples?

   Show answer

10. Give an example with zero correlation but positive mutual information.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What is mutual information, and why use it instead of correlation?" The KL from the joint to the product of the marginals. It is zero exactly for independent variables, it sees nonlinear dependence, and it does not change under invertible transforms of each variable.
• "Prove the data processing inequality." Expand $I(X; Y, Z)$ with the chain rule in two orders, use $I(X;Z \mid Y) = 0$ and $I(X;Y \mid Z) \ge 0$.
• "Can a neural network's hidden layer contain more information about the label than the input?" No: $Y \to X \to Z$ is Markov, so $I(Y;Z) \le I(Y;X)$. It can contain more usable information for a linear probe.
• "How would you estimate mutual information between two signals?" Discrete: plug-in with a permutation baseline (or a bias correction). Continuous, low dimension: the Gaussian formula if the data are Gaussian, else KSG. High dimension: a variational bound with a learned critic (InfoNCE). Always state the bias.
• "What is the information gain of a decision-tree split?" $H(Y) - H(Y \mid S) = I(Y;S)$.

10. Practice #

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

1. mutual_information(pxy) from a joint table, checked three ways: entropies, the KL form, and sklearn.metrics.mutual_info_score on counts.
2. gaussian_mutual_information(cov, dx) from log-determinants, checked against $-\frac12\log(1 - \rho^2)$ and against invariance under invertible linear maps of each block.
3. The DPI by simulation: multiply a joint table by random channel matrices and check $I(X;Z) \le I(X;Y)$.
4. The plug-in bias: simulate independent data, compare the mean estimate with $(K_X - 1)(K_Y - 1)/(2N)$, and write a permutation test.
5. Rank the features of the breast-cancer data set (sklearn.datasets.load_breast_cancer) by mutual information and by correlation with the label, with one synthetic feature whose spread, not its mean, depends on the class: correlation misses it, mutual information does not.

11. Watch and read #

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

Mutual information from a joint table, step by step, and why it works where correlation fails.

Lecture 7: Noisy Channel Coding (II): The Capacity of a Noisy ChannelJakob Foerster · 47 min

David MacKay's Cambridge lecture: the mutual information of the binary symmetric channel and its capacity.

Mutual Information || @ CMU || Lecture 24b of CS Theory ToolkitRyan O'Donnell · 28 min

The definitions, the chain rule and the data processing inequality, with proofs.

• David MacKay, Information Theory, Inference, and Learning Algorithms, free PDF: §8.1 (mutual information and the two-bar diagram), §8.3 and exercise 8.9 (the data-processing theorem, with solution), chapter 9 (channels and capacity).
• Kevin Murphy, Probabilistic Machine Learning: An Introduction, free PDF: §6.3 (mutual information, conditional mutual information, the data processing inequality, sufficient statistics).
• Thomas Cover and Joy Thomas, Elements of Information Theory, 2nd edition, §2.4–2.9 (mutual information, chain rules, the data-processing inequality, sufficient statistics) and §8.5 (mutual information of densities; example 8.5.1 is the Gaussian case).
• Alexander Kraskov, Harald Stögbauer and Peter Grassberger, "Estimating mutual information" (2004): the kNN (KSG) estimator used by scikit-learn.
• Liam Paninski, "Estimation of entropy and mutual information" (Neural Computation, 2003): the bias of plug-in estimators and how to correct it.