4
$\begingroup$

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.

$\endgroup$
  • 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$ – Peter Shor Oct 17 '19 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 '19 at 19:12
  • 1
    $\begingroup$ Much more comprehensible now! Interesting question. $\endgroup$ – Peter Shor Oct 17 '19 at 19:35
  • $\begingroup$ X-posted: math.stackexchange.com/q/3397888/339790 $\endgroup$ – Rodrigo de Azevedo Oct 18 '19 at 6:12
3
$\begingroup$

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

$\endgroup$
  • $\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 '19 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$ – Sasha Kozachinskiy Oct 27 '19 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 '19 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$ – Sasha Kozachinskiy Oct 28 '19 at 7:54
  • $\begingroup$ Thanks a lot!!! $\endgroup$ – Han Zhao Oct 28 '19 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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