# Maximization of Mutual Information

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.

• Oct 18 '19 at 6:13

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$$.

• Wow thanks a lot! That's indeed a fantastic answer. Based on your idea I think may be we can slightly simplify the first part of the proof as follows: $I(X; Y, Z) = I(X; Z) + I(X;Y | Z) = I(X; Y | Z) = I(X, Z; Y) - I(Z; Y)$, where the second equality follows from the assumption that $X$ is independent of $Z$? Oct 21 '19 at 3:24
• You're right, that's even simpler. Would you like me to update my answer with this derivation? Oct 21 '19 at 5:58

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

• Thanks for the answer, and sorry for the confusion here: I've edited my original question to clarify it. Here we have a constraint on the joint distribution between $Y, Z$ which is given and fixed. The marginal on $Y, Z$ of the optimal joint distribution should be consistent with this given distribution. Oct 17 '19 at 19:23

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.

• Thanks for the answer, and sorry for the confusion here: I've edited my original question to clarify it. Here we have a constraint on the joint distribution between $Y, Z$ which is given and fixed. The marginal on $Y, Z$ of the joint distribution should be consistent with this given distribution. Oct 17 '19 at 19:22