Mutual Information

In general, the channel itself can add noise. This means that the channel adds an additional layer of uncertainty to our transmissions. Consider a channel with input symbols $A=\{a_{1},a_{2},\ldots ,a_{n}\}$, and output symbols $B=\{b_{1},b_{2},\ldots ,b_{m}\}$. Note that the input and output alphabets do not need to have the same number of symbols. Given the noise in the channel, if we observe the output symbol $b_{j}$, we are not sure which $a_{i}$ was the input symbol.

We can then characterize the discrete channel as a set of probabilities $\{P\left(a_{i}\mid b_{j}\right)\}$. If the probability distribution of the outputs depend on the current input, then the channel is memoryless. Let us consider the information we get from observing a symbol $b_{j}$ at the output of a discrete memoryless channel (DMC).

Definition

Figure 1: A noisy channel.

Given a probability model of the source, we have an a priori estimate $P\left(a_{i}\right)$ that symbol $a_{i}$ will be sent next. Upon observing $b_{j}$, we can revise our estimate to $P\left(a_{i}\mid b_{j}\right)$, as shown in Fig. 1. The change in information, or mutual information, is given by:

$I\left(a_{i};b_{j}\right)=\log _{2}\left({\frac {1}{P\left(a_{i}\right)}}\right)-\log _{2}\left({\frac {1}{P\left(a_{i}\mid b_{j}\right)}}\right)=\log _{2}\left({\frac {P\left(a_{i}\mid b_{j}\right)}{P\left(a_{i}\right)}}\right)$

(1)

Let's look at a few properties of mutual information. Expressing the equation above in terms of $I\left(a_{i}\right)$:

$I\left(a_{i};b_{j}\right)=I\left(a_{i}\right)+\log _{2}\left(P\left(a_{i}\mid b_{j}\right)\right)$

(2)

Thus, we can say:

$I\left(a_{i};b_{j}\right)\leq I\left(a_{i}\right)$

(3)

Figure 2: An information channel.

This is expected since, after observing $b_{j}$, the amount of uncertainty is reduced, i.e. we know a bit more about $a_{i}$, and the most change in information we can get is when $a_{i}$ and $b_{j}$ are perfectly correlated, with $I\left(a_{i};b_{j}\right)=I\left(a_{i}\right)$. Thus, we can think of mutual information as the average information conveyed across the channel, as shown in Fig. 2. From Bayes' Theorem, we have the property:

$I\left(a_{i};b_{j}\right)=\log _{2}\left({\frac {P\left(a_{i}\mid b_{j}\right)}{P\left(a_{i}\right)}}\right)=\log _{2}\left({\frac {P\left(b_{j}\mid a_{i}\right)}{P\left(b_{j}\right)}}\right)=I\left(b_{j};a_{i}\right)$

(4)

Note that if $a_{i}$ and $b_{j}$ are independent, where $P\left(a_{i}\mid b_{j}\right)=P\left(a_{i}\right)$ and $P\left(b_{j}\mid a_{i}\right)=P\left(b_{j}\right)$, then:

$I\left(a_{i};b_{j}\right)=\log _{2}\left({\frac {P\left(a_{i}\mid b_{j}\right)}{P\left(a_{i}\right)}}\right)=\log _{2}\left({\frac {P\left(b_{j}\mid a_{i}\right)}{P\left(b_{j}\right)}}\right)=\log _{2}\left(1\right)=0$

(5)

We can get the average mutual information over all the input symbols as:

$I\left(A;b_{j}\right)=\sum _{i=1}^{n}P\left(a_{i}\mid b_{j}\right)\cdot I\left(a_{i};b_{j}\right)=\sum _{i=1}^{n}P\left(a_{i}\mid b_{j}\right)\cdot \log _{2}\left({\frac {P\left(a_{i}\mid b_{j}\right)}{P\left(a_{i}\right)}}\right)$

(6)

Similarly, for all the output symbols:

$I\left(a_{i};B\right)=\sum _{j=1}^{m}P\left(b_{j}\mid a_{i}\right)\cdot \log _{2}\left({\frac {P\left(b_{j}\mid a_{i}\right)}{P\left(b_{j}\right)}}\right)$

(7)

For both input and output symbols, we get:

${\begin{aligned}I\left(A;B\right)&=\sum _{i=1}^{n}P\left(a_{i}\right)\cdot I\left(a_{i};B\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i}\right)P\left(b_{j}\mid a_{i}\right)\cdot \log _{2}\left({\frac {P\left(b_{j}\mid a_{i}\right)}{P\left(b_{j}\right)}}\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {P\left(a_{i},b_{j}\right)}{P\left(a_{i}\right)\cdot P\left(b_{j}\right)}}\right)\\&=I\left(B;A\right)\end{aligned}}$

(8)

Non-Negativity of Mutual Information

To show the non-negativity of mutual information, let us use Jensen's Inequality, which states that for a convex function, $f\left(x\right)$:

$\langle f\left(x\right)\rangle \geq f\left(\langle x\rangle \right)$

(9)

Using the fact that $f\left(x\right)=-\log _{2}\left(x\right)$ is convex, and applying this to our expression for mutual information, we get:

${\begin{aligned}I\left(A;B\right)&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {P\left(a_{i},b_{j}\right)}{P\left(a_{i}\right)\cdot P\left(b_{j}\right)}}\right)\\&=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {P\left(a_{i}\right)\cdot P\left(b_{j}\right)}{P\left(a_{i},b_{j}\right)}}\right)\\&=\left\langle -\log _{2}\left({\frac {P\left(a_{i}\right)\cdot P\left(b_{j}\right)}{P\left(a_{i},b_{j}\right)}}\right)\right\rangle \\&\geq -\log _{2}\left(\left\langle {\frac {P\left(a_{i}\right)\cdot P\left(b_{j}\right)}{P\left(a_{i},b_{j}\right)}}\right\rangle \right)=-\log _{2}\left(\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot {\frac {P\left(a_{i}\right)\cdot P\left(b_{j}\right)}{P\left(a_{i},b_{j}\right)}}\right)\\&\geq -\log _{2}\left(\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i}\right)\cdot P\left(b_{j}\right)\right)=-\log _{2}\left(\sum _{i=1}^{n}P\left(a_{i}\right)\sum _{j=1}^{m}P\left(b_{j}\right)\right)=-\log _{2}\left(1\right)\\&\geq 0\\\end{aligned}}$

(10)

Note that $I\left(A;B\right)=0$ when $A$ and $B$ are independent.

Conditional and Joint Entropy

Given $A$ and $B$, and their entropies:

$H\left(A\right)=\sum _{i=1}^{n}P\left(a_{i}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i}\right)}}\right)$

(11)

$H\left(B\right)=\sum _{j=1}^{m}P\left(b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)$

(12)

Conditional Entropy

The conditional entropy is a measure of the average uncertainty about $B$ when $A$ is known, and we can define it as:

${\begin{aligned}H\left(B\mid A\right)&=\sum _{i=1}^{n}P\left(a_{i}\right)\sum _{j=1}^{m}P\left(b_{j}\mid a_{i}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\mid a_{i}\right)}}\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i}\right)P\left(b_{j}\mid a_{i}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\mid a_{i}\right)}}\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(b_{j},a_{i}\right)\cdot \log _{2}\left({\frac {P\left(a_{i}\right)}{P\left(b_{j},a_{i}\right)}}\right)\\\end{aligned}}$

(13)

And similarly,

${\begin{aligned}H\left(A\mid B\right)&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(b_{j},a_{i}\right)\cdot \log _{2}\left({\frac {P\left(b_{j}\right)}{P\left(b_{j},a_{i}\right)}}\right)\\&\neq H\left(B\mid A\right)\\\end{aligned}}$

(14)

Joint Entropy

If we extend the definition of entropy to two (or more) random variables, $A$ and $B$, we can define the joint entropy of $A$ and $B$ as:

$H\left(A,B\right)=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i},b_{j}\right)}}\right)$

(15)

Expanding expression for joint entropy, and using $P\left(a_{i},b_{j}\right)=P\left(a_{i}\mid b_{j}\right)P\left(b_{j}\right)$ we get:

${\begin{aligned}H\left(A,B\right)&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i}\mid b_{j}\right)P\left(b_{j}\right)}}\right)=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left(P\left(a_{i}\mid b_{j}\right)P\left(b_{j}\right)\right)\\&=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\left(\log _{2}\left(P\left(a_{i}\mid b_{j}\right)\right)+\log _{2}\left(P\left(b_{j}\right)\right)\right)\\&=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left(P\left(a_{i}\mid b_{j}\right)\right)-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left(P\left(b_{j}\right)\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i}\mid b_{j}\right)}}\right)+\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {P\left(b_{j}\right)}{P\left(a_{i},b_{j}\right)}}\right)+\sum _{j=1}^{m}\left(\sum _{i=1}^{n}P\left(a_{i},b_{j}\right)\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)\\&=H\left(A\mid B\right)+\sum _{j=1}^{m}P\left(b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)\\&=H\left(A\mid B\right)+H\left(B\right)\end{aligned}}$

(16)

If we instead used $P\left(a_{i},b_{j}\right)=P\left(b_{j}\mid a_{i}\right)P\left(a_{i}\right)$, we would get the alternative expression:

$H\left(A,B\right)=H\left(B\mid A\right)+H\left(A\right)$

(17)

We can then expand our expression for $I\left(A;B\right)$ as:

${\begin{aligned}I\left(A;B\right)&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {P\left(a_{i},b_{j}\right)}{P\left(a_{i}\right)\cdot P\left(b_{j}\right)}}\right)\\&=\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \left(\log _{2}\left(P\left(a_{i},b_{j}\right)\right)-\log _{2}\left(P\left(a_{i}\right)\right)-\log _{2}\left(P\left(b_{j}\right)\right)\right)\\&=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i},b_{j}\right)}}\right)+\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i}\right)}}\right)+\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)\\&=-\sum _{i=1}^{n}\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i},b_{j}\right)}}\right)+\sum _{i=1}^{n}\left(\sum _{j=1}^{m}P\left(a_{i},b_{j}\right)\right)\cdot \log _{2}\left({\frac {1}{P\left(a_{i}\right)}}\right)+\sum _{j=1}^{m}\left(\sum _{i=1}^{n}P\left(a_{i},b_{j}\right)\right)\cdot \log _{2}\left({\frac {1}{P\left(b_{j}\right)}}\right)\\&=-H\left(A,B\right)+H\left(A\right)+H\left(B\right)\\&=H\left(A\right)-H\left(A\mid B\right)\\&=H\left(B\right)-H\left(B\mid A\right)\\\end{aligned}}$

(18)

We can then think of mutual information as the reduction in uncertainty due to another random variable. The above relationships between mutual information and the entropies are illustrated in Fig. 2. Note that $H\left(A\mid A\right)=0$ since $P\left(a_{i}\mid a_{i}\right)=1$. We can then write:

$I\left(A;A\right)=H\left(A\right)-H\left(A\mid A\right)=H\left(A\right)$

(19)

Thus, we can think of entropy as self-information.

Channel Capacity

The maximum amount of information that can be transmitted through a discrete memoryless channel, or the channel capacity, with units bits per channel use, can then be thought of as the maximum mutual information over all possible input probability distributions:

$C=\max _{P\left(A\right)}I\left(A;B\right)$

(20)

Or equivalently, we need to choose $\{P\left(a_{i}\right)\}$ such that we maximize $I\left(A;B\right)$. Since:

$I\left(A;B\right)=\sum _{i=1}^{n}P\left(a_{i}\right)\cdot I\left(a_{i};B\right)$

(21)

And if we are using the channel at its capacity, then for every $a_{i}$:

$I\left(a_{i};B\right)=C$

(22)

Thus, we can maximize channel use by maximizing the use for each symbol independently. From the definition of mutual information and from the Gibbs inequality, we can see that:

$C\leq H\left(A\right),H\left(B\right)\leq \log _{2}\left(n\right),\log _{2}\left(m\right)$

(23)

Where $n$ and $m$ are the number of symbols in $A$ and $B$ respectively. Thus, the channel capacity of a channel is limited by the logarithm of the number of distinguishable symbols at its input (or output).

Activity A3.1 Channel Capacity -- This activity introduces the concept of mutual information and channel capacity in noisy channels.

Sources

• Tom Carter's notes on Information Theory
• Dan Hirschberg's notes on Data Compression
• Lance Williams' notes on Geometric and Probabilistic Methods in Computer Science