1
$\begingroup$

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

$\endgroup$
3
  • $\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
    Jan 1, 2020 at 12:05
  • $\begingroup$ We exclude such trivial cases. $\endgroup$ Jan 2, 2020 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$ Feb 22, 2020 at 14:26

1 Answer 1

1
$\begingroup$

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

$\endgroup$

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.