Maximization of Mutual Information

Question

Let $X\in\{0,1\}^d$ be a Boolean vector and $Y, Z\in\{0,1\}$ are Boolean variables. Assume that there is a joint distribution $\mathcal{D}$ over $Y, Z$ and we'd like to find a joint distribution $\mathcal{D}'$ over $X, Y, Z$ such that:

1. The marginal of $\mathcal{D}'$ on $Y, Z$ equals $\mathcal{D}$.

2. $X$ are independent of $Z$ under $\mathcal{D}'$, i.e., $I(X;Z) = 0$.

3. $I(X; Y)$ is maximized,

where $I(\cdot;\cdot)$ denotes the mutual information. For now I don't even know what is a nontrivial upper bound of $I(X;Y)$ given that $I(X;Z) = 0$? Furthermore, is it possible we can know the optimal distribution $\mathcal{D}'$ that achieves the upper bound?

My conjecture is that the upper bound of $I(X;Y)$ should have something to do with the correlation (coupling?) between $Y$ and $Z$, so ideally it should contain something related to that.

Answer 1

We have the following series of inequalities: \begin{align} I(X;Y) & \le I(X;Y,Z) \\ & = I(X;Z) + I(X;Y|Z) \\ & = I(X;Y|Z) \\ & = I(X,Z;Y) - I(Y;Z) \\ & \le H(Y) - I(Y;Z) \\ & \le 1 \text{ bit} - I(Y;Z) , \end{align} where in the third line we've used that $I(X;Z)=0$.

Answer 2

I start with the bound $$1\geq H(Y)=I(X; Y)+I(Y; Z|X)$$ $$I(X; Y)\leq1-I(Y; Z|X)\leq1$$ Now it is obvious that $Z\perp Y, X$ and $Y=X_1$ uniformly distributed over $\{0, 1\}$ does the job

Answer 3

As stated, the problem is rather trivial, unless I'm misunderstanding something.

If the relation between $Y,Z$ is arbitrary, and we want to maximize $I(X;Y)$ then the condition $I(X;Z) = 0$ adds nothing.

Just maximize (without constraints) $I(X;Y)$. Using bits:

$$I(X;Y) \le H(Y) - H(Y|X) \le 1$$

This bound is achieved if $H(Y) = 1$ (fair coin) and $H(Y |X)=0$ ; the latter can be attained in several ways, it's enough that $Y$ is a function of $X$, for example $Y=X_1$ and the other components arbitrary.