# Bounds for Mutual Information

$V_1$, $V_2$ be two binary strings with equal number of bits (say the length is $l$). Then the mutual information of $V_1$, $V_2$ can be defined as:

$I(V_1;V_2)$ = $\sum_{y \in Y} \sum_{x \in X} p(x,y) \log{ \left(\frac{p(x,y)}{p(x)\,p(y)} \right) }$

Where $p(x,y)$ = frequency of the ordered pair $(x,y)$ where $x$,$y$ comes from same bit positions of $V_1$ and $V_2$.Here $x$ and $y$ can take values from the set {0, 1}. Here the set $X$=$Y$={0, 1}. $p(x)$ and $p(y)$ are the frequencies of 1's in the string $V_1$ and $V_2$ respectively.

Example: Suppose $V_1=100010$ and $V_2=001101$ be given two bit strings. Here $l$=6. So here p(1)=2/6, p(1)=3/6 in case of $V_1$ and $V_2$ respectively. Also $p(0,0)=1/6$, $p(0,1)=3/6$, $p(1,0)=2/6$ and $p(1,1)=0/6$.

Questions: If $p(x,y)\neq 0$ for all ordered pair $(x,y)$. What is the minimum of $I$? If at least one $p(x,y)=0$ for some pair $(x,y)$, then what is the maximum $I$? If only one $p(x,y)\neq 0$ for an ordered pair $(x,y)$, what is the maximum I?

The minimum $MI$ possible is always zero. This occurs when the random variables $X$ and $Y$ are independent. This means $p(x,y)=p(x)p(y)$, and so the ratio $\frac{p(x,y)}{p(x)p(y)}=\frac{p(x)p(y)}{p(x)p(y)}=1$ , and of course $log(1)=0$ so the mutual information is zero.
The maximum $MI$ can vary from case to case. It's easier to think about this if we refer to the entropy definition $MI(X,Y) = H(X) - H(X|Y)$. The maximum would occur when $H(X|Y)=0$, so the upper limit on $MI(X,Y)$ is $H(X)=\sum_x p(x) log(\frac{1}{p(x)})$. Since we are dealing with binary strings, this is has maximum of $H(X)=1$ when the number of $0$'s and $1$'s have equal probability in string $V_1$, and there is a deterministic relationship between the values of the strings $V_1$ and $V_2$. So for example, anywhere we see a $1$ in $V_1$ we get a $0$ in $V_2$ in the same position. This makes sense, because maximum information gain occurs when we can always guess one value correctly from the other.
In fact, any deterministic relationship between $X$ and $Y$ causes $H(X|Y)=0$. Given $Y$, there is no uncertainty/entropy in $X$ since we can get the answer with absolute certainty.
If we only have one $p(x,y)\neq0$, then all terms in the mutual information sum vanish, so $MI(X,Y)=0$. You could think of this as saying the strings contain no information at all since they just repeat the same symbol over and over and there is no uncertainty in their contents.