Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
A non tight lower bound is the maximum of the entropy of the two variables. –  Thomas Ahle Jun 17 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 at 23:31

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.