Suppose I have four random variables $X,Y,U,V$ following a distribution which factorizes in the form:

$$P(X,Y,U,V) = P(X,Y)P(U|X)P(V|Y)$$

I have the intuition that we should have an inequality of the form:

$$\mathrm{MI}(U;V) \leqslant \mathrm{MI}(X;Y)$$

where $\mathrm{MI}(X;Y)$ denotes the mutual information between $X$ and $Y$. But I can't prove it.

A particular case is when $\mathrm{MI} (X ; Y)=0$, in which case $U,V$ are also independent and $\mathrm{MI} (U ; V) =0$ as well.

In general, is there a way to understand the relation between $\mathrm{MI} (U ; V)$ and $\mathrm{MI} (X ; Y)$?

Note that this result would be a generalization of the data processing inequality, which can be obtained as a particular case of the above inequality by setting $U=X$.

I have an application where $\mathrm{MI}(X;Y)$ is much easier to compute than $\mathrm{MI}(U;V)$. And I would like to exploit this to draw some conclusions about $U;V$. For instance, under what conditions $\mathrm{MI}(U;V)=0$ implies $\mathrm{MI}(X;Y)=0$?


It might be easier to work with entropy.

Let's consider a simpler case, with 3 variables $A, B,C$ where $A$ and $C$ are conditionally independent given $B$.

If we can show that $\mathrm{MI}(A;C) \leq \mathrm{MI}(A;B)$, we can use that for your specific question.

Note that $\mathrm{MI}(A;C) = H(A, C) - H(A | C) - H(C | A)$.

One trick we will use a lot is that $\forall P, Q, R:H(P, Q | R) = H(Q | R) + H(P | Q, R)$ (even if $P, Q$ or $R$ consist of conjunctions of variables or are empty).

With this trick, we can rewrite: $$\begin{eqnarray} \mathrm{MI}(A;C) &=& \Big[H(A,B,C) - H(B|A,C) \Big] - \Big[H(A,B|C) - H(B|A,C)\Big]\\&&- \Big[H(B,C|A) - H(B|A,C)]\\ &=&H(A,B,C) + H(B|A,C) - H(A,B|C) - H(B,C|A) \end{eqnarray}$$ We can continue: $$\begin{eqnarray} \mathrm{MI}(A;C) &=& H(A,B,C) + H(B|A,C) - \Big[H(A|B,C) + H(B|C)\Big]\\ &&-\Big[H(C|B,A) + H(B|A)\Big]\\ \end{eqnarray}$$ Now, since $A$ and $C$ are conditionally independent, we have that $H(A|B,C) = H(A|B)$ (and the same goes for $H(C|A,B)$). $$\begin{eqnarray} \mathrm{MI}(A;C) &=& H(A,B,C) + H(B|A,C)\\ &&- \Big[H(A|B) + H(B|C) + H(C|B) + H(B|A)\Big] \end{eqnarray}$$ Now, using our trick again: $$\begin{eqnarray} \mathrm{MI}(A;C) &=& \Big[H(A, B) + H(C|B)\Big] + H(B|A,C)\\ &&- \Big[H(A|B) + H(B|C) + H(C|B) + H(B|A)\Big] \end{eqnarray}$$ Rearranging a bit: $$\begin{eqnarray} \mathrm{MI}(A;C) &=& \Big[H(A, B) - H(A|B) - H(B|A)\Big]\\ && + \Big[H(B|A,C) - H(B|C)]\\ &=& \mathrm{MI}(A;B) + H(B|A,C) - H(B|C) \end{eqnarray} $$ Now, note that $H(B|C) \geq H(B|A, C)$, and we get: $$\mathrm{MI}(A;C) \leq \mathrm{MI}(A;B)$$ and we are done.

We can now this rule for the actual question; to first show that $\mathrm{MI}(U;Y) \leq \mathrm{MI}(X;Y)$ and then to show that $\mathrm{MI}(U;V) \leq \mathrm{MI}(U;Y)$, and our proof is complete.

  • $\begingroup$ The first part of your answer is just proving the Data processing inequality, right? $\endgroup$ – becko Dec 18 '20 at 9:51
  • $\begingroup$ See my answer (which is just a summarized version of yours, after skipping the proof of the Data processing inequality). Do you have any ideas on how to answer the last part? Under what conditions $\mathrm{MI}(U;V)=0$ implies $\mathrm{MI}(X;Y)=0$? $\endgroup$ – becko Dec 18 '20 at 12:26
  • $\begingroup$ Ah yes, you are right. I did not recall that theorem, although it makes perfect sense. That would have made my answer quite a bit shorter indeed! $\endgroup$ – Robby the Belgian Dec 18 '20 at 15:24
  • $\begingroup$ As for the other question: in the DPE, equality holds if $A,C$ gives as much information about $B$ as $A$ does (so if $A$ and $B$ are conditionally independent given $C$). For your situation, that becomes that you could write your joint probability as $P(U,V)P(X|U)P(Y|V)$. $\endgroup$ – Robby the Belgian Dec 18 '20 at 15:30
  • $\begingroup$ That condition is stronger, in that it makes $\mathrm{MI}(U;V) = \mathrm{MI}(X;Y)$, right? $\endgroup$ – becko Dec 19 '20 at 15:28

The desired inequality can be obtained by two applications of the Data Processing Inequality (DPI).

First consider the Markov chain $Y\rightarrow X\rightarrow U$. Then the DPI implies that $\mathrm{MI}(U,Y)\le\mathrm{MI}(X,Y)$.

Next, rewrite the original factorization as:

$$P (x, y, u, v) = P (u) P (x|u) P (y|x) P (v|y)$$

In this form, we see that we also have the Markov chain $U\rightarrow X\rightarrow Y\rightarrow V$. For this chain, the DPI implies that $\mathrm{MI}(U,V) \le \mathrm{MI}(U,Y)$.

Combining the two inequalities, we obtain the desired result:

$$\mathrm{MI}(U,V) \le \mathrm{MI}(X,Y)$$

This answer is based on @Robby's answer above.

However, I still have trouble to find conditions under which $\mathrm{MI}(U,V)=0$ imply that $\mathrm{MI}(X,Y)=0$.


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.