Mutual Information

For (discrete) random variables \(X,Y\) with joint probability mass function (pmf) \(p_{XY}\) and marginal pmfs \(p_X,p_Y\), their Mutual Information (MI) is defined as \[I(X;Y) = \sum_{x,y} p(x,y)\log \Big(\frac{p_{XY}(x,y)}{p_X(x)p_Y(y)}\Big)=\mathbb{E}_{p_{XY}}\log \Big[\frac{p_{XY}(x,y)}{p_X(x)p_Y(y)}\Big]\] Note that this is symmetric.

As \(H(X)=I(X;X)\), the Shannon Entropy \(H\) is sometimes called the self-information of \(X\).

We also have the following formulations for \(I(X;Y)\), assuming all entropies and conditional entropies are finite (to avoid \(\infty - \infty\)): \[ I(X;Y)=H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(X,Y)\]

The last formula is reminiscent of set-additive functions \(\mu\) over sets \(A,B\) where \(\mu(A\cap B)=\mu(A)+\mu(B)-\mu(A\cup B)\). More generally, this analogy extends further:

Information theory	Set theory
\(I\) or \(H\)	\(\mu\) (set additive function)
,	\(\cup\)
;	\(\cap\)
\(\mid\)	\(-\) i.e. \(A-B=A\cap B^C\)

For random variables \(X,Y,Z\), the conditional mutual information between \(X,Y\) conditioned on \(Z\) is \[I(X;Y|Z)=\sum_{x,y,z}p_{XYZ}(x,y,z)\log \Big(\frac{p(x,y|z)}{p(x|z)p(y|z)}\Big) = \mathbb{E}_{p_{XYZ}}\log \Big[ \frac{p(x,y|z)}{p(x|z)p(y|z)}\Big]\]

Even though conditioning never increases entropy i.e. \(H(Y|X)\leq H(Y)\), the counterpart does not hold for mutual information, i.e. in general \(I(X;Y|Z)\nleq I(X;Y)\).

Decomposing the joint distribution, we could rewrite this as \(I(X;Y|Z)=\sum_z p(z)I(X;Y|Z=z)\).

The chain rule for mutual information states that \(I(X_1,X_2,\cdots,X_n|Y)=\sum_{i=1}^n I(X_i;Y|X_1,\cdots,X_{i-1})\). Similarly, the conditional chain rule for mutual information simply involves conditioning on another random variable \(Z\) on both sides.

An important inequality here is the data processing inequality which states that given a Markov Chain \(X\to Y \to Z\), \(I(X;Y)\geq I(X;Z)\) i.e. processing data after receiving it cannot increase information.

We also have the following convexity of mutual information result, that for fixed \(p(x)\), \(I(X;Y)\) is a convex functional of \(p(y|x)\). The concavity of mutual information states the opposite, that for fixed \(p(y|x)\), \(I(X;Y)\) is a concave functional of \(p(x)\).

All the Shannon Entropy measures can be rewritten as special cases of conditional mutual information. To see this, let \(\Phi\) be a constant random variable, then we have \(H(X)=I(X;X|\Phi), H(X|Y)=I(X;X|Y), I(X;Y)=I(X;Y|\Phi)\). This fact is relevant to define information measures as in terms of signed measures.