Mutual information decrease with coarse-graining

92 Views Asked by At

Let $X,A,Y,B,C,D$ be random binary variables. $D$ is independent from $X,A,C$ and $C$ is independent from $Y,B,D$.

Is it true that:

If $I(Y:B|D=0)\leq \epsilon$ then $I(X\oplus Y:A\oplus B|C=0,D=0)\leq \epsilon \times I(X:A|C=0)$.

This result seems intuitive and I managed to show it for $\epsilon=0$ and $\epsilon=1$, but maybe in the general case we should have a function $f(\epsilon)$ on the right hand side and not simply $\epsilon$. If the result is true, how would you show it using the data processing inequality, the chain rule etc.?

Thanks for your help.

1

There are 1 best solutions below

2
On

First, let's simplify by noting that the variables $D$ and $C$ are unnecessary in your question. Indeed, since $X,A,C$ are independent from $D$, $I(X:A|C=0)=I(X:A|C=0,D=0)$. Similarly, since $Y,B,D$ are independent from $C$, $I(Y:B|D=0)=I(Y:B|C=0,D=0)$. So, we can just consider your problem conditioned on $C=D=0$.

Thus, your question can be rephrased as: If $X,Y,A,B$ are binary random variables, does $I(Y:B)\leq \epsilon$ imply $I(X\oplus Y:A\oplus B)\leq f(\epsilon) \times I(X:A)$?

Without any further constraints, the answer is no. To see this, let $X,A$ be independent Bernoulli(1/2), let $Y=0$ and let $B=X \oplus A$. Then $I(X:A)=0$, but $I(X\oplus Y:A\oplus B)=I(X:X)=1$.