Comparing entropies $H((f(X,Y), g(X,Y)))$ and $H ((f(X,Y),g(X,Z)))$

Question

Let X,Y,Z be three independent uniform distributions on $\{0,1\}^n$; $f, g:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ be two boolean functions. Is it true that

$$H((f(X,Y), g(X,Y)))\leq H ((f(X,Y),g(X,Z)))$$

where $H(\cdot)$ represents the Shannon entropy

Answer 1

Let $X_1 = [X \ \ Y]$ and $X_2 = [X \ \ Z]$.

Then $$H(f(X_1),g(X_1)) = H(f(X_1)) + H(g(X_1)|f(X_1))\\ H(f(X_1),g(X_2)) = H(f(X_1)) + H(g(X_2)|f(X_1))$$

so

$$H(f(X_1),g(X_1))-H(f(X_1),g(X_2))= H(g(X_1)|f(X_1)) - H(g(X_2)|f(X_1)) \leq 0.$$

You can also view $f(X,Y),g(X,Z)$ as a version of $f(X,Y),g(X,Y)$ that has been passed through a channel with additional randomness. By data processing, the inequality follows.