For random variables X and Y, is there any one-bit variable $Z=f(Y)$, such that $I(X;Z)\geq I(X;Y)/B$ where $B$ is the number of bits to represent $Y$?

  • $\begingroup$ If X and Y are independent, finding Z is trivial. I think you assume that X and Y are not independent, OK? Also, if X is identical to Y, or X=g(Y), the answer is clear! $\endgroup$ – Shahrooz Janbaz Jan 1 at 12:05
  • $\begingroup$ We exclude such trivial cases. $\endgroup$ – Saber Saleh Jan 2 at 7:30
  • $\begingroup$ Your definition of B is ambiguous. For instance, if Y can have 3 different values, is B=2 or B=ln(3) or B=H(Y) ? $\endgroup$ – Arnaud Mégret Feb 22 at 14:26

No. The problem of choosing $Z$ with a rate constraint to maximize $I(X;Z)$ is called the information bottleneck problem and is characterized by the solution to an integral equation.

There is no limit to the complexity of how the information about $X$ appears in $Y$.

Consider that after observing $Y=y$ then $X$ is characterized by the conditional distribution $P_{X|Y=y}$. To preserve information about $X$ then $Z$ must describe which of these conditional distributions appears. But there is no limit to the amount of complexity in this weighted collection of conditional distributions $(P_{Y=y}\cdot P_{X|Y=y})_y$.

For a specific example, consider $(X,Y)$ with the joint-distribution:

\begin{equation} P_{X,Y} = \frac{1}{6} \begin{bmatrix} 0,1,1\\ 1,0,1\\ 1,1,0 \end{bmatrix}. \end{equation}

Then one can check any nontrivial $Z$ as you described gives the same $H(Z),\ H(X,Z)$. One can also check $I(X;Z)=\log_2 3-\frac{4}{3} < I(X;Y)/H(Y)=1-\frac{1}{\log_2 3}$.

| cite | improve this answer | |

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.