Past exam of the communication Theory course of the University of Oxford / 2008 / 2

For a finite probability distribution,with $0{\log }_{2}0=0$. If the positive support has size $s\le n$, apply the given strict Jensen inequality to the random variable $Z=1/p_X$:Equality requires $s=n$ and $Z$ constant almost surely, so all probabilities are $1/n$. Conversely the uniform distribution attains this bound. Thus $\boxed{H(X)\le {\log }_{2}n}$, with exactly that equality case.

Define $H(X\mid Y)={\sum }_y\mathbb{P}(Y=y)H(X\mid Y=y)$. The joint entropy identity $H(X,Y)=H(Y)+H(X\mid Y)$ follows by writing $p_{xy}=q_y{p}_{x\mid y}$ and expanding its logarithm. If $Y=g(X)$, then $H(Y\mid X)=0$ and $H(X,Y)=H(X)$, giving the desired decomposition.

Group the first two symbols together and keep the third separate. If $c<1$, the identity becomeswhere $h(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$. Binary entropy is at most one, with equality precisely at $1/2$. HenceEquality holds exactly when $a=b=(1-c)/2$. When $c=1$, $a=b=0$, so the same conclusion holds at the boundary.

The capacity of a discrete memoryless channel is $C={\max }_{P_X}I(X;Y)$, in bits per channel use. For the binary symmetric channel with crossover probability $p$, $H(Y\mid X)=h(p)$ and $H(Y)\le 1$. A uniform input makes the output uniform, attainingFor the binary erasure channel, let $E$ be its erasure indicator. This flag is visible in the output and independent of the input. If there is no erasure, the output reveals the input; otherwise it reveals nothing. Consequentlyagain attained by a uniform input. These formulas include crossover probabilities zero and one, and complete erasure.

Let $X$ be the original input, $U$ the output of the first channel, and $Y$ the final output. The independent erasure flag is observable from $Y$. The mutual information chain rule, conditioning on that flag, givesThe same uniform input maximizes $I(X;U)$ as in the binary symmetric channel. ThusThis scaling works because the erasure event is independent of both the input and the first channel noise.