Let $U$ be the uniform random variable over $n$-bit binary strings, and let $X$ be another random variable that is dependent on $U$ and ranges over $n$-bit binary strings.

Assuming $I(X;U) \le \epsilon$, can we find a tight lower bound on $H(X \oplus U)$? For instance, can we prove something like $H(X \oplus U) \ge n - \epsilon$?

P.S.: The mutual information and entropy are denoted by $I$ and $H$, and $\oplus$ denotes the XOR operator.

  • $\begingroup$ A non tight lower bound is the maximum of the entropy of the two variables. $\endgroup$ Jun 17 '14 at 15:47
  • $\begingroup$ Doesn't this fall out of the information-theoretic characterization instantly? Since $U=X\oplus(X\oplus U)$, if $H(X\oplus U)$ weren't that large then $U$ wouldn't have full entropy. The same should be true of any function $f(X,U)$ for which there's a function $g()$ such that $U=g(X, f(X,U))$. $\endgroup$ Aug 25 '14 at 23:31

Case $\epsilon = 0$ can be proved in a way that reveals for the general case $\epsilon >0$.

Lemma. (Applying an independent random injective function to a random variable does not decrease entropy) If $X, Y$ are independent discrete random variables and $f_y$ is an injective function on the range of $X$ for each $y$ in the range of $Y$, then $H(f_Y(X)) \ge H(X)$.

Proof: $H(f_Y(X)) \ge H(f_Y(X)|Y) = H(X|Y) = H(X)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.