# Is mutual information transitive?

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,

• 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. – Seyed Sep 10 '13 at 17:01
• I see. Then the last sentence of your post is misleading. – Did Sep 10 '13 at 17:03
• 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. – Seyed Sep 10 '13 at 17:06
• 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$ – AlexR Sep 10 '13 at 17:26
• 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. – Arash Sep 10 '13 at 17:29

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.
• 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. – Arash Sep 10 '13 at 17:43
• 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. – Arash Sep 10 '13 at 17:59