Mutual Information

⚡ Key Takeaways

Mutual information $I(X;Y)$ measures the amount of information (in bits or nats) that one random variable carries about another — equivalently, the reduction in uncertainty about $X$ from observing $Y$ . Key result: $I(X;Y) = H(X) - H(X\mid Y) \ge 0$ , with equality iff $X \perp Y$ . It applies wherever dependence must be quantified: communication channels, feature selection, neuroscience, statistical inference. Introduced by Claude Shannon (1948).

💡 The Core Insight

Independence means $p(x,y)=p(x)p(y)$ . Mutual information measures how far the true joint distribution is from this independence factorization, using relative entropy as the yardstick. Because relative entropy is nonnegative and vanishes only when its two arguments coincide, mutual information is a faithful "dependence detector": it is exactly zero precisely when independence holds, and it grows as the joint distribution concentrates away from the product structure.

DefinitionMutual Information

Let $X$ and $Y$ be random variables on (possibly distinct) spaces with joint distribution $P_{XY}$ and marginals $P_X$ , $P_Y$ . The mutual information is the relative entropy between the joint and the product of marginals:

1

\quad I(X;Y) = D_{\mathrm{KL}}\!\big(P_{XY}\,\big\|\,P_X\otimes P_Y\big).

Derivation hint: This is the definition. The symbol $\otimes$ denotes the product measure assigning mass $P_X(A)P_Y(B)$ to rectangles $A\times B$ . In the discrete case with joint pmf $p(x,y)$ and marginals $p(x)=\sum_y p(x,y)$ , $p(y)=\sum_x p(x,y)$ :

2

\quad I(X;Y) = \sum_{x\in\mathcal X}\sum_{y\in\mathcal Y} p(x,y)\,\log\frac{p(x,y)}{p(x)\,p(y)}.

Derivation hint: Expand the KL definition $D_{\mathrm{KL}}(P\|Q)=\sum p\log(p/q)$ with $P=p(x,y)$ and $Q=p(x)p(y)$ . In the continuous case with joint density $f(x,y)$ and marginals $f_X,f_Y$ (assuming $P_{XY}\ll P_X\otimes P_Y$ ):

3

\quad I(X;Y) = \int\!\!\int f(x,y)\,\log\frac{f(x,y)}{f_X(x)\,f_Y(y)}\;dx\,dy.

Derivation hint: Replace the joint pmf by the joint density and sums by integrals; the Radon–Nikodym derivative of $P_{XY}$ w.r.t. $P_X\otimes P_Y$ is $f(x,y)/(f_X(x)f_Y(y))$ . Here $\log$ base 2 gives bits, base $e$ gives nats, base 256 gives bytes. Symbols: $\mathcal X,\mathcal Y$ are the alphabets; $H(\cdot)$ below denotes Shannon entropy.

TheoremEquivalent Forms

For discrete random variables, mutual information admits the entropy decompositions

4

\quad I(X;Y) = H(X) - H(X\mid Y) = H(Y) - H(Y\mid X),

5

\quad I(X;Y) = H(X) + H(Y) - H(X,Y),

where $H(X)=-\sum_x p(x)\log p(x)$ , $H(X\mid Y)=-\sum_{x,y}p(x,y)\log p(x\mid y)$ , and $H(X,Y)=-\sum_{x,y}p(x,y)\log p(x,y)$ . Derivation hint: Substitute $p(x,y)=p(x\mid y)p(y)$ into [2] and split the logarithm; for [5] use $p(x\mid y)=p(x,y)/p(y)$ twice.

TheoremFundamental Properties

1. Nonnegativity: $I(X;Y)\ge 0$ , with equality iff $X\perp Y$ . 2. Symmetry: $I(X;Y)=I(Y;X)$ . 3. Bounds: $I(X;Y)\le \min\{H(X),H(Y)\}$ (discrete case). 4. Self-information: $I(X;X)=H(X)$ . 5. Data Processing Inequality: if $X\to Y\to Z$ is a Markov chain, then $I(X;Z)\le I(X;Y)$ . 6. Chain rule: $I(X;Y,Z)=I(X;Y)+I(X;Z\mid Y)$ . 7. Invariance: for invertible smooth maps $\phi,\psi$ , $I(\phi(X);\psi(Y))=I(X;Y)$ .

