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

• Your question is confusing. Is it the following: given a joint distribution on $Y,Z$, what is the distribution on $X,Y,Z$ with this marginal that maximizes $I(X;Y)$ and makes $I(X;Z) = 0$? Because if you don't have a constraint on the joint distribution of $Y,Z$, you can just maximize $I(X;Y)$ and make $Z$ independent of both of them. Oct 17 '19 at 17:50
• @PeterShor Yes that's exactly what I mean, and thanks a lot for the clarification! Will edit the question accordingly. Oct 17 '19 at 19:12
• Much more comprehensible now! Interesting question. Oct 17 '19 at 19:35
• Oct 18 '19 at 6:12

The maximum of $$I(X:Y)$$ in your problem is $$H(Y) - H(Z) \cdot \bigg|\Pr[Y = 0|Z = 0] - \Pr[Y = 0|Z = 1] \bigg|.$$

Let me first demonstrate an example for which this maximum is attained. Denote $$\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1]$$. Sample $$X$$ uniformly at random from $$[0, 1]$$ and then sample $$Z$$ independently from $$X$$ according to the corresponding marginal distribution of $$\mathcal{D}$$. Next, define: $$Y = \begin{cases} 0 & \mbox{if X\le\alpha, Z = 0 or X\le \beta, Z = 1},\\ 1 &\mbox{otherwise.}\end{cases}$$

So we have 3 jointly distributed random variables $$X, Y, Z$$. It is clear that $$(Y, Z)\sim\mathcal{D}$$ and $$I(X:Z) = 0$$. Let's compute $$I(X:Y)$$. As $$I(X:Y) = H(Y) - H(Y|X)$$, we only have to deal with $$H(Y|X)$$. Assume WLOG that $$\alpha \le \beta$$. Then if $$X\le \alpha$$ or $$X > \beta$$, then $$Y$$ is constant. If $$\alpha < X \le \beta$$, then $$Y = 1- Z$$. I.e., the conditional distribution of $$Y$$ given $$X = r\in (\alpha, \beta]$$ is equal to the conditional distrbitution of $$1 - Z$$ given $$X = r\in(\alpha, \beta]$$. But $$Z$$ is independent of $$X$$, which means that this conditional distribution is just the distribution of $$Z$$. In other words, $$H(Y|X) = \Pr[\alpha < X \le \beta] \cdot H(Z) = (\beta - \alpha) H(Z)$$, as required.

There is a technical problem that $$X$$ takes infinitely many values. However, we can assume that $$X$$ takes just $$3$$ values with probabilities $$\alpha, \beta - \alpha, 1 - \beta$$. I.e., we partition $$[0, 1]$$ into $$3$$ intervals $$[0, \alpha], (\alpha, \beta], (\beta, 1]$$, take a random point $$P$$ in $$[0, 1]$$ and let $$X$$ be the interval of the partition containing $$P$$. The rest of the argument works similarly.

Note that in this example $$Y$$ is a function of $$X$$ and $$Z$$. First, let me show that the maximum in your problem is indeed attained when $$Y$$ is a function of $$X$$ and $$Z$$.

Lemma. Assume that $$X, Y, Z$$ are 3 jointly distributed random variables satisfying $$(Y,Z) \sim\mathcal{D}$$ and $$I(X:Z) = 0$$.Then there are 3 jointly distributed random variables $$X^\prime, Y^\prime, Z^\prime$$ such that $$(Y^\prime, Z^\prime)\sim\mathcal{D}$$, $$I(X^\prime:Z^\prime) = 0$$, $$I(X^\prime:Y^\prime) \ge I(X:Y)$$ and $$Y^\prime$$ is a function of $$X^\prime$$ and $$Z^\prime$$.

Proof. Sample $$(X_1, Z^\prime)$$ according to the distribution of $$(X, Z)$$ and then sample $$P$$ uniformly from $$[0, 1]$$ and independently from $$(X_1, Z^\prime)$$. Set $$X^\prime = (X_1, P)$$. Let $$x$$ be the value of $$X_1$$ and $$z$$ be the value of $$Z^\prime$$. Define $$Y^\prime = \begin{cases} 0 & \mbox{if P \le \Pr[Y = 0| X = x, Z = z]},\\ 1 &\mbox{otherwise.}\end{cases}.$$ First of all, $$X^\prime$$ and $$Z^\prime$$ are independent and $$Y^\prime$$ is a function of $$X^\prime$$ and $$Z^\prime$$ by construction. Further, it is clear that the distribution of $$(X_1, Y^\prime, Z^\prime)$$ is identical to the distribution of $$(X, Y, Z)$$. In particular this means that $$(Y^\prime, Z^\prime) \sim\mathcal{D}$$. Moreover, this gives us the following $$I(X^\prime:Y^\prime) = I(X_1, P:Y^\prime) \ge I(X_1:Y^\prime) = I(X:Y)$$ and the lemma is proved. Once again, there is a technical problem with the fact that $$P$$ takes infinitely many values, but it is clear that $$P$$ can be discretized'' as above. $$\blacksquare$$

To finish the argument we have to show that for any $$3$$ jointly distributed random variables $$X, Y, Z$$ such that $$(Y, Z)\sim\mathcal{D}, I(X:Z) = 0$$ and $$Y = f(X, Z)$$ for some function $$f$$ it holds that: $$I(X:Y) \le H(Y) - H(Z) \cdot |\beta - \alpha|,$$ where $$\alpha = \Pr[Y = 0|Z = 0], \beta = \Pr[Y = 0|Z = 1].$$

Let $$W$$ be the set of values of $$X$$. Next, define: $$W_0 = \{x\in W \mid f(x, 0) = 0\}, \qquad W_1 = \{x\in W \mid f(x, 1) = 0\}.$$ Note that $$\alpha = \Pr[f(X, Z) = 0|Z = 0] = \Pr[f(X, 0) = 0|Z = 0] = \Pr[f(X, 0) = 0] = \Pr[X\in W_0]$$ (in the third equality we use the fact that $$Z$$ and $$X$$ are independent). Similarly, $$\beta = \Pr[X\in W_1]$$. Now, assume WLOG that $$\alpha \le \beta$$. Note that $$\Pr[X\in W_1\setminus W_0] \ge \beta - \alpha$$. On the other hand, $$X\in W_1\setminus W_0$$ implies that $$Y = 1 - Z$$. Hence $$H(Y|X) \ge (\beta - \alpha) H(Z)$$ and $$I(X:Y) = H(Y) - H(Y|X) \le H(Y) - H(Z) (\beta - \alpha).$$

• Hi Sasha, sorry for the late response and thanks so much for the detailed explanation and proof! If my understanding is correct, here basically the proof essentially implies that 2 bits, i.e., $d = 2$ is enough in order to achieve the optimal value? Furthermore, in the last part of the proof, $Y$ is actually not a deterministic function of $(X, Z)$ but a randomized one since the generation process involves $P$ right? Here we only require that $P$ is independent of $(X, Z)$. Please correct me if I am wrong here. Oct 27 '19 at 1:21
• It seems that 2 bits are enough, right. As for your second questions, in the last part I definitely mean that $Y$ is a deterministic function of $(X, Z)$. The logic is as follows: we start with some $X, Y, Z$; then, roughly speaking, we add $P$ to $X$ so that now $Y$ is a deterministic function of $X, Z$. This can only increase $I(X:Y)$. Oct 27 '19 at 9:26
• Ah I see, yeah that makes sense! Sorry one last question, what's the underlying argument you used to claim that $H(Y|X) \geq (\beta - \alpha) H(Z)$? I understand that I can use the definition of conditional entropy to expand it, but it seems to me there is a simpler way to see this? Oct 27 '19 at 16:10
• Yes, I used the definition of conditional entropy -- for every $x\in W_1\setminus W_0$ the entropy of $Y|X = x$ equals the entropy of $Z$, and probability that $X\in W_1\setminus W_0$ is at least $\beta - \alpha$. Oct 28 '19 at 7:54
• Thanks a lot!!! Oct 28 '19 at 12:34