# Calculation of Shannon entropy given the mutual information of Binary strings

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.

• What have you previously tried? Why haven't they worked? – James Jun 13 '15 at 6:29
• 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...". – James Jun 13 '15 at 6:30
• 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. – Fukuzita Jun 13 '15 at 6:31
• @James, Question is edited. – Fukuzita Jun 13 '15 at 6:33
• 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$? – Sasho Nikolov Jun 13 '15 at 15:14

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

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.

• How come $C=A=B?$ – Fukuzita Jun 15 '15 at 9:36
• 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$. – Bernhard Jun 15 '15 at 9:56
• A and B are two independent binary strings. They are not same. – Fukuzita Jun 15 '15 at 10:36
• 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. – Bernhard Jun 15 '15 at 13:13
• -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. – Peter Shor Jun 17 '15 at 9:46