ProofNonnegativity via Jensen's Inequality

We prove $I(X;Y)\ge0$ and the equality condition.

Step 1. Write, using [2],

6

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

Derivation hint: Negate [2] and flip the fraction inside the log.

Step 2. The function $\log$ is concave, so by Jensen's inequality applied to the expectation under $p(x,y)$ ,

7

\quad -I(X;Y)=\mathbb E\!\left[\log\frac{p(X)p(Y)}{p(X,Y)}\right]\le \log\,\mathbb E\!\left[\frac{p(X)p(Y)}{p(X,Y)}\right].

Derivation hint: For concave $\log$ , $\mathbb E[\log U]\le \log \mathbb E[U]$ with $U=p(X)p(Y)/p(X,Y)$ .

Step 3. Evaluate the inner expectation over the support of $p(x,y)$ :

8

\quad \mathbb E\!\left[\frac{p(X)p(Y)}{p(X,Y)}\right]=\sum_{(x,y):p(x,y)>0}p(x,y)\,\frac{p(x)p(y)}{p(x,y)}=\sum_{(x,y):p(x,y)>0}p(x)p(y)\le 1.

Derivation hint: The $p(x,y)$ cancels; the remaining sum over the support of the joint is $\le \sum_{\text{all }x,y}p(x)p(y)=1$ .

Step 4. Thus $-I(X;Y)\le\log 1=0$ , i.e. $I(X;Y)\ge0$ .

Step 5 (equality). Jensen is tight iff $U$ is constant a.s., i.e. $p(x)p(y)/p(x,y)=c$ on the support, forcing $p(x,y)=p(x)p(y)$ everywhere — exactly independence. $\blacksquare$

∎

ProofData Processing Inequality

Assume the Markov chain $X\to Y\to Z$ , i.e. $Z\perp X\mid Y$ .

Step 1. By the chain rule [property 6] applied two ways,

9

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

Derivation hint: Expand $I(X;(Y,Z))$ by conditioning first on $Z$ , then on $Y$ .

Step 2. The Markov property gives $I(X;Z\mid Y)=0$ , since $X$ and $Z$ are conditionally independent given $Y$ . Derivation hint: Conditional MI is zero exactly under conditional independence, by the equality case of nonnegativity applied to the conditional distributions.

Step 3. Substituting, $I(X;Z)+I(X;Y\mid Z)=I(X;Y)$ . Since conditional mutual information $I(X;Y\mid Z)\ge0$ ,

10

\quad I(X;Z)\le I(X;Y).\qquad\blacksquare

Derivation hint: Drop the nonnegative term $I(X;Y\mid Z)$ .

∎

CE

Claude Elwood Shannon

1916–2001

Shannon, an American mathematician and electrical engineer at Bell Labs, founded information theory in his 1948 monograph A Mathematical Theory of Communication. He introduced entropy as a measure of uncertainty and what he called the rate of transmission — now mutual information — as the quantity governing reliable communication over noisy channels. Shannon's genius was to recognize that "information" could be made precise as a measure of reducible uncertainty, divorced from semantic meaning, and that this measure governs hard operational limits. His noisy channel coding theorem established channel capacity $C=\max_{p(x)}I(X;Y)$ as the supremum of achievable error-free rates, making mutual information not a mere mathematical convenience but a physical constant of a communication system.

🧠 Intuition

Think of $I(X;Y)$ as "how many yes/no questions about $X$ you save by first looking at $Y$ ." Before seeing $Y$ , your uncertainty about $X$ is $H(X)$ bits. After seeing $Y$ , it drops to $H(X\mid Y)$ . The mutual information is the average savings, $H(X)-H(X\mid Y)$ . A second picture is the Venn diagram of entropies: draw two overlapping circles of areas $H(X)$ and $H(Y)$ . The total covered area is $H(X,Y)$ , the overlap is $I(X;Y)$ , and the crescents are the conditional entropies $H(X\mid Y)$ and $H(Y\mid X)$ . Equation [5] is just "overlap = sum of circles minus union." (This picture is exactly correct for two variables; for three or more it can produce negative "interaction information" and must be used with care.) A third picture is statistical surprise: each observed pair $(x,y)$ carries pointwise information $\log\frac{p(x,y)}{p(x)p(y)}$ — positive when $x$ and $y$ co-occur more than chance, negative when less. Mutual information is the average of this pointwise log-likelihood ratio, and the average is always nonnegative even though individual terms can be negative.

