Proof that Mutual Information Is Symmetric

The mutual information (MI) between two random variables captures how much information entropy is obtained about one random variable by observing the other. Since that definition does not specify which is the observed random variable, we might suspect this is a symmetric quantity. In fact, it is; and I claimed that without proof in my previous post. The goal of this post is to show why this definition is indeed symmetric. The proof will highlight a useful interpretation of MI.

Let $X$ and $Y$ be continuous random variables with densities $p_X(x)$ and $p_Y(y)$ respectively. The MI of $X$ and $Y$ is

$\begin{aligned} \text{MI}(X, Y) &= \mathbb{H}[X] - \mathbb{E}_Y\left[ \mathbb{H}[X \mid Y = y]\right] \\ &= -\int_x p_X(x) \ln p_X(x) \text{d}x + \int_y p_Y(y) \int_x p_{X \mid Y}(x, y) \ln p_{X \mid Y}(x, y) \text{d}x \text{d}y \\ &= - \int_y \int_x p_{X, Y}(x, y) \ln p_X(x) \text{d}x \text{d}y + \int_y p_Y(y) \int_x p_{X \mid Y}(x, y) \ln p_{X \mid Y}(x, y) \text{d}x \text{d}y \\ &= - \int_y \int_x p_{X, Y}(x, y) \ln p_X(x) \text{d}x \text{d}y + \int_y \int_x p_{X, Y}(x, y) \ln p_{X \mid Y}(x, y) \text{d}x \text{d}y \\ &= \int_y \int_x p_{X, Y}(x, y) \Big( \ln p_{X \mid Y}(x, y) - \ln p_X(x) \Big) \text{d}x \text{d}y \\ &= \int_y \int_x p_{X, Y}(x, y) \ln \left[ \frac{p_{X \mid Y}(x, y)}{p_X(x)} \right] \text{d}x \text{d}y \\ &= \int_y \int_x p_{X, Y}(x, y) \ln \left[ \frac{p_{X \mid Y}(x, y)}{p_X(x)} \times \frac{p_Y(y)}{p_Y(y)} \right] \text{d}x \text{d}y \\ &= \int_y \int_x p_{X, Y}(x, y) \ln \left[ \frac{p_{X, Y}(x, y)}{p_X(x)p_Y(y)} \right] \text{d}x \text{d}y \\ &= \text{KL}[p_{X, Y} \lVert p_X \otimes p_Y]. \end{aligned} \tag{1}$

In the last line of Eq. $1$, “KL” refers to the KL divergence. Since the KL divergence is non-negative, mutual information is also non-negative. Furthermore, the mutual information is zero if and only if $X$ and $Y$ are independent. This makes intuitive sense: if two random variables are independent, observing one tells you nothing about the other.

Finally, it’s pretty easy to see that we can simply reverse our calculations to get the mutual information of $Y$ and $X$:

$\begin{aligned} \text{MI}(Y, X) &= \mathbb{H}[Y] - \mathbb{E}_X\left[ \mathbb{H}[Y \mid X = x]\right] \\ &= -\int_y p_Y(y)\ln p_Y(y) \text{d}y + \int_x p_X(x) \int_y p_{Y \mid X}(y, x) \ln p_{Y \mid X}(y, x) \text{d}y \text{d}x \\ &= -\int_x \int_y p_{X, Y}(x, y)\ln p_Y(y) \text{d}y \text{d}x + \int_x p_X(x) \int_y p_{Y \mid X}(y, x) \ln p_{Y \mid X}(y, x) \text{d}y \text{d}x \\ &= -\int_x \int_y p_{X, Y}(x, y)\ln p_Y(y) \text{d}y \text{d}x + \int_x \int_y p_{X, Y}(x, y) \ln p_{Y \mid X}(y, x) \text{d}y \text{d}x \\ &= \int_x \int_y p_{X, Y}(x, y) \Big( \ln p_{Y \mid X}(x, y) - \ln p_Y(y) \Big) \text{d}y \text{d}x \\ &= \int_x \int_y p_{X, Y}(x, y) \ln\left[\frac{p_{Y \mid X}(x, y)}{p_Y(y)}\right] \text{d}y \text{d}x \\ &= \int_x \int_y p_{X, Y}(x, y) \ln\left[\frac{p_{Y \mid X}(x, y)}{p_Y(y)} \times \frac{p_X(x)}{p_X(x)}\right] \text{d}y \text{d}x \\ &= \int_x \int_y p_{X, Y}(x, y) \ln\left[\frac{p_{X,Y}(x, y)}{p_X(x)p_Y(y)} \right] \text{d}y \text{d}x \\ &= \text{KL}[p_{X, Y} \lVert p_X \otimes p_Y(y)]. \end{aligned} \tag{2}$

It’s easy to see that these derivations hold if $X$ and $Y$ are both discrete. The tricky case is if $X$ is discrete and $Y$ is continuous. Certainly, the derivations still work if we can interchange integrals and sums, which is true for finite sums. However, when the sums are infinite, we are effectively interchanging limits and integration. I don’t know enough measure theory to know when this is possible; but my very loose understanding is that the main value of Lebesgue integration is that it is easier to know when such regularity conditions hold.