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

ronny-fernandez

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

post by Ronny Fernandez (ronny-fernandez) · 2019-07-08T02:51:28.221Z · LW · GW · 1 comment

This is a question post.

  Answers
    12 jessicata
    3 Miss_Figg
None
1 comment

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.

Answers

answer by jessicata · 2019-07-08T07:46:20.903Z · LW(p) · GW(p)

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

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

$I (S; X, Y) - I (S; X) = H (Y) + H (S, X) - H (S, X, Y) = I (Y; S, X) \geq 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).

answer by Miss_Figg · 2019-07-08T15:39:36.282Z · LW(p) · GW(p)

We want to prove:

\int \int p_{x s} (x, s) log \frac{p_{x s} (x, s)}{p_{s} (s) p_{x} (x)} d x d s + \int \int p_{y s} (y, s) log \frac{p_{y s} (y, s)}{p_{s} (s) p_{y} (y)} d y d s \leq \int \int \int p_{x y s} (x, y, s) log \frac{p_{x y s} (x, y, s)}{p_{s} (s) p_{x y} (x, y)} d x d y d s

This can be rewritten as:

\int \int \int p_{x y s} (x, y, s) log \frac{p_{s x} (s, x)}{p_{s} (s) p_{x} (x)} d x d y d s + \int \int \int p_{x y s} (x, y, s) log \frac{p_{s y} (s, y)}{p_{s} (s) p_{y} (y)} d x d y d s \leq \int \int \int p_{x y s} (x, y, s) log \frac{p_{x y s} (x, y, s)}{p_{s} (s) p_{x} (x) p_{y} (y)} d x d y d s

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

\int \int \int p_{x y s} (x, y, s) log \frac{p_{x y s} (x, y, s) p_{s} (s)}{p_{x s} (x, s) p_{y s} (y, s)} d x d y d s \geq 0

Now if we just prove that $q (x, y, s) = \frac{p_{x s} (x, s) p_{y s} (y, s)}{p_{s} (s)}$ is a probability distribution, then the left hand side is $K L (p_{x y s} (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_{x s} (x, s) p_{y s} (y, s)}{p_{s} (s)} d x d y d s = \int \frac{p_{s} (s) p_{s} (s)}{p_{s} (s)} d s = \int p_{s} (s) d s = 1

Q.e.d.

1 comment

Comments sorted by top scores.

comment by Jalex Stark (jalex-stark-1) · 2019-07-08T12:38:13.242Z · LW(p) · GW(p)

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.)

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

Contents

Answers

1 comment