Figure

Venn-diagram decomposition of entropies. The overlap is the mutual information; the crescents are conditional entropies; the union is the joint entropy.

ExampleBinary Symmetric Channel

Given: A binary input $X\in\{0,1\}$ with $P(X=0)=P(X=1)=\tfrac12$ passes through a channel that flips the bit with probability $\varepsilon=0.1$ , producing output $Y$ . Compute $I(X;Y)$ in bits.

Step 1 — Output marginal. By symmetry, $P(Y=0)=P(Y=1)=\tfrac12$ , so $H(Y)=1$ bit.

Step 2 — Conditional entropy. Given $X$ , the output is wrong with probability $\varepsilon$ :

11

\quad H(Y\mid X)=H_b(\varepsilon)=-\varepsilon\log_2\varepsilon-(1-\varepsilon)\log_2(1-\varepsilon).

Derivation hint: Given $X=x$ , $Y$ is Bernoulli $(\varepsilon)$ away from $x$ ; its entropy is the binary entropy function $H_b$ .

Step 3 — Evaluate. With $\varepsilon=0.1$ :

H_b(0.1)=-0.1\log_2 0.1-0.9\log_2 0.9 = 0.1\cdot3.3219+0.9\cdot0.1520=0.3322+0.1368=0.4690.

Step 4 — Combine. $I(X;Y)=H(Y)-H(Y\mid X)=1-0.4690$ .

\boxed{I(X;Y)=0.531\ \text{bits}}

This is exactly the channel capacity for a uniform input; over a noisy channel each transmitted bit conveys only about half a bit of information.

ExampleBivariate Gaussian

Given: $(X,Y)$ jointly Gaussian with correlation coefficient $\rho=0.8$ . Compute $I(X;Y)$ in nats and bits.

Step 1 — Formula. For a zero-mean bivariate normal,

12

\quad I(X;Y)=-\tfrac12\ln\!\big(1-\rho^2\big)\ \text{nats}.

Derivation hint: Use $I=h(X)+h(Y)-h(X,Y)$ with differential entropy $h=\tfrac12\ln(2\pi e\,\sigma^2)$ for marginals and $\tfrac12\ln\big((2\pi e)^2\det\Sigma\big)$ for the joint, with $\det\Sigma=\sigma_X^2\sigma_Y^2(1-\rho^2)$ ; the $\sigma$ and $2\pi e$ terms cancel.

Step 2 — Evaluate. $1-\rho^2=1-0.64=0.36$ , so

I=-\tfrac12\ln(0.36)=-\tfrac12(-1.0217)=0.5108\ \text{nats}.

Step 3 — Convert to bits. Divide by $\ln 2=0.6931$ :

I=0.5108/0.6931=0.7370\ \text{bits}.

\boxed{I(X;Y)=0.511\ \text{nats}=0.737\ \text{bits}}

Note that as $\rho\to1$ , $I\to\infty$ : perfect deterministic dependence between continuous variables carries unbounded information, reflecting that differential entropy is unbounded below.

⚠️ Common mistake

Differential mutual information is finite and nonnegative, but the differential entropy terms can be negative. Do not conclude that $I(X;Y)$ inherits the pathologies of differential entropy. Although $h(X)$ can be negative and is not invariant under change of variables, the combination in [3] is a genuine relative entropy: it is nonnegative, invariant under invertible reparametrizations, and equals $+\infty$ when $X$ determines $Y$ . Treat $I$ , not $h$ , as the fundamental object in the continuous setting.

Zero correlation does not imply zero mutual information. Correlation captures only linear dependence; mutual information captures all dependence. The converse (independence) is the only condition that forces $I=0$ .

CounterexampleUncorrelated but Strongly Dependent

Let $X\sim\mathrm{Uniform}(-1,1)$ and $Y=X^2$ . Then

13

