Given the discrete random variables $X,Y,$ and $Z=f(X,Y)$, where $f$ is some function, how can I show that: $$ H(Z) \leq H(X,Y) $$ With equality if the function $f$ is invertible?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
Let $W=(X,Y)$ such that $Z=f(W)$. Then, the mutual information between $W$ and $Z$ is: $$ I(W;Z) = H(Z) - H(Z|W) = H(W) - H(W|Z) $$ Since: $$ H(Z|W)=H(f(W)|W)=0 $$ Then: $$ H(Z) = H(W) - H(W|Z) $$ Since $H(W|Z)$ is non-negative, then: $$ H(Z) \leq H(W) $$ If $f$ is invertible, which means that $H(W|Z)=H(f^{-1}(Z)|Z)=0$, then: $$ H(Z) = H(W) $$
-
$\begingroup$ Does the equality also imply that $f$ is invertible? $\endgroup$ Commented Oct 27, 2023 at 8:19
-
$\begingroup$ @HoseinRahnama A modified version of the converse is true: consider any two random variables $X$ and $Y$ such that $X = f(Y)$ and $H(X) = H(Y)$. Because $X = f(Y)$, then $H(X\mid Y) = 0$. Also, because $H(X) = H(Y)$, then $H(Y \mid X ) = H(X \mid Y) = 0$. Because $H(Y \mid X) = 0$, then there exists some function $g$ such that $Y = g(X) = g(f(Y))$. This implies that $f$ has a left-inverse $g$, which implies that $f$ is injective. $\endgroup$– mhdadkCommented Oct 28, 2023 at 15:44
-
$\begingroup$ Actually, I’m not sure if the argument above holds, it may be the case that $g$ does not exist. The proof needs more work. $\endgroup$– mhdadkCommented Oct 28, 2023 at 16:44
-
$\begingroup$ I think that the argument in the answer follows by noting that $H(X|Y) = 0$ if and only if there is function $f$ such that $X = f(Y)$. $\endgroup$ Commented Oct 29, 2023 at 18:43