2
$\begingroup$

So I've been trying to figure this out since I saw it quoted in a paper. Suppose $y$ and $z$ are two independent variables. Is it true then that $I(x;y) + I(x;z) \leq I(x:y,z)$? My intuition is that since $y $ and $z$ are independent, the information gain from taking them singly (in sequence) or together is the same.

$\endgroup$

1 Answer 1

2
$\begingroup$

The proof is straightforward from computation. $$\begin{align}&I(x;y)+I(x;z)-I(x;y,z)\\ =&H(y)-H(y|x)+H(z)-H(z|x)-(H(y,z)-H(y,z|x))\\ =&H(y)+H(z)-H(y,z)+H(y,z|x)-H(y|x)-H(z|x)\\ =&I(y;z)-I(y;z|x)\\ \leq&0\end{align}$$ The last inequality comes from the independence of $y$ and $z$ which results $I(y;z)=0$. Intuitively thinking, though $y$ and $z$ are independent, if $x$ is a function of $y,z$, we may indeed obtain connections between them. For example, suppose $x,y,z$ are binary random variables and $x=y+z$ and given $x=1$, we can find connection between $y,z$, that is $y=1+z$.

$\endgroup$
9
  • $\begingroup$ You and the OP are both familiar with notations like $I(x;y)$, $H(y\mid x)$ etc. I am not. Can you give me a (very) short college on this in the form of a comment? I am familiar with probabilities. $\endgroup$
    – drhab
    Dec 2, 2013 at 8:53
  • $\begingroup$ @drhab: See this. $\endgroup$ Dec 2, 2013 at 8:54
  • $\begingroup$ @StefanHansen Clicking on the link in your comment sends me to this page (try it yourself). So I think something is wrong with it. $\endgroup$
    – drhab
    Dec 2, 2013 at 8:57
  • $\begingroup$ @drhab: Oops, edited the link. $\endgroup$ Dec 2, 2013 at 8:58
  • 1
    $\begingroup$ @drhab Let me explain these notions in an intuitive way. These notions all go around a core concept called information. This is quite important. For example, he entropy $H(x)$ measures the uncertainty of random variable $X$. That means $X$ contains $H(X)$ that much information. And conditional entropy $H(X|Y)$ contains information of $X$ if we have already known $Y$. Then of course the information has been reduced. Similarly, $I(X;Y)$ measure those information that we can obtain from both $X$ and $Y$. This diagram shows perfect what I said. $\endgroup$
    – Shuchang
    Dec 2, 2013 at 9:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .