Markov chains' mutual information

Question

If we have the Markov chain $W \to X \to Y \to Z$, how to compare $I(X;Y)+I(W;Z)$ and $I(X;Z)+I(W;Y)$?

Answer 1

This is problem 4.33 in Cover and Thomas texbook. There are many solutions. Let me change the letters for legibility : $A \to B \to C \to D$

Then $$\begin{align} d &= I(B;C) + I (A;D) - I(B;D)-I(A;C)\\ &= H(B,D) + H(A,C) - H(B,C) - H(A,D)\\ &= H(D \mid B) -H(C \mid B) + H(C \mid A) - H(D \mid A) \\ &= H(D \mid BA) - H(D \mid A) + H(C \mid A) -H(C \mid BA) \\ &= I(C;B \mid A) - I(D;B \mid A) \end{align} $$

where in the fourth line we've used the Markov property. Now, conditioned on $A$, the variables $B\to C \to D$ form also a Markov chain. And by a well known (and intuitive, and much easier to prove) property, the mutual information among the farthest variables is less or equal than any of the others, that is $I(C;B \mid A) \ge I(D;B \mid A)$.

Hence $d \ge 0$.