Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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