# Maximization of information over set of non-injective functions (Equality)

Let $$X$$, $$Y$$, $$Z$$ be discrete random variables, with $$Y$$ and $$Z$$ independent. Does the following equality hold if $$Z$$ is independent also of $$X$$? $$\max_{f_{Y,Z}} \big\{ \ I(X; f_{Y,Z}(Y,Z)) \ \big\} = \max_{f_X, f_Y} \big \{ \ I(X; f_Y(Y), f_Z(Z)) \ \big \}$$ where the maximization is taken over all non-injective, deterministic functions.

P.S.: See this for the inequality version of the question.

No. Let $$Y,Z$$ be iid Bernoulli(1/2), and let $$X=Y+Z$$ mod 2, which induces pairwise independence. The only non-injective deterministic functions $$f_Y,f_Z$$ are constants, rendering the RHS zero. For the LHS, we can take $$f_{Y,Z}(Y,Z)$$ equal to the the binary AND of $$Y$$ and $$Z$$, which is not injective, and not independent of $$X$$. Hence, the LHS is something positive, showing there can be strict inequality.

• But is $X$ independent of $Z$? Sep 2, 2022 at 13:49
• Ups, I noticed that I have a typo in the question. Sep 2, 2022 at 13:49
• Sorry, for that. The second independence, the one highlighted in bold, should have been with $X$ and not again with $Y$. I corrected this point now. Sep 2, 2022 at 15:12
• My answer still works. X,Y,Z are pairwise independent in this construction.
– Tom
Sep 3, 2022 at 14:53

I think I might be able to provide a proof for a slightly modified version of the hypotheses, which would still be enough for the theorem that I am trying to prove.

Let $$F_1:=\{(y,z) \to f_1(y,z)\}$$ and $$F_2:= \{(y,z) \to (f_y(y),f_z(z))\}$$ where $$f_1$$ and $$f_2$$ are non-injective. This relaxes the hypothesis that $$f_y$$ and $$f_z$$ must also be separately non-injective. We then have $$\max_{F_1} \big\{ \ I(X; f_1(Y,Z)) \ \big\} = \max_{F_2} \big \{ \ I(X; f_2(Y,Z)) \ \big \}$$

Proof. Call $$f_1^* = \arg \max_{F_1} \big\{ \ I(X; f_1(Y,Z)) \ \big\}$$ and $$f_2^* = (f_y^*, f_z^*)= \arg \max_{F_2} \big\{ \ I(X; f_2(Y,Z)) \ \big\}$$. We have $$I(X; Y, Z) \stackrel{(a)}{\ge} I(X; f_1^*(Y,Z)) \stackrel{(b)}{\ge} I(X; f_2^*(Y,Z)) = I(X; f_y^*(Y), f_z^*(Y)) \stackrel{(c)}{\ge} I(X; Y, f_z^*) \stackrel{(d)}{=} I(X;Y)$$ where (a) follows from the data processing inequality, (b) from the fact that $$F_2 \subseteq F_1$$, (c) from the definition of $$f_2^*$$ and from the fact that $$(y, f_z^*(z)) \in F_2$$, and (d) from the fact that $$f_z^*(Z)$$ is independent of $$X$$ and $$Y$$. Because $$I(X;Y,Z) = I(X;Y)$$ we obtain $$I(X; f_1^*(Y,Z)) = I(X; f_2^*(Y,Z))$$. Is that correct?