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.

  • 1
    $\begingroup$ 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. $\endgroup$ Oct 17, 2019 at 17:50
  • 1
    $\begingroup$ @PeterShor Yes that's exactly what I mean, and thanks a lot for the clarification! Will edit the question accordingly. $\endgroup$
    – Han Zhao
    Oct 17, 2019 at 19:12
  • 1
    $\begingroup$ Much more comprehensible now! Interesting question. $\endgroup$ Oct 17, 2019 at 19:35
  • $\begingroup$ X-posted: math.stackexchange.com/q/3397888/339790 $\endgroup$ Oct 18, 2019 at 6:12

1 Answer 1


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

  • $\begingroup$ 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. $\endgroup$
    – Han Zhao
    Oct 27, 2019 at 1:21
  • $\begingroup$ 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)$. $\endgroup$ Oct 27, 2019 at 9:26
  • $\begingroup$ 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? $\endgroup$
    – Han Zhao
    Oct 27, 2019 at 16:10
  • $\begingroup$ 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$. $\endgroup$ Oct 28, 2019 at 7:54
  • $\begingroup$ Thanks a lot!!! $\endgroup$
    – Han Zhao
    Oct 28, 2019 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.