Encoding a random variable with mutual information constraints

Question

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

Answer 1

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