\quad \mathrm{Cov}(X,Y)=\mathbb E[X^3]-\mathbb E[X]\mathbb E[X^2]=0-0\cdot\tfrac13=0,

Derivation hint: $X$ is symmetric about $0$ , so all odd moments vanish. so the correlation is exactly zero. Yet $Y$ is a deterministic function of $X$ , so observing $X$ removes all uncertainty about $Y$ : $H(Y\mid X)=0$ and $I(X;Y)=H(Y)>0$ . A dependence-detector based on correlation reports "independent"; mutual information correctly reports strong dependence. This is precisely why MI is preferred for nonlinear feature screening.

connection

Mutual information sits at the hub of several quantitative theories.

Kullback–Leibler Divergence: MI is a KL divergence ([1]); all its properties descend from those of relative entropy.
Shannon Entropy and Conditional Entropy: the decompositions [4]–[5] express MI through these, giving the Venn-diagram picture.
Channel Capacity: $C=\max_{p(x)}I(X;Y)$ is the operational meaning of MI in communication, via Shannon's noisy channel coding theorem.
Fisher Information: for a parametric family near independence, MI is approximated by a quadratic form in the Fisher information metric; locally MI behaves like a squared statistical distance.
Total Correlation and Interaction Information: these multivariate generalizations extend MI beyond two variables, where the naive Venn picture breaks down.
Maximal Information Coefficient and distance correlation: practical estimators built to inherit MI's "zero iff independent" property.

🔬 Where this appears

⏳ History

- 1948 — Claude Shannon publishes A Mathematical Theory of Communication, introducing entropy, conditional entropy, and the "rate of transmission"

R=H(X)-H(X\mid Y)

, the original mutual information, together with the noisy channel coding theorem.

- 1951 — Solomon Kullback and Richard Leibler formalize directed divergence (relative entropy), retroactively revealing MI as a special case.

- 1957–1959 — Aleksandr Khinchin and Andrey Kolmogorov give axiomatic and measure-theoretic foundations; Kolmogorov defines MI for general (non-discrete) probability spaces via the supremum over finite partitions.

- 1959 — I. M. Gelfand and A. M. Yaglom express mutual information between Gaussian processes via spectral densities, extending MI to continuous-time signals.

- 1964 — Alfréd Rényi proposes generalized information measures, prompting study of which axioms uniquely pin down Shannon's MI.

- 1972 — Suguru Arimoto and Richard Blahut independently devise the Arimoto–Blahut algorithm to compute channel capacity

\max_p I(X;Y)

numerically.

- 1980s — Imre Csiszár and János Körner develop the "method of types," giving sharp, MI-based proofs of coding theorems.

- 1990s — MI becomes the dominant criterion in medical image registration (Viola & Wells; Maes et al., 1997).

- 2003–2004 — Alexander Kraskov, Harald Stögbauer, and Peter Grassberger publish the KSG estimator, a

k

-nearest-neighbor method that estimates continuous MI accurately from samples.

- 2018 — Belghazi et al. introduce MINE, estimating MI with neural networks via the Donsker–Varadhan variational bound, fueling MI-based deep representation learning.

open-problem

Estimating mutual information from finite samples is fundamentally hard. For continuous variables, no estimator can be uniformly consistent at a guaranteed rate over all distributions; the convergence rate depends on unknown smoothness, and high-dimensional MI estimation suffers a curse of dimensionality. Popular neural estimators (MINE, InfoNCE) produce lower bounds that are provably loose: McAllester and Stratos (2020) showed any distribution-free lower bound from $n$ samples cannot exceed $O(\ln n)$ , so estimated MI of "tens of bits" from modest data is statistically meaningless. Open and active questions include: (i) the optimal minimax sample complexity for MI estimation under structural assumptions; (ii) trustworthy upper bounds usable as regularizers; (iii) the right multivariate generalization — interaction information can be negative and the Venn picture fails for $\ge3$ variables, leaving "synergy versus redundancy" decompositions (the partial information decomposition of Williams & Beer, 2010) without a fully agreed-upon definition; (iv) MI as a representation-learning objective is invariant to any invertible map, so maximizing it alone cannot prefer "useful" representations — a tension that current theory only partially resolves.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also