2
$\begingroup$

Suppose A, B and C are random variables. Given that the mutual information between A and B is very large and also the mutual information between B and C is very large, could we conclude that the mutual information between A and C is also large? In other words, if we know the mutual information between A and B and the mutual information between B and C, what could we say about the mutual information between A and C?

Thanks,

$\endgroup$
  • $\begingroup$ Imagine H(B|A)=H(C|B)=0, i.e. maximum mutual information between A and B, and between C and B. Now I claim the mutual information between A and C is low. To refute this claim, I could say given A, I know B because H(B|A)=0. Similarly, given B, I know C because H(C|B)=0. So by knowing A, I could find B and subsequently I could find C. This implies a large mutual information between A and C. This was an intuitive proof. I cannot prove it mathematically. $\endgroup$ – Seyed Sep 10 '13 at 17:01
  • $\begingroup$ I see. Then the last sentence of your post is misleading. $\endgroup$ – Did Sep 10 '13 at 17:03
  • $\begingroup$ Thanks Did. In my comment, I assume maximum mutual information. If the mutual information between A and B and between B and C is not large, then I cannot prove the transitivity even intuitively. That is why I preferred to ask a more general question and add the last sentence. $\endgroup$ – Seyed Sep 10 '13 at 17:06
  • $\begingroup$ Intuitively, when viewing it as the "intersection" of sets; you will only get lower bounds, say something like $$I(A;C) \geq I(A;B) + I(B;C) - 1$$ With $I(A;B), I(B;C) \geq c$ you can only reach $I(A;C) \geq 2c - 1 < c$ for $c < 1$ $\endgroup$ – AlexR Sep 10 '13 at 17:26
  • $\begingroup$ Arguing based on set theoretic intuition is not always true. Just consider the relation between $I(A;B)$ and $I(A;B|C)$. There is no definite relation between them unlike what set theoretical intuition might suggest. $\endgroup$ – Arash Sep 10 '13 at 17:29
1
$\begingroup$

The relation between $I(A;C)$ and $I(A;B)$,$I(B;C)$ depends on the joint probability distribution of $A,B,C$. For instance if you have the Markov relation that $P(A|BC)=P(A|B)$, then this will imply that: $$ I(A;B)=I(A;BC)\geq I(A;C). $$ Similarly $$ I(B;C)=I(BA;C)\geq I(A;C). $$ Therefore $$ \min\left(I(A;B),I(B;C)\right)\geq I(A;C). $$ On the other hand if you assume different Markov relation as $P(A|BC)=P(A|C)$, you get: $$ I(A;C)=I(A;BC)\geq I(A;B). $$ So there is no specific relation between mutual informations if you do not know their joint distribution.

$\endgroup$
  • $\begingroup$ I see. So even knowing that for example H(B|A)=H(C|B)=0 does not help? $\endgroup$ – Seyed Sep 10 '13 at 17:41
  • $\begingroup$ This is different. $H(B|A)=0$ means $B=f(A)$ and similarly $C=g(B)=g(f(A))$ so $H(C|A)=0$ too. $\endgroup$ – Arash Sep 10 '13 at 17:43
  • $\begingroup$ Based on what you said, if H(B|A)<c and H(C|B)<c, I cannot make any conclusion on H(C|A), right? $\endgroup$ – Seyed Sep 10 '13 at 17:52
  • $\begingroup$ The conditional entropy is different from mutual information. For conditional entropy you can have: $H(C|A)\leq H(BC|A)=H(B|A)+H(C|BA)\leq H(B|A)+H(C|B)\leq 2c$. But saying that mutual information is very large does not say very much about the conditional entropy. $\endgroup$ – Arash Sep 10 '13 at 17:59
  • $\begingroup$ If I(A;B)=H(B)-H(B|A) is very large, we can say H(B|A) is close to 0. So I think knowing the mutual information is very large or very small, we can infer something about the conditional entropy as well. $\endgroup$ – Seyed Sep 10 '13 at 18:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.