1.45 Mutual information and Jensen's inequality: study notes

Learn AI by Story

1. The idea in one sentence

Mutual information I(X; Y) measures how many bits of uncertainty about X disappear when you learn Y (it is zero exactly when X and Y are independent and never negative), and the reason it can never be negative is Jensen's inequality: for a convex function f, f(E[x]) ≤ E[f(x)].

2. The story from the video

Zoya runs an umbrella stall. Over 100 mornings (illustrative data) she wrote down the sky and whether it rained:

Cloudy and rain: 20 mornings
Cloudy and dry: 15 mornings
Clear and rain: 5 mornings
Clear and dry: 60 mornings

So P(rain) = (20 + 5) ÷ 100 = 0.25 and P(cloudy) = (20 + 15) ÷ 100 = 0.35. Before looking at the sky, her uncertainty about rain is H(rain) = H(0.25) ≈ 0.81 bits.

If the sky is cloudy, P(rain) = 20 ÷ 35 ≈ 0.571 and the uncertainty is about 0.985 bits (nearly a coin flip). If the sky is clear, P(rain) = 5 ÷ 65 ≈ 0.077 and the uncertainty is only about 0.391 bits. Averaging with the weights 0.35 and 0.65 gives 0.35 × 0.985 + 0.65 × 0.391 ≈ 0.60 bits. The drop, 0.811 − 0.599 = 0.212 bits, is the mutual information: looking at the sky is worth about 0.21 bits about rain.

The video then lists the properties: I(X; Y) is symmetric, never negative, and zero exactly when X and Y are independent. It shows that zero correlation does not mean zero mutual information with y = x². Finally, it explains why the number is never negative using Jensen's inequality: with x equal to 1 or 3 with equal chance and f(x) = x², f(E[x]) = 4 but E[f(x)] = 5. For the concave logarithm, log E[x] ≥ E[log x]. Since −log is convex, KL(p ‖ q) ≥ 0, and mutual information is a KL divergence. Uses: feature selection, decision trees and variational autoencoders.

3. Key definitions (glossary)

Self-information I(x): I(x) = −log P(x), the surprise of seeing outcome x. With log₂ the unit is bits; with the natural log it is nats. Plain English: rarer events are more surprising.
Entropy H(X): H(X) = −Σ P(x) log₂ P(x), the average self-information. Plain English: how uncertain X is, in bits.
Joint entropy H(X, Y): the entropy of the pair (X, Y). It lies between max(H(X), H(Y)) and H(X) + H(Y). Plain English: uncertainty of both together.
Conditional entropy H(X given Y): the average uncertainty left in X after learning Y. Plain English: what is still unknown after peeking.
Chain rule: H(X, Y) = H(Y) + H(X given Y). Plain English: learn Y first, then what is left of X.
Mutual information I(X; Y): I(X; Y) = H(X) − H(X given Y) = Σ p(x, y) log₂ [p(x, y) ÷ (p(x) p(y))]. Plain English: bits of X that Y gives away.
KL divergence KL(p ‖ q): Σ p(x) log [p(x) ÷ q(x)] (Kullback and Leibler 1951). It is not symmetric. Plain English: the cost of pretending the data follow q when they follow p.
Relative entropy: another name for KL divergence (Bishop 1.6.1). Plain English: same thing.
Convex function: f(λa + (1 − λ)b) ≤ λf(a) + (1 − λ)f(b) for 0 ≤ λ ≤ 1. Plain English: a "smile": the chord lies above the curve.
Concave function: the reverse, a "frown". The function −f is concave when f is convex. Plain English: a hill.
Jensen's inequality: for convex f, f(E[x]) ≤ E[f(x)]; for concave f the inequality flips. Plain English: averaging first, then bending, gives less than bending first, then averaging (for a smile).
Independence: p(x, y) = p(x) p(y). Plain English: knowing one tells you nothing about the other.
Correlation: a measure of linear relationship. Plain English: it can miss curved relationships.
Pointwise mutual information pmi(x, y): log [p(x, y) ÷ (p(x) p(y))] for one pair of values (D2L 22.11). Plain English: how much more often the pair occurs than chance predicts. Mutual information is its average.
Nat and bit: units of information, log base e versus log base 2. Plain English: bits count yes/no questions.
Strictly convex: the chord lies strictly above the curve; examples are x², eˣ, e⁻ˣ, log(1/x) and x log x (MacKay 2.7). Plain English: no straight stretches.
ELBO (background): the evidence lower bound in variational autoencoders, derived with Jensen. Plain English: a tractable floor under an intractable quantity.
Information gain (background): the entropy reduction from a decision-tree split, equal to the mutual information between the split and the label. Plain English: how much a question helps.

