1

Let $x,y$ be stochastic variables and $p$ be a probability measure.

$I[X,Y] :=- \sum_{x,y} p(x,y)\ln{p(x,y)}$ with $p(x,y) := P(X=x, Y=y)$

I have to show that $I[X, Y] \le I[X]+I[Y]$

I mustn't assume that $X$ and $Y$ are independent. My problem is how to write $p(x,y)$ into $p(x)$ and $p(y)$.

Any tipps or ideas on how to separate the p(x,y) and show the inequality? Thanks in advance!

Conditional Entropy is less than entropy is similar, but it doesn't fully answer my question (their definition of $I$ is different: over there: $I[X,Y] = \sum_{x,y} p(x,y) \ln \frac{{p(x,y)}}{p(x)p(y)}$

Community
  • 1
DeltaChief
  • 955
  • I tried to write $p(x,y)=p(x)p(y \mid x)$ but since $p(y \mid x)$ is definded via $p(x,y)/p(x)$ that doesn't bring me anywhere – DeltaChief Dec 17 '16 at 09:51
  • Do you know the chain rule for entropy? This is a direct consequence of that, and the fact that conditioning reduces entropy. – Theoretical Economist Dec 17 '16 at 10:47
  • 1
    Starting from the formula which you say "does not fully answer" your question, note that $$\sum_{x,y}p(x,y)\ln\frac{p(x,y)}{p(x)p(y)}$$ is $$\sum_{x,y}p(x,y)\ln p(x,y)-\sum_x\left(\sum_yp(x,y)\right)\ln p(x)-\sum_y\left(\sum_xp(x,y)\right)\ln p(y)$$ which is $$\sum_{x,y}p(x,y)\ln p(x,y)-\sum_xp(x)\ln p(x)-\sum_yp(y)\ln p(y)$$ hence, in the end, this formula does fully answer your question. – Did Dec 17 '16 at 10:55
  • ah, ok thanks a lot! – DeltaChief Dec 17 '16 at 11:04

1 Answers1

-1

By the chain rule for entropy, $$ I[X,Y] = I[X] + I[Y|X] $$

Conditioning reduces entropy, so $$ I[Y|X] \leq I[Y] $$

Thus, $$ I[X,Y] \leq I[X] + I[Y] $$

Community
  • 1
Theoretical Economist
  • 6,472
  • This is considering as known an equivalent version of the desired result, is it not? – Did Dec 17 '16 at 10:57
  • @Did Ah, yes. I meant to include a link to the other post about conditioning in my answer. – Theoretical Economist Dec 17 '16 at 11:02
  • Link or no link, I find odd to state that A holds because B holds when A and B are basically different formulations of the same result and when there is no reason to expect that B would be well known while A would not. In the present case, if I was forced to decide which came first of the egg and the hen, I might elect A as being the base result and B as being a consequence of A, not the opposite as your answer posits. – Did Dec 17 '16 at 11:07
  • @Did In general, sure. However, if I am asked to demonstrate A, and the asker acknowledges an equivalent statement B without recognising the equivalence, pointing out that they are equivalent is an answer, is it not? – Theoretical Economist Dec 17 '16 at 11:13
  • I missed where the OP ackowledged B. Actually they rejected B as being irrelevant to A, didn't they? – Did Dec 17 '16 at 11:16
  • I missed where the OP rejected B as being irrelevant to A. Actually they admitted that B was similar to A, didn't they? – Theoretical Economist Dec 17 '16 at 11:30
  • On a less facetious note, I am happy to delete my answer if it is actively unhelpful. – Theoretical Economist Dec 17 '16 at 11:31
  • Quote: "Conditional Entropy is less than entropy (the question) is similar, but it doesn't fully answer my question". – Did Dec 17 '16 at 11:41