Mutual Information

I(X; Y) = D_ KL(p_XY | p_X p_Y) — the information X and Y share.

The idea

The mutual information of two random variables measures how much information each carries about the other.

Definition (Mutual information).

The mutual information of $X$ and $Y$ is the drop in uncertainty about $X$ produced by observing $Y$, $I(X; Y) = H(X) - H(X \mid Y),$ measured in bits when the entropies use base-$2$ logarithms and in nats when they use natural logarithms.

Written out over the joint distribution, the same quantity is

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

This form compares the joint law $p(x, y)$ with the product law $p(x)p(y)$ the pair would follow if the variables were independent, so mutual information measures how far the pair is from independence.

Proposition (Properties of mutual information).

For all $X$ and $Y$, $I(X; Y) = I(Y; X) \ge 0$, with $I(X; Y) = 0$ if and only if $X$ and $Y$ are independent.

Symmetry is visible in the sum, which is unchanged when $x$ and $y$ trade places: what $Y$ reveals about $X$ equals what $X$ reveals about $Y$. Unlike correlation, mutual information registers dependence of any form, not only linear.

The quantities fit a single picture: draw $H(X)$ and $H(Y)$ as two overlapping regions whose union is the joint entropy $H(X, Y)$. The overlap is $I(X; Y)$, and the crescents left over are the conditional entropies $H(X \mid Y)$ and $H(Y \mid X)$, so each identity above reads as a fact about region areas.

Ways to work on it

• Walkthrough. Compute the mutual information of a small joint distribution and verify its basic properties.
• Practice. Read exact mutual information from a small joint table.
• Hardest. Get I(X; Y) from channel entropies, then apply the data-processing inequality.

Not sure where to start? Take the ten-question placement test.