# A tight lower bound for the entropy of the XOR of two random variables

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.

• A non tight lower bound is the maximum of the entropy of the two variables. – Thomas Ahle Jun 17 '14 at 15:47
• 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))$. – Steven Stadnicki Aug 25 '14 at 23:31

## 1 Answer

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)$.