Q. 9.18 - A First Course in Probability

Question

In transmitting a bit from location A to location B, if we let X denote the value of the bit sent at location A and Y denote the value received at location B, then H(X) − HY(X) is called the rate of transmission of information from A to B. The maximal rate of transmission, as a function of P{X = 1} = 1 − P{X = 0}, is called the channel capacity. Show that for a binary symmetric channel with P{Y = 1|X = 1} = P{Y = 0|X = 0} = p, the channel capacity is attained by the rate of transmission of information when P{X = 1} = 1 2 and its value is 1 + p log p + (1 − p)log(1 − p).

Step-by-Step Solution

Answer

The given statement is justified below.

Step 1 : Given Information

We have given that $H\left(X\right)-H_Y\left(X\right)$ is called rate of transmission of information and function $P\left\{X=1\right\}=1-P\left\{X=0\right\}$ is called the channel capacity.

Step 2: Simplify

Let us consider

$X~\left(\begin{array}{cc}0& 1\\ 1-r& r\end{array}\right)$

Let determine

 $H\left(X\right)-H_Y\left(X\right)$.

Consider

$H\left(X\right)=-\left(1-r\right)\text{log}\left(1-r\right)-r\text{log}r$

Also, we have

$H_Y\left(X\right)=H_{Y-0}\left(X\right)P\left(Y=0\right)+H_{Y-1}P\left(Y=1\right)$

Then,

$$\begin{gathered} H_{Y-0}\left(X\right)=-P\left(X=0\mid Y=0\right)\text{log}P\left(X=0\mid Y=0\right) \\ -P\left(X=1\mid Y=0\right)\text{log}P\left(X=1\mid Y=0\right) \end{gathered}$$

Using Bayesian formula, we can calculate conditional probabilities

$P\left(X=0\mid Y=0\right)=\frac{P\left(Y=0\mid X=0\right)P\left(X=0\right)}{P\left(Y=0\mid X=0\right)P\left(X=0\right)+P\left(Y=0\mid X=1\right)P\left(X=1\right)}$

                            $=\frac{p\left(1-r\right)}{p\left(1-r\right)+\left(1-p\right)r}$

That is,

$$\begin{gathered} H_{Y-0}\left(X\right)= -\frac{p\left(1-r\right)}{p\left(1-r\right)+\left(1-p\right)r}\text{log}\frac{p\left(1-r\right)}{p\left(1-r\right)+\left(1-p\right)r} \\ -\frac{\left(1-p\right)r}{p\left(1-r\right)+\left(1-p\right)r}\text{log}\frac{\left(1-p\right)r}{p\left(1-r\right)+\left(1-p\right)r} \end{gathered}$$

                           

Step 3: Calculation

Similarly, we have

$$\begin{gathered} H_{Y-0}\left(X\right)= -\frac{p\left(1-r\right)}{p\left(1-r\right)+\left(1-p\right)r}\text{log}\frac{p\left(1-r\right)}{p\left(1-r\right)+\left(1-p\right)r} \\ -\frac{\left(1-p\right)r}{p\left(1-r\right)+\left(1-p\right)r}\text{log}\frac{\left(1-p\right)r}{p\left(1-r\right)+\left(1-p\right)r} \end{gathered}$$

At last, we have

$$\begin{gathered} P\left(Y=0\right)=P\left(Y=0\mid X=0\right)P\left(X=0\right)+P\left(Y=0\mid X=1\right)P\left(X=1\right) \\ =p\left(1-r\right)+\left(1-p\right)r \end{gathered}$$

and 

$\begin{array}{l}P\left(Y=1\right)=P\left(Y=1\mid X=0\right)P\left(X=0\right)+P\left(Y=1\mid X=1\right)P\left(X=1\right)\\ =\left(1-p\right)\left(1-r\right)+pr\end{array}$

Now, differentiate it and set it to the zero. We have that the differential is equal to zero if and only if $r=\frac{1}{2}$. In this case, the rate of transmission of information from $A$ to $B$ is equal to  $1+p\text{log}p+\left(1-p\right)\text{log}\left(1-p\right)$ which had to be proved.