<p>The maximum of <span class="math-container">$I(X:Y)$</span> in your problem is <span class="math-container">$$H(Y) - H(Z) \cdot \bigg|\Pr[Y = 0|Z = 0] - \Pr[Y = 0|Z = 1] \bigg|. $$</span></p>

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

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

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

<p>Note that in this example <span class="math-container">$Y$</span> is a function of <span class="math-container">$X$</span> and <span class="math-container">$Z$</span>.
First, let me show that the maximum in your problem is indeed attained when  <span class="math-container">$Y$</span> is a function of <span class="math-container">$X$</span> and <span class="math-container">$Z$</span>.</p>

<p><strong>Lemma.</strong> Assume that <span class="math-container">$X, Y, Z$</span> are 3 jointly distributed random variables satisfying <span class="math-container">$(Y,Z) \sim\mathcal{D}$</span> and <span class="math-container">$I(X:Z) = 0$</span>.Then there are 3 jointly distributed random variables <span class="math-container">$X^\prime, Y^\prime, Z^\prime$</span> such that <span class="math-container">$(Y^\prime, Z^\prime)\sim\mathcal{D}$</span>, <span class="math-container">$I(X^\prime:Z^\prime) = 0$</span>, <span class="math-container">$I(X^\prime:Y^\prime) \ge I(X:Y)$</span> and <span class="math-container">$Y^\prime$</span> is a function of <span class="math-container">$X^\prime$</span> and <span class="math-container">$Z^\prime$</span>.</p>

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

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

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

CC BY-SA 4.0
2019-10-27T01:21:39.930Z
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.
Han Zhao
CC BY-SA 4.0
2019-10-27T09:26:16.217Z
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)$.
Sasha Kozachinskiy
CC BY-SA 4.0
2019-10-27T16:10:14.490Z
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?
Han Zhao
CC BY-SA 4.0
2019-10-28T07:54:36.777Z
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$.
Sasha Kozachinskiy
CC BY-SA 4.0
2019-10-28T12:34:59.683Z
Thanks a lot!!!
Han Zhao
CC BY-SA 4.0
2019-10-21T19:32:57.983Z
2019-10-21T19:32:57.983Z
Sasha Kozachinskiy
<p>Let <span class="math-container">$X\in\{0,1\}^d$</span> be a Boolean vector and <span class="math-container">$Y, Z\in\{0,1\}$</span> are Boolean variables. Assume that there is a joint distribution <span class="math-container">$\mathcal{D}$</span> over <span class="math-container">$Y, Z$</span> and we'd like to find a joint distribution <span class="math-container">$\mathcal{D}'$</span> over <span class="math-container">$X, Y, Z$</span> such that:</p>

<p>1). The marginal of <span class="math-container">$\mathcal{D}'$</span> on <span class="math-container">$Y, Z$</span> equals <span class="math-container">$\mathcal{D}$</span>.</p>

<p>2). <span class="math-container">$X$</span> are independent of <span class="math-container">$Z$</span> under <span class="math-container">$\mathcal{D}'$</span>, i.e., <span class="math-container">$I(X;Z) = 0$</span>.</p>

<p>3). <span class="math-container">$I(X; Y)$</span> is maximized,</p>

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

<p>My conjecture is that the upper bound of <span class="math-container">$I(X;Y)$</span> should have something to do with the correlation (coupling?) between <span class="math-container">$Y$</span> and <span class="math-container">$Z$</span>, so ideally it should contain something related to that.   </p>

CC BY-SA 4.0
2019-10-17T17:50:26.583Z
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.
Peter Shor 
CC BY-SA 4.0
2019-10-17T19:12:56.510Z
@PeterShor Yes that's exactly what I mean, and thanks a lot for the clarification! Will edit the question accordingly.
Han Zhao
CC BY-SA 4.0
2019-10-17T19:35:04.817Z
Much more comprehensible now! Interesting question.
Peter Shor 
CC BY-SA 4.0
2019-10-18T06:12:44.617Z
X-posted: https://math.stackexchange.com/q/3397888/339790
Rodrigo de Azevedo
<pr.probability><boolean-functions><it.information-theory>
Maximization of Mutual Information
Han Zhao
# Maximization of Mutual Information

(Asked by: username_0 on 2019-10-17)

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.

**Tags:** pr.probability, boolean-functions, it.information-theory

> **Comments:**
> **username_1**: 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.  
> **username_0**: @PeterShor Yes that's exactly what I mean, and thanks a lot for the clarification! Will edit the question accordingly.  
> **username_1**: Much more comprehensible now! Interesting question.  
> **username_2**: X-posted: https://math.stackexchange.com/q/3397888/339790  

---

## 1 answers

### Answer by username_3 on 2019-10-21. Score: 3 | Accepted answer

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

> **Comments:**
> **username_0**: 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.  
> **username_3**: 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)$.  
> **username_0**: 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?  
> **username_3**: 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$.  
> **username_0**: Thanks a lot!!!  

---

