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$?
 A: 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.
A: 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$.
A: This proof is essentially the same as the proof by becko, up to further simplifications.

The original Bayesian network is
$$V\leftarrow Y\to X \to U.$$
By comparing $v$-structures (immoralities) we see that this Bayesian network is Markov equivalent to the Markov chain
$$V\to Y\to X\to U.$$
From this, the inequality $\mathrm{MI}(V, U) \le \mathrm{MI}(X; Y)$ follows easily – the Markov chain can be only as strong as its strongest link.
