1
$\begingroup$

Suppose $A$ and $B$ two different binary strings of length $l$. Suppose the Mutual Information (https://en.wikipedia.org/wiki/Mutual_information) of $A$ and $B$ is known to be $I$.

Now suppose bit-wise a Boolean function is applied to get another bit-string $C$. The Boolean function is $f(0,0)=0, f(0,1)=0, f(1,0)=0, f(1,1)=1$.

Under this function f, what would be the Shannon entropy of the bit-string $C$? I want to know the least upper bound and greatest lower bound of the Shannon entropy.

Thanks in advance.

$\endgroup$
  • $\begingroup$ What have you previously tried? Why haven't they worked? $\endgroup$ – James Jun 13 '15 at 6:29
  • $\begingroup$ You have defined A and B twice. "Suppose A and B are two binary strings..." and "Suppose the mutual information of two discrete r.v.s A and B...". $\endgroup$ – James Jun 13 '15 at 6:30
  • $\begingroup$ My strong guess is the entropy of the bit-string C would be less than 0.5. Am I right? I am interested more on least upper bound and greatest lower bound. $\endgroup$ – Fukuzita Jun 13 '15 at 6:31
  • $\begingroup$ @James, Question is edited. $\endgroup$ – Fukuzita Jun 13 '15 at 6:33
  • $\begingroup$ Say the last $l$ bits of $A$ and the last $l$ bits of $B$ are all mutually independent and uniform in $\{0,1\}$. Moreover, let $(A_1, B_1)$ also be independent from everything else, and have some joint distribution that ensures the 1/2 mutual information. Then wouldn't the entropy of $C$ be linear in $l$? $\endgroup$ – Sasho Nikolov Jun 13 '15 at 15:14
2
$\begingroup$

The mutual information tells you nothing about the entropy of C.

The mutual information can be $l$ and the entropy of $C$ can be $0$: set $$ A(i) = 1-B(i) = \begin{cases} 0 \mbox{ with probability } 1/2, \\ 1 \mbox{ with probability } 1/2. \end{cases}$$

The mutual information can be $l$ and the entropy of $C$ can be $l$: set $$A(i) = B(i) = \begin{cases} 0 \mbox{ with probability } 1/2, \\ 1 \mbox{ with probability } 1/2. \end{cases} $$

The mutual information can be $0$ and the entropy of $C$ can be $l$: set $$ A(i) = \begin{cases} 0 \mbox{ with probability } 1 - 1/\sqrt{2},\\ 1 \mbox{ with probability } 1/\sqrt{2}, \end{cases}$$ and use the same distribution for $B(i)$, making $A$ independent of $B$.

Finally, the mutual information can be $0$ and the entropy of $C$ can be $0$: set $$A(i) = B(i) = 1.$$

And you can get any convex combination of these cases by using these same distributions on substrings of $A$ and $B$.

$\endgroup$
1
$\begingroup$

The greatest lower bound is 0 bits:

$A=1-B$, so $I(A,B)=H(A)=H(B)=0.5$. But with your definition of $f$, $C=0$, and hence $H(C)=0$

An upper bound is given in the comments by Peter Shor.

$\endgroup$
  • $\begingroup$ How come $C=A=B?$ $\endgroup$ – Fukuzita Jun 15 '15 at 9:36
  • $\begingroup$ Because $A=B$ by assumption. If $A_i=0$ and $B_i=0$, then $C_i=f(A_i,B_i)$. But $f(0,0)=0$ and $f(1,1)=1$. $\endgroup$ – Bernhard Jun 15 '15 at 9:56
  • $\begingroup$ A and B are two independent binary strings. They are not same. $\endgroup$ – Fukuzita Jun 15 '15 at 10:36
  • $\begingroup$ If they are independent then the mutual information will be zero. The bounds I stated hold -- of course -- only for the question you asked above. If you have additional constraints not mentioned in your question (e.g., $A$ and $B$ are not equal), then the bounds may be different. $\endgroup$ – Bernhard Jun 15 '15 at 13:13
  • 1
    $\begingroup$ -1: The mutual information can be 0 and the entropy of C can be $H(1/4)\cdot l$ if you let A and B be independent strings where each bit is 0 or 1 with probability $1/2$. And by altering this example slightly, you can make the mutual information $1/2$ and not change $H(C )$ much. This upper bound is wrong. $\endgroup$ – Peter Shor Jun 17 '15 at 9:46

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.