Mutual Information — Mathematics Knowledge System

Overview

Mutual information I(X;Y) measures the amount of information that one random variable X contains about another random variable Y. It equals the reduction in uncertainty about X after observing Y (or vice versa, since I(X;Y) is symmetric). Mutual information is zero iff X and Y are independent, and equals H(X) = H(Y) iff X and Y are deterministically related. It is expressible as a KL divergence between the joint distribution and the product of marginals, making it always non-negative. Mutual information is the key quantity optimized in the definition of channel capacity and is fundamental to feature selection in machine learning.

Intuition

Mutual information I(X;Y) answers: 'How much does knowing Y reduce my uncertainty about X?' If X and Y are independent (knowing Y tells you nothing about X), then I(X;Y) = 0. If X determines Y completely, then knowing Y tells you everything about X, so I(X;Y) = H(X). In between, I(X;Y) captures partial dependence. Unlike correlation, mutual information detects any kind of statistical dependence, not just linear relationships. Think of it as the 'shared information' between X and Y — the overlap in their respective entropy circles in a Venn diagram.

Formal Definition

Definition

For discrete random variables X and Y with joint distribution p(x,y) and marginals p(x), p(y):

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

Mutual information definition

I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X)

Entropy reduction forms

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

Joint entropy form

I(X;Y) = D_{\mathrm{KL}}\bigl(p(x,y) \,\|\, p(x)p(y)\bigr)

KL divergence form

I(X;Y) \geq 0, \text{ with equality iff } X \perp\!\!\!\perp Y

Non-negativity

Notation

Notation	Meaning
$I(X;Y)$	Mutual information between X and Y
$H(X\|Y)$	Conditional entropy of X given Y
$I(X;Y\|Z)$	Conditional mutual information given Z

Theorems

Theorem 1: Data Processing Inequality

If X \to Y \to Z forms a Markov chain, then I(X;Z) \leq I(X;Y). Processing data cannot increase mutual information.

Theorem 2: Symmetry of Mutual Information

I(X;Y) = I(Y;X) for all random variables X, Y.

Theorem 3: Chain Rule for Mutual Information

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

Worked Examples

1
Since Y = X exactly, H(X|Y) = 0 (no uncertainty about X once Y is known).
$H(X|Y) = 0$
2
Apply I(X;Y) = H(X) - H(X|Y).
$I(X;Y) = H(X) - 0 = H(X) = 1 \text{ bit}$

✓ Answer

I(X;Y) = 1 bit. Knowing Y completely determines X, so mutual information equals H(X).

Practice Problems

Easyfree response

Using the Venn diagram interpretation, express I(X;Y) in terms of H(X), H(Y), and H(X,Y).

Mediumapplication

Explain how the data processing inequality shows that no deterministic function f can increase mutual information: I(f(X);Y) ≤ I(X;Y).

Common Mistakes

Common Mistake

Assuming I(X;Y) = 0 implies X and Y are uncorrelated but possibly dependent.

I(X;Y) = 0 implies X and Y are fully statistically independent (not just uncorrelated). Mutual information detects all forms of dependence.

Common Mistake

Confusing I(X;Y|Z) < I(X;Y) always (thinking conditioning reduces MI).

Conditioning on Z can either increase or decrease mutual information. The example X XOR Y shows that I(X;Z|Y) > I(X;Z) = 0.

Quiz

Historical Background

Mutual information as a concept emerged directly from Shannon's 1948 paper, where it appeared as the key quantity transmitted through a noisy channel. Shannon called it the 'rate of transmission of information.' The interpretation as a KL divergence between joint and product distributions was formalized in subsequent work. Its role in statistics as a measure of dependence (more general than correlation) was recognized in the 1950s and has grown enormously in importance with machine learning applications.

1948
Shannon defines mutual information implicitly as the information transmitted through a channel.
Claude Shannon
1959
Mutual information formally studied as a measure of statistical dependence.
Rényi
1970s
Data processing inequality formalized, establishing mutual information as central to coding theory.
2000s
Mutual information becomes a standard tool in machine learning for feature selection and independent component analysis.

Summary

Mutual information I(X;Y) = H(X) - H(X|Y) = D_KL(p(x,y)||p(x)p(y)) measures the information shared between two random variables.
I(X;Y) is always non-negative and equals zero iff X and Y are independent; it equals H(X) = H(Y) when X and Y are deterministically related.
The data processing inequality states that for a Markov chain X → Y → Z, I(X;Z) ≤ I(X;Y) — processing data never increases mutual information.
Mutual information is symmetric: I(X;Y) = I(Y;X), unlike conditional entropy which is generally asymmetric.

References

PaperShannon, C.E. (1948). A Mathematical Theory of Communication. Bell System Technical Journal.
BookCover, T. and Thomas, J. (2006). Elements of Information Theory, 2nd ed. Wiley. Ch. 2.
WebsiteWikipedia — Mutual information