$$

The mutual information measures the dependence between $\mathit{X},\mathit{Y}$ by comparing their distribution to what it would have been if $\mathit{X}$ and $\mathit{Y}$ had been independent, using information divergence. Formally, the mutual information is the divergence between the joint distribution $P_{\mathit{X},\mathit{Y}}$ and the product of the marginals $P_{\mathit{X}}$ and $P_{\mathit{Y}}$:

$$\begin{array}{rl}\mathrm{I}[\mathit{X};\mathit{Y}]& :=\mathrm{D}\left(\begin{array}{c}{\displaystyle \phantom{\left(P_{\mathit{X},\mathit{Y}}\right)}{P}_{\mathit{X},\mathit{Y}}}\\ \\ {\displaystyle \phantom{\left(P_{\mathit{X}}{P}_{\mathit{Y}}\right)}{P}_{\mathit{X}}{P}_{\mathit{Y}}}\end{array}\right)\\ & =\underset{(x,y)\sim (\mathit{X},\mathit{Y})}{\mathrm{E}}\left[\frac{\mathrm{Pr}[\mathit{X}=x\wedge \mathit{Y}=y]}{\mathrm{Pr}[\mathit{X}=x]\mathrm{Pr}[\mathit{Y}=y]}\right]\\ \text{(1)}& & =\mathrm{H}[\mathit{X}]+\mathrm{H}[\mathit{Y}]-\mathrm{H}[\mathit{X},\mathit{Y}]\text{(2)}& & =\mathrm{H}[\mathit{Y}]-\mathrm{H}[\mathit{Y}\mid \mathit{X}].\end{array}$$

Equivalently, let ${\mathit{X}}^{\prime }$ be distributed identically to $\mathit{X}$ and ${\mathit{Y}}^{\prime }$ be distributed identically to $\mathit{Y}$, but with ${\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }$ independent. Then

$$\mathrm{I}[\mathit{X};\mathit{Y}]=\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}}\\ \\ {\displaystyle \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }}\end{array}\right].$$

Since the divergence is nonnegative, $(1)$ shows the subadditivity of entropy and $(2)$ shows that conditioning only decreases entropy.

Properties

Another link to information divergence

We also have

$$\begin{array}{rl}\mathrm{I}[\mathit{X};\mathit{Y}]& =\underset{(x,y)\sim (\mathit{X},\mathit{Y})}{\mathrm{E}}\left[\frac{\mathrm{Pr}[\mathit{Y}=y|\mathit{X}=x]}{\mathrm{Pr}[\mathit{Y}=y]}\right]\\ & =\underset{x\sim \mathit{X}}{\mathrm{E}}\left[\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}|}_{\mathit{X}=x}\right)}{\mathit{Y}|}_{\mathit{X}=x}}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right]\right].\end{array}$$

In other words, the mutual information measures how much (on average) the distribution of $\mathit{Y}$ changes when it gets conditioned on $\mathit{X}$. This expression is convenient if we want to lower bound the mutual information because the term $\mathrm{D}\left[\begin{array}{c}\phantom{\left({\mathit{Y}|}_{\mathit{X}=x}\right)}{\mathit{Y}|}_{\mathit{X}=x}\\ \\ \phantom{\left(\mathit{Y}\right)}\mathit{Y}\end{array}\right]$ is always nonnegative, and if $\mathit{Y}$ is binary we can use asymptotic estimates for the binary divergence to compute it.

Random bits

If $\mathit{X},\mathit{Y}$ are uniform random bits with correlation $\rho$, then using the properties of entropy deficit (and assuming WLOG that $\mathit{X},\mathit{Y}\in \{\pm 1\}$), their mutual information is

$$\begin{array}{rl}\mathrm{I}[\mathit{X};\mathit{Y}]& =\underset{x\sim \mathit{X}}{\mathrm{E}}\left[\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({\mathit{Y}|}_{\mathit{X}=x}\right)}{\mathit{Y}|}_{\mathit{X}=x}}\\ \\ {\displaystyle \phantom{\left(\mathit{Y}\right)}\mathit{Y}}\end{array}\right]\right]\\ \text{(}\mathit{Y}\text{ uniform)}& & =\underset{x\sim \mathit{X}}{\mathrm{E}}\left[\mathrm{D}\left[{\mathit{Y}|}_{\mathit{X}=x}\right]\right]\text{(}\mathit{Y}\in \{\pm 1\}\text{)}& & =\underset{x\sim \mathit{X}}{\mathrm{E}}\left[\mathrm{\Theta }\left(\mathrm{E}{[\mathit{Y}|\mathit{X}=x]}^2\right)\right]& =\underset{x\sim \mathit{X}}{\mathrm{E}}\left[\mathrm{\Theta }((\rho x{)}^2)\right]\\ & =\mathrm{\Theta }\left({\rho }^2\right)\end{array}$$

If $\mathit{X},\mathit{Y}$ are biased bits with $\mathrm{Pr}[\mathit{X}=1]=\mathrm{Pr}[\mathit{Y}=1]=p$ (with $p<1/2$), then their mutual information is

• up to $\mathrm{H}[\mathit{X}]=H(p)=\mathrm{\Theta }(p\log \frac{1}{p})$ if they’re positively correlated;
• only up to $\mathrm{\Theta }(p^2)$ if they’re negatively correlated¹ (note that their correlation cannot be lower than $-\frac{p}{1-p}$).

Additivity

Mutual information itself is not generally sub- or superadditive. For example, if ${\mathit{X}}_1,\dots ,{\mathit{X}}_n,\mathit{Y}$ are all the same random coin flip, we have

$$\mathrm{I}[\mathit{X};\mathit{Y}]=1\sum \mathrm{I}[{\mathit{X}}_i;\mathit{Y}]=n,$$

but if ${\mathit{X}}_1,\dots ,{\mathit{X}}_n$ are independent coin flips and $\mathit{Y}:={\mathit{X}}_1\oplus \cdots \oplus {\mathit{X}}_n$ is their parity, then

$$\mathrm{I}[\mathit{X};\mathit{Y}]=1\sum \mathrm{I}[{\mathit{X}}_i;\mathit{Y}]=0.$$

On the other hand, whenever the ${\mathit{X}}_i$’s are independent like in the second example, then it is superadditive:

$$\mathrm{I}[\mathit{X};\mathit{Y}]\ge \sum \mathrm{I}[{\mathit{X}}_i;\mathit{Y}].$$

Indeed,

$$\begin{array}{rl}\mathrm{I}[\mathit{X};\mathit{Y}]& =\mathrm{H}[\mathit{X}]-\mathrm{H}[\mathit{X}\mid \mathit{Y}]\\ \text{(independence)}& & =(\sum \mathrm{H}[{\mathit{X}}_i])-\mathrm{H}[\mathit{X}\mid \mathit{Y}]\text{(subadditivity)}& & \ge (\sum \mathrm{H}[{\mathit{X}}_i]-\mathrm{H}[{\mathit{X}}_i\mid \mathit{Y}])& \ge \sum \mathrm{I}[{\mathit{X}}_i;\mathit{Y}].\end{array}$$

This is an example of a reverse entropic inequality.

Lower and upper bounds

#to-write

• two main bounds from murphy--probabilistic-ml-advanced.pdf
  • and entropy as a special case?

Conditional mutual information

Similarly, the conditional mutual information $\mathrm{I}[\mathit{X};\mathit{Y}|\mathit{Z}]$ measures the average (over $z\sim \mathit{Z}$) divergence between the conditional random variables ${(\mathit{X},\mathit{Y})|}_{\mathit{Z}=z}$ and an independent copy ${{\mathit{X}}^{\prime }|}_{\mathit{Z}=z},{{\mathit{Y}}^{\prime }|}_{\mathit{Z}=z}$:

$$\begin{array}{rl}\mathrm{I}[\mathit{X};\mathit{Y}|\mathit{Z}]& :=\underset{z\sim \mathit{Z}}{\mathrm{E}}\left[\mathrm{D}\left[\begin{array}{c}{\displaystyle \phantom{\left({(\mathit{X},\mathit{Y})|}_{\mathit{Z}=z}\right)}{(\mathit{X},\mathit{Y})|}_{\mathit{Z}=z}}\\ \\ {\displaystyle \phantom{({{\mathit{X}}^{\prime }|}_{\mathit{Z}=z},{{\mathit{Y}}^{\prime }|}_{\mathit{Z}=z})}{{\mathit{X}}^{\prime }|}_{\mathit{Z}=z},{{\mathit{Y}}^{\prime }|}_{\mathit{Z}=z}}\end{array}\right]\right]\\ & =\mathrm{E}[\log \frac{\mathrm{Pr}[\mathit{X}=x\wedge \mathit{Y}=y|\mathit{Z}=z]}{\mathrm{Pr}[\mathit{X}=x|\mathit{Z}=z]\mathrm{Pr}[\mathit{Y}=y|\mathit{Z}=z]}]\\ & =\mathrm{H}\left[\mathit{X}\right|\mathit{Z}]+\mathrm{H}\left[\mathit{Y}\right|\mathit{Z}]-\mathrm{H}[\mathit{X},\mathit{Y}|\mathit{Z}]\\ \text{(3)}& & =\mathrm{H}\left[\mathit{Y}\right|\mathit{Z}]-\mathrm{H}\left[\mathit{Y}\right|\mathit{X},\mathit{Z}].\end{array}$$

#to-write

• also define this one using distributions instead of random variables?
  • or just rather, just define it based on the non-conditional version

Chain rule

By telescoping, we get

$$\begin{array}{rl}\text{(by (2))}& \mathrm{I}[{\mathit{X}}_1,\dots ,{\mathit{X}}_n;\mathit{Y}]& =\mathrm{H}[\mathit{Y}]-\mathrm{H}\left[\mathit{Y}\right|{\mathit{X}}_1,\dots ,{\mathit{X}}_n]& =\sum \mathrm{H}\left[\mathit{Y}\right|{\mathit{X}}_1,\dots ,{\mathit{X}}_{i-1}]-\mathrm{H}\left[\mathit{Y}\right|{\mathit{X}}_1,\dots ,{\mathit{X}}_i]\\ \text{(by (3))}& & =\sum \mathrm{I}[{\mathit{X}}_i;\mathit{Y}|{\mathit{X}}_1,\dots ,{\mathit{X}}_{i-1}].\end{array}$$

Interaction information

#to-write

• argue that the base case (1 variable) is under-defined: it could be taken as either $-\mathrm{H}[\mathit{X}]$ or $\mathrm{D}[\mathit{X}]$, given that the entropy of the reference distribution gets cancelled out from then on?
• in this choice of sign, $\mathrm{I}[\mathit{X};\mathit{Y};\mathit{Z}]=\mathrm{I}[\mathit{X};\mathit{Y}|\mathit{Z}]-\mathrm{I}[\mathit{X};\mathit{Y}]$ (or denoted with $\mathrm{D}$?) makes sense (?) because
  • it’s positive when $\mathit{X},\mathit{Y}$ have a “shared effect”, e.g. $\mathit{Z}=\mathit{X}\oplus \mathit{Y}$, which leads us to be able to predict them better together than expected
    • (but otoh if you think about it like shared entropy, then it’s clearly negative: everything was looking completely independent so far and now you have a correlation reducing your entropy)
  • it’s negative when $\mathit{X},\mathit{Y}$ have a “shared cause”, e.g. $\mathit{X}=\mathit{Z}$ and $\mathit{Y}=\bar{\mathit{Z}}$, which leads us to be somewhat disappointed in our ability to predict them together given that the pairwise dependences were so strong!
    • (and if you think about like shared entropy, then it’s positive (??))
• I think this choice of sign makes more sense because it’s about revealing information about things that looked more random, it’s about being able to predict better than expected!
  • information != entropy
• if you want $\mathrm{I}[\mathit{X};\mathit{E}]=\mathrm{E}\left[\mathrm{I}\left[\mathit{X}\right|\mathit{E}]\right]$, that would force the prior to be $[\mathit{X}]$ itself?

1. Proof. (a) We have $\mathrm{I}[\mathit{X};\mathit{Y}]\le O(p^2)$ because the total variation distance between $\mathit{X},\mathit{Y}$ and ${\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }$ is $\le O(p^2)$ and the smallest probability of an outcome of ${\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }$ is $\ge p^2$, so the information divergence must be $O(p^2)$. (b) We get $\mathrm{I}[\mathit{X};\mathit{Y}]=\mathrm{\Theta }(p^2)$ when $\mathit{X}=1$ and $\mathit{Y}=1$ are mutually exclusive: this means that $\mathrm{Pr}[\mathit{X}=\mathit{Y}=1]=0$, while $\mathrm{Pr}[{\mathit{X}}^{\prime }={\mathit{Y}}^{\prime }=1]=p^2$, so $\mathrm{I}[\mathit{X};\mathit{Y}]=\mathrm{D}\left(\begin{array}{c}\phantom{(\mathit{X},\mathit{Y})}\mathit{X},\mathit{Y}\\ \\ \phantom{({\mathit{X}}^{\prime },{\mathit{Y}}^{\prime })}{\mathit{X}}^{\prime },{\mathit{Y}}^{\prime }\end{array}\right)\ge D\left(\begin{array}{c}\phantom{\left(0\right)}0\\ \\ \phantom{\left(p^2\right)}{p}^2\end{array}\right)=\mathrm{\Theta }(p^2)$. ↩