# Encoding a random variable with mutual information constraints

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

• 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! – Shahrooz Janbaz Jan 1 at 12:05
• We exclude such trivial cases. – Saber Saleh Jan 2 at 7:30
• 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) ? – 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}$$.