4. Detailed explanation, from basics to the full picture

Step 1: Surprise and entropy

Goodfellow et al. (G3, 3.13) define the self-information of an event as I(x) = −log P(x). Rare events carry more information. Shannon entropy is the expected self-information, H(X) = −Σ P(x) log₂ P(x). For a yes/no variable with P(yes) = p, H(p) = −p log₂ p − (1 − p) log₂(1 − p). A fair coin has H(0.5) = 1 bit; a heavily lopsided one has little entropy.

Step 2: Two variables together

For a pair (X, Y), the joint entropy H(X, Y) lies between max(H(X), H(Y)) and H(X) + H(Y) (D2L 22.11). The conditional entropy H(X given Y) is the leftover uncertainty about X once Y is known. The chain rule connects them: H(X, Y) = H(Y) + H(X given Y) (MacKay 8.1).

Step 3: Mutual information as a reduction in uncertainty

MacKay (8.1) defines I(X; Y) = H(X) − H(X given Y). It is symmetric, so I(X; Y) = I(Y; X) and equally H(Y) − H(Y given X). Zoya's sky tells her as much about rain as rain tells her about the sky.

Step 4: Mutual information as a distance from independence

Bishop (1.6.1) writes it as a KL divergence between the true joint distribution and the product of the marginals:

I[x, y] = KL(p(x, y) ‖ p(x) p(y)) ≥ 0.

If the variables are independent, p(x, y) = p(x) p(y), the two distributions are identical and the KL divergence is zero. The converse also holds: I = 0 only for independent variables.

Step 5: Convex functions and Jensen's inequality

A function is convex if, for any two points, the chord between them lies on or above the curve: f(λa + (1 − λ)b) ≤ λf(a) + (1 − λ)f(b) (Bishop 1.6.1). Jensen's inequality extends this from two points to any average: f(E[x]) ≤ E[f(x)]. MacKay (2.7) calls it "convex-smile, concave-frown" and gives a picture: put masses on a convex curve; their centre of gravity lies above the curve. Strictly convex examples are x², eˣ, e⁻ˣ, log(1/x) and x log x.

Step 6: Why KL ≥ 0

Take f(u) = −ln u, which is convex. Bishop shows KL(p ‖ q) = −Σ p(x) ln [q(x) ÷ p(x)] = E_p[−ln(q ÷ p)]. By Jensen, E[−ln(q ÷ p)] ≥ −ln E[q ÷ p] = −ln Σ q(x) = −ln 1 = 0 when q is a normalised distribution on the same points. So KL(p ‖ q) ≥ 0, and applying this to p(x, y) and p(x) p(y) gives I(X; Y) ≥ 0.

Step 7: Reading the number

I(X; Y) = 0 means independence. At the other extreme, I(X; Y) = H(X) when X is an invertible function of Y (D2L 22.11): Y fully determines X. Everything in between is partial information. Mutual information catches any dependence, linear or not, which is why it is a stronger tool than correlation.

5. Everything the video skipped

Formulas in simple words

H(X) = −Σ P(x) log₂ P(x): average surprise.
I(X; Y) = H(X) − H(X given Y): uncertainty before minus uncertainty after.
I(X; Y) = Σ p(x, y) log₂ [p(x, y) ÷ (p(x) p(y))]: average over all pairs of pmi(x, y).
Jensen: f(E[x]) ≤ E[f(x)] for convex f; reversed for concave f such as log.
pmi(x, y) = log [p(x, y) ÷ (p(x) p(y))]: positive when a pair is more common than independence predicts, negative when it is rarer.

Variants

Bits versus nats: log₂ gives bits; ln gives nats (G3). Converting multiplies by a constant.
Pointwise mutual information: used for single pairs, such as two words (D2L 22.11).
Information gain (background): the same quantity applied to a tree split.
Mutual-information bounds (background): contrastive methods such as InfoNCE optimise a lower bound on mutual information.

Limitations

Estimating I(X; Y) from limited data is hard for continuous or high-dimensional variables (background).
Mutual information does not say which direction a dependence runs, or whether it is causal; it is symmetric.
A value in bits depends on the log base used, so always say bits or nats.

Background

Shannon founded information theory in 1948. This document covers only the pieces in the listed sources.
KL divergence was introduced by Kullback and Leibler in 1951 (Bishop 1.6.1), and it is not symmetric: KL(p ‖ q) ≠ KL(q ‖ p) in general.

Links on the roadmap

Before: 1.43 Monte Carlo sampling and 1.44 MCMC. The two videos used expectations E[f(x)] repeatedly, and Jensen's inequality is a statement about expectations.
After: 1.46 Fourier transform: frequencies in sound and signals.

6. Worked examples with real numbers

Example A: Zoya's mutual information (the uncertainty-drop way)

Setup: the 100-morning table (illustrative): cloudy and rain 20, cloudy and dry 15, clear and rain 5, clear and dry 60.

Marginals: P(rain) = 25 ÷ 100 = 0.25 and P(cloudy) = 35 ÷ 100 = 0.35, so P(clear) = 0.65.
Entropy of rain: H(0.25) = −0.25 log₂ 0.25 − 0.75 log₂ 0.75 = 0.5 + 0.311 ≈ 0.811 bits.
Given cloudy: P(rain) = 20 ÷ 35 ≈ 0.571, so H = −0.571 log₂ 0.571 − 0.429 log₂ 0.429 ≈ 0.985 bits.
Given clear: P(rain) = 5 ÷ 65 ≈ 0.0769, so H ≈ 0.391 bits.
Weighted average: H(rain given sky) = 0.35 × 0.985 + 0.65 × 0.391 ≈ 0.599 bits.
Subtract: I(sky; rain) = 0.811 − 0.599 = 0.212 bits.

Result: I(sky; rain) ≈ 0.21 bits. That is about 0.212 ÷ 0.811 ≈ 26% of her uncertainty about rain removed by looking at the sky.

Example B: The same number from the direct formula

Setup: use I(X; Y) = Σ p(x, y) log₂ [p(x, y) ÷ (p(x) p(y))] with the same table.

Cloudy and rain: p = 0.20, ratio 0.20 ÷ (0.35 × 0.25) ≈ 2.286, log₂ ≈ 1.193, term 0.20 × 1.193 ≈ +0.239.
Cloudy and dry: p = 0.15, ratio 0.15 ÷ (0.35 × 0.75) ≈ 0.571, log₂ ≈ −0.807, term ≈ −0.121.
Clear and rain: p = 0.05, ratio 0.05 ÷ (0.65 × 0.25) ≈ 0.308, log₂ ≈ −1.700, term ≈ −0.085.
Clear and dry: p = 0.60, ratio 0.60 ÷ (0.65 × 0.75) ≈ 1.231, log₂ ≈ 0.300, term ≈ +0.180.
Add the four terms: 0.239 − 0.121 − 0.085 + 0.180 ≈ 0.212.

Result: I(sky; rain) ≈ 0.212 bits, the same answer as Example A. The pairs that are more common than chance (positive pmi) outweigh the rarer ones.

Example C: Zero correlation but high mutual information

Setup: X is uniform on {−1, 0, 1} and Y = X² (illustrative).

E[X] = (−1 + 0 + 1) ÷ 3 = 0.
XY = X³ takes the values −1, 0, 1, so E[XY] = 0.
Covariance = E[XY] − E[X] E[Y] = 0 − 0 = 0, so the correlation is exactly 0.
Y takes the value 0 with probability 1/3 and 1 with probability 2/3, so H(Y) = H(1/3, 2/3) = −(1/3) log₂(1/3) − (2/3) log₂(2/3) ≈ 0.918 bits.
Y is a function of X, so H(Y given X) = 0 and I(X; Y) = H(Y) − H(Y given X) = 0.918 bits.

Result: the correlation is 0 but I(X; Y) ≈ 0.918 bits, which is all of Y's uncertainty. Mutual information sees the curved relationship that correlation misses.

Example D: Jensen's inequality with numbers

Setup: x is 1 or 3 with equal probability, and f(x) = x² (convex).

E[x] = ½ × 1 + ½ × 3 = 2.
f(E[x]) = 2² = 4.
E[f(x)] = ½ × 1² + ½ × 3² = ½ × 1 + ½ × 9 = 5.
Compare: 4 ≤ 5, as Jensen predicts for a convex function.
The gap, 5 − 4 = 1, equals Var(x), because for f(x) = x² we have E[x²] − (E[x])² = Var(x) (check: Var(x) = ½(1 − 2)² + ½(3 − 2)² = 1).

Result: f(E[x]) = 4 ≤ E[f(x)] = 5.

Example E: The concave case with the logarithm

Setup: the same x, 1 or 3 with equal probability, now with the concave function f(x) = ln x.

log of the average: ln E[x] = ln 2 ≈ 0.693.
Average of the logs: E[ln x] = (ln 1 + ln 3) ÷ 2 = (0 + 1.099) ÷ 2 ≈ 0.549.
Compare: 0.693 ≥ 0.549.

Result: ln E[x] ≈ 0.693 ≥ E[ln x] ≈ 0.549, so for a concave function the inequality flips. This is the version behind the evidence lower bound in VAEs (background).

7. Comparison tables

Mutual information versus correlation

Feature	Correlation	Mutual information
Detects linear links	Yes	Yes
Detects curved links	Often no	Yes
Zero means	No linear link	Independent
Sign	Plus or minus	Never negative

Entropy quantities at a glance

Quantity	Symbol	Meaning	Zoya value
Entropy of rain	H(rain)	Uncertainty alone	0.811 bits
Conditional entropy	H(rain given sky)	Left after the sky	0.599 bits
Mutual information	I(sky; rain)	Difference	0.212 bits

Convex versus concave

Property	Convex	Concave
Shape	Smile	Frown
Examples	x², eˣ, −ln x	ln x, √x
Jensen	f(E[x]) ≤ E[f(x)]	f(E[x]) ≥ E[f(x)]
Chord	Above the curve	Below the curve

8. Common mistakes and myths

Myth: zero correlation means independence. Truth: with Y = X² the correlation is 0 but I(X; Y) ≈ 0.918 bits.
Mistake: forgetting the weights when averaging conditional entropies. The 0.985 and 0.391 must be weighted by 0.35 and 0.65, not averaged equally. An equal average would give (0.985 + 0.391) ÷ 2 = 0.688, which is wrong.
Myth: mutual information can be negative. It cannot: it is a KL divergence, and KL ≥ 0 follows from Jensen.
Mistake: mixing bits and nats. Using ln gives nats; using log₂ gives bits.
Myth: pointwise mutual information is never negative. A single pair can have negative pmi (see Example B); only the average I(X; Y) is non-negative.
Mistake: assuming KL divergence is symmetric. KL(p ‖ q) ≠ KL(q ‖ p) in general, so it is not a distance. (Mutual information itself is symmetric.)
Myth: Jensen's inequality always has the same direction. It flips for concave functions.
Mistake: reading I(X; Y) as causation. It says only that knowing one helps predict the other.

9. Real-life and AI uses

Feature selection. Rank inputs by their mutual information with the label. (Background: scikit-learn offers mutual_info_classif.)
Decision trees. (Background: information gain for a split equals the mutual information between the split and the label.)
Variational autoencoders and EM. (Background: these optimise a lower bound log p(x) ≥ E_q[log p(x, z) − log q(z)], derived with Jensen's inequality; this is the ELBO.)
Contrastive learning. (Background: InfoNCE objectives act as bounds on mutual information.)
Language and word embeddings. Pointwise mutual information measures how strongly two words co-occur compared with chance (D2L 22.11).
Weather and everyday decisions. Zoya's stall is the small version: how much does one cheap observation reduce uncertainty about a costly outcome?

10. Self-check questions (with answers)

What is H(0.25) in bits? About 0.811 bits.
How do you compute H(rain given sky) in Zoya's table? Weight the two conditional entropies: 0.35 × 0.985 + 0.65 × 0.391 ≈ 0.599 bits.
What is I(sky; rain)? 0.811 − 0.599 ≈ 0.212 bits.
Is mutual information symmetric? Yes: I(X; Y) = I(Y; X) = H(X) − H(X given Y) = H(Y) − H(Y given X).
When is I(X; Y) equal to zero? Exactly when X and Y are independent.
For X uniform on {−1, 0, 1} and Y = X², what are the correlation and I(X; Y)? Correlation 0, and I(X; Y) = H(Y) ≈ 0.918 bits.
State Jensen's inequality for a convex f. f(E[x]) ≤ E[f(x)].
With x equal to 1 or 3 and f(x) = x², what are f(E[x]) and E[f(x)]? 4 and 5.
Why is KL(p ‖ q) ≥ 0? −ln is convex, so Jensen gives E_p[−ln(q ÷ p)] ≥ −ln E_p[q ÷ p] = −ln 1 = 0.
For the concave logarithm, which is larger, ln E[x] or E[ln x]? ln E[x]; for x equal to 1 or 3, 0.693 ≥ 0.549.

11. Key takeaways, go deeper, next

Key takeaways

I(X; Y) = H(X) − H(X given Y): the bits of uncertainty removed by learning Y.
I(X; Y) = KL(p(x, y) ‖ p(x) p(y)) ≥ 0, with equality exactly when X and Y are independent.
It is symmetric and detects nonlinear dependence that correlation can miss.
Jensen's inequality, f(E[x]) ≤ E[f(x)] for convex f, is what guarantees KL ≥ 0.
In Zoya's data, the sky gives about 0.21 bits about rain.

Go deeper

Bishop, Pattern Recognition and Machine Learning, section 1.6.1 (relative entropy and mutual information).
MacKay, Information Theory, Inference, and Learning Algorithms, sections 2.7 and 8.1.
Zhang et al., Dive into Deep Learning, section 22.11 (information theory).

Next on the roadmap: 1.46 Fourier transform: frequencies in sound and signals.

12. Sources and further reading

Bishop, Pattern Recognition and Machine Learning (2006), Section 1.6.1 Relative entropy and mutual information
MacKay, Information Theory, Inference, and Learning Algorithms (2003), Section 2.7 Jensen's inequality for convex functions and Chapter 8.1 More about entropy
Zhang, Lipton, Li and Smola, Dive into Deep Learning, Section 22.11 Information Theory
Goodfellow, Bengio and Courville, Deep Learning (2016), Chapter 3, section 3.13 Information Theory
Goodfellow, Bengio and Courville, Deep Learning (2016), Chapter 17, section 17.1.2 Basics of Monte Carlo sampling (expectations as averages)
Shannon, A Mathematical Theory of Communication (1948), Entropy and the Markov ("Markoff") approximations to English text

Accuracy note: Zoya's table and every number derived from it, the y = x² example and the Jensen examples are illustrative or computed from stated assumptions, and the arithmetic was checked in Python. Statements marked "(background)", including feature selection tools, information gain in decision trees, the ELBO, InfoNCE and the claim that estimating mutual information is hard, are not from the listed sources and should be checked before being relied on.

Mutual information and Jensen's inequality: study notes