Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 2 / 11G (Coding & Cryptography)

For a discrete random variable with probabilities $p_i$, its Shannon entropy in bits is $H(X)=-{\sum }_i{p}_i{\log }_2{p}_i$, with $0{\log }_{2}0=0$. Gibbs inequality states thatwith equality exactly when $p=q$. If $q_i=0<p_i$, the left side is infinite. Otherwise apply $-\ln u\ge 1-u$ to $u=q_i/p_i$ for $p_i>0$:Equality requires $q_i=p_i$ on the support and no remaining mass outside it. In particular, comparison with the uniform probability distribution on two outcomes gives binary Shannon entropy at most $1$.

Write $q=1-p_1$. For $q>0$, grouping the last two outcomes givesEquality holds if $p_2=p_3$; if $q=0$ it also holds, and then both are zero. Thus equality holds exactly when $p_2=p_3$.

For the discrete memoryless channel, assume $\alpha ,\beta \ge 0$ and $\alpha +\beta \le 1$, and set $w=1-\alpha -\beta$. Both conditional output probability distributions have Shannon entropy $H(w,\alpha ,\beta )$. The third output has probability $\beta$ regardless of the input; the first two have total probability $1-\beta$. Their Shannon entropy is maximized by making them equal, which a uniform input achieves. Hence the channel capacity isand thereforeThe usual zero-times-log convention includes $\beta =1$, when $C=0$. If $w=\alpha$, the rows coincide and every input achieves zero mutual information; otherwise the uniform input is the unique maximizing input.