0
$\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
0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$? $\endgroup$
    – Han Zhao
    Oct 21 '19 at 3:24
  • $\begingroup$ You're right, that's even simpler. Would you like me to update my answer with this derivation? $\endgroup$
    – Artemy
    Oct 21 '19 at 5:58
  • $\begingroup$ Yeah please go ahead, thanks! $\endgroup$
    – Han Zhao
    Oct 21 '19 at 6:24
-1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Han Zhao
    Oct 17 '19 at 19:23
-1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Han Zhao
    Oct 17 '19 at 19:22

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.