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

Your Answer


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

Browse other questions tagged or ask your own question.