161-A3.1

• Activity: Mutual Information and Channel Capacity
• Instructions: In this activity, you are tasked to
  • Walk through the examples.
  • Calculate the channel capacity of different channel models.
• Should you have any questions, clarifications, or issues, please contact your instructor as soon as possible.

Example 1: Mutual Information

Given the following probabilities:

Table 1: $X$: Blood Type, $Y$: Chance for Skin Cancer

	A	B	AB	O
Very Low	1/8	1/16	1/32	1/32
Low	1/16	1/8	1/32	1/32
Medium	1/16	1/16	1/16	1/16
High	1/4	0	0	0

To get the entropies of $X$ and $Y$, we need to calculate the marginal probabilities:

$P_{X}=\{{\tfrac {1}{2}},{\tfrac {1}{4}},{\tfrac {1}{8}},{\tfrac {1}{8}}\}$

(1)

$P_{Y}=\{{\tfrac {1}{4}},{\tfrac {1}{4}},{\tfrac {1}{4}},{\tfrac {1}{4}}\}$

(2)

And since:

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

(3)

We get:

$H\left(X\right)={\frac {1}{2}}\log _{2}2+{\frac {1}{4}}\log _{2}4+{\frac {1}{8}}\log _{2}8+{\frac {1}{8}}\log _{2}8={\frac {7}{4}}\,\mathrm {bits} =1.75\,\mathrm {bits}$

(4)

$H\left(Y\right)={\frac {1}{4}}\log _{2}4+{\frac {1}{4}}\log _{2}4+{\frac {1}{4}}\log _{2}4+{\frac {1}{4}}\log _{2}4=2\,\mathrm {bits}$

(5)

Calculating the conditional entropies using:

$H\left(X\mid Y\right)=\sum _{i=1}^{4}\sum _{j=1}^{4}P\left(x_{i},y_{j}\right)\cdot \log _{2}\left({\frac {P\left(y_{j}\right)}{P\left(x_{i},y_{j}\right)}}\right)={\frac {11}{8}}\,\mathrm {bits} =1.375\,\mathrm {bits}$

(6)

$H\left(Y\mid X\right)=\sum _{i=1}^{4}\sum _{j=1}^{4}P\left(x_{i},y_{j}\right)\cdot \log _{2}\left({\frac {P\left(x_{i}\right)}{P\left(x_{i},y_{j}\right)}}\right)={\frac {13}{8}}\,\mathrm {bits} =1.625\,\mathrm {bits}$

(7)

Note that $H\left(X\mid Y\right)\neq H\left(Y\mid X\right)$. Calculating the mutual information, we get:

$I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)={\frac {7}{4}}-{\frac {11}{8}}=0.375\,\mathrm {bits}$

(8)

Or equivalently:

$I\left(X;Y\right)=H\left(Y\right)-H\left(Y\mid X\right)=2-{\frac {13}{8}}=0.375\,\mathrm {bits}$

(9)

Let us try to understand what this means:

• If we only consider $X$, we have the a priori probabilities, $P_{X}$ for each blood type, and we can calculate the entropy, $H\left(X\right)$, i.e. the expected value of the information we get when we observe the results of the blood test.
• Will our expectations change if we do not have access to the blood test, but instead, we get to access (1) the person's susceptibility to skin cancer, and (2) the joint probabilities in Table 1? Since we are given more information, we expect one of the following:
  • The uncertainty to be equal to the original uncertainty if $X$ and $Y$ are independent, since $H\left(X\mid Y\right)=H\left(X\right)$, thus $I\left(X;Y\right)=H\left(X\right)-H\left(X\mid Y\right)=0$.
  • A reduction in the uncertainty equal to $I\left(X;Y\right)$, due to the additional information given by $P\left(x_{i},y_{j}\right)$.
  • If $X$ and $Y$ are perfectly correlated, we reduce the uncertainty to zero since $H\left(X\mid Y\right)=H\left(X\mid X\right)=0$ and $I\left(X;Y\right)=H\left(X\right)$.

Example 2: A Noiseless Binary Channel

Consider transmitting information over a noiseless binary channel shown in Fig. 1. The input, $A=\{0,1\}$ has a priori probabilities $P\left(A=0\right)=\alpha$ and $P\left(A=1\right)=1-\alpha$, and the output is $B=\{0,1\}$. Calculating the output probabilities:

${\begin{aligned}P\left(B=0\right)&=P\left(B=0\mid A=0\right)\cdot P\left(A=0\right)+P\left(B=0\mid A=1\right)\cdot P\left(A=1\right)\\&=1\cdot \alpha +0\cdot \left(1-\alpha \right)\\&=\alpha \\\end{aligned}}$

(10)

${\begin{aligned}P\left(B=1\right)&=P\left(B=1\mid A=0\right)\cdot P\left(A=0\right)+P\left(B=1\mid A=1\right)\cdot P\left(A=1\right)\\&=0\cdot \alpha +1\cdot \left(1-\alpha \right)\\&=1-\alpha \\\end{aligned}}$

(11)

Thus, the entropy at the output is:

$H\left(B\right)=\alpha \log _{2}{\frac {1}{\alpha }}+\left(1-\alpha \right)\log _{2}{\frac {1}{1-\alpha }}=H\left(A\right)$

(12)

The conditional entropy, $H\left(B\mid A\right)$ is then:

${\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)\\=&\,\,P\left(A=0\right)\cdot P\left(B=0\mid A=0\right)\cdot \log _{2}{\frac {1}{P\left(B=0\mid A=0\right)}}\\&+P\left(A=0\right)\cdot P\left(B=1\mid A=0\right)\cdot \log _{2}{\frac {1}{P\left(B=1\mid A=0\right)}}\\&+P\left(A=1\right)\cdot P\left(B=0\mid A=1\right)\cdot \log _{2}{\frac {1}{P\left(B=0\mid A=1\right)}}\\&+P\left(A=1\right)\cdot P\left(B=1\mid A=1\right)\cdot \log _{2}{\frac {1}{P\left(B=1\mid A=1\right)}}\\=&\,\,\alpha \cdot 1\cdot \log _{2}1\\&+\alpha \cdot 0\cdot \log _{2}{\frac {1}{0}}\\&+\left(1-\alpha \right)\cdot 0\cdot \log _{2}{\frac {1}{0}}\\&+\left(1-\alpha \right)\cdot 1\cdot \log _{2}1\\=&\,\,0\\\end{aligned}}$

(13)

Which is expected since $A$ and $B$ are perfectly correlated, and there is no uncertainty in $B$ once $A$ is given. Thus, the mutual information is:

${\begin{aligned}I\left(A;B\right)&=H\left(B\right)-H\left(B\mid A\right)=H\left(B\right)\\&=\alpha \log _{2}{\frac {1}{\alpha }}+\left(1-\alpha \right)\log _{2}{\frac {1}{1-\alpha }}\\\end{aligned}}$

(14)

To get the channel capacity, we get the maximum $I\left(A;B\right)$ over all $\alpha$. Thus, we can take the derivative of the mutual information and set it equal to zero, to find the optimal $\alpha$. And noting that $\log _{2}x={\tfrac {1}{\ln 2}}\ln x$, we get:

${\begin{aligned}{\frac {\partial I\left(A;B\right)}{\partial \alpha }}&={\frac {\partial }{\partial \alpha }}\left(\alpha \log _{2}{\frac {1}{\alpha }}+\left(1-\alpha \right)\log _{2}{\frac {1}{1-\alpha }}\right)=0\\&={\frac {\partial }{\partial \alpha }}\left({\frac {\alpha }{\ln 2}}\ln {\frac {1}{\alpha }}+{\frac {1-\alpha }{\ln 2}}\ln {\frac {1}{1-\alpha }}\right)=0\\&={\frac {1}{\ln 2}}\ln {\frac {1}{\alpha }}-\alpha {\frac {1}{\alpha ^{2}}}{\frac {\alpha }{\ln 2}}-{\frac {1}{\ln 2}}\ln {\frac {1}{1-\alpha }}-{\frac {1-\alpha }{\ln 2}}{\frac {1-\alpha }{\left(1-\alpha \right)^{2}}}=0\\\end{aligned}}$

(15)

Sources

• Yao Xie's slides on Entropy and Mutual Information