[Question] Is the sum individual informativeness of two independent variables no more than their joint informativeness?

[Ronny Fernandez]

Is it true that:

If I(X;Y) = 0 then I(S;X) + I(S;Y) ⇐ I(S;X,Y)

Can you find a counterexample, or prove this and teach me your proof?

Someone showed me a simple analytic proof. I am still interested in seeing different ways people might prove this though.

[jessicata]

$$I(S;X,Y)=H\left(S\right)+H(X,Y)-H(S,X,Y)=H\left(S\right)+H\left(X\right)+H\left(Y\right)-H(S,X,Y)$$

$$I(S;X)=H\left(S\right)+H\left(X\right)-H(S,X)$$

$$I(S;X,Y)-I(S;X)=H\left(Y\right)+H(S,X)-H(S,X,Y)=I(Y;S,X)\ge I(S;Y)$$

For a visualization, see information diagrams, and note that the central cell I(S; X; Y) must be non-positive (because I(S; X; Y) + I(X; Y | S) = I(X; Y) = 0).

[Miss_Figg]

We want to prove:

$$\int \int p_{xs}(x,s)\log \frac{p_{xs}(x,s)}{p_s\left(s\right)p_x\left(x\right)}dxds+\int \int p_{ys}(y,s)\log \frac{p_{ys}(y,s)}{p_s\left(s\right)p_y\left(y\right)}dyds\le \int \int \int p_{xys}(x,y,s)\log \frac{p_{xys}(x,y,s)}{p_s\left(s\right)p_{xy}(x,y)}dxdyds$$

This can be rewritten as:

$$\int \int \int p_{xys}(x,y,s)\log \frac{p_{sx}(s,x)}{p_s\left(s\right)p_x\left(x\right)}dxdyds+\int \int \int p_{xys}(x,y,s)\log \frac{p_{sy}(s,y)}{p_s\left(s\right)p_y\left(y\right)}dxdyds\le \int \int \int p_{xys}(x,y,s)\log \frac{p_{xys}(x,y,s)}{p_s\left(s\right)p_x\left(x\right)p_y\left(y\right)}dxdyds$$

After moving everything to the right hand side and simplifying, we get:

$$\int \int \int p_{xys}(x,y,s)\log \frac{p_{xys}(x,y,s)p_s\left(s\right)}{p_{xs}(x,s)p_{ys}(y,s)}dxdyds\ge 0$$

Now if we just prove that $q(x,y,s)=\frac{p_{xs}(x,s)p_{ys}(y,s)}{p_s\left(s\right)}$ is a probability distribution, then the left hand side is $KL\left(p_{xys}\right(x,y,s),q)$ , and Kullback-Leibler divergence is always nonnegative.

Ok, q is obviously nonnegative, and its integral equals 1:

$$\int \int \int \frac{p_{xs}(x,s)p_{ys}(y,s)}{p_s\left(s\right)}dxdyds=\int \frac{p_s\left(s\right)p_s\left(s\right)}{p_s\left(s\right)}ds=\int p_s\left(s\right)ds=1$$

Q.e.d.

[Jalex Stark]

Just for amusement, I think this theorem can fail when s, x, y represent subsystems of an entangled quantum state. (The most natural generalization of mutual information to this domain is sometimes negative.)