# A generalization of the data processing inequality

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.

• The first part of your answer is just proving the Data processing inequality, right? – becko Dec 18 '20 at 9:51
• 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$? – becko Dec 18 '20 at 12:26
• 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! – Robby the Belgian Dec 18 '20 at 15:24
• 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)$. – Robby the Belgian Dec 18 '20 at 15:30
• That condition is stronger, in that it makes $\mathrm{MI}(U;V) = \mathrm{MI}(X;Y)$, right? – 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)$$

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