Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 66 / 4

The Shannon entropy of a finite-valued random variable isAn epsilon-sufficient set is a subset $S\subseteq {\mathcal{A}}_X$ retaining all but at most $ϵ$ of the probability:Usually $0\le ϵ\le 1$. Sufficiency here concerns retained probability mass, rather than a sufficient statistic.

Use the weak notion of a typical set. For a word $z^n=(z_1,\dots ,z_n)$ write $P_Z^n(z^n)={\prod }_{i=1}^n{P}_Z(z_i)$. The definition isA weakly typical sequence therefore has probability between $2^{-n(H(Z)+\delta )}$ and $2^{-n(H(Z)-\delta )}$. Words containing zero-probability symbols are excluded. These two bounds and the weak law of large numbers provide the three conclusions below.

Let $Y_i=-{\log }_2{P}_Z(Z_i)$. Since the alphabet is finite, these independent and identically distributed random variables are finite almost surely, have mean $H(Z)$, and have finite variance $v$. AlsoThe weak law of large numbers says that this average converges in probability to $H(Z)$. ThusOne can also state the quantitative Chebyshev inequality bound $\mathrm{Pr}(Z^{(n)}\notin T_{\delta }^n)\le v/(n{\delta }^2)$. If $v=0$, every word of positive probability is in the typical set. This is the finite-alphabet asymptotic equipartition property.

Every word in the typical set has probability at least $2^{-n(H(Z)+\delta )}$. ConsequentlyRearranging proves the upper estimate in the typical-set cardinality bounds:

Fix $0\le ϵ<1$ and $\delta >0$. By the asymptotic equipartition property, all sufficiently large $n$ satisfy $\mathrm{Pr}(Z^{(n)}\notin T_{\delta }^n)\le (1-ϵ)/2$. For any epsilon-sufficient set $S_n$,Each word in this intersection has probability at most $2^{-n(H(Z)-\delta )}$. Hencewhich gives the minimum size of a sufficient set for an IID source:The Chebyshev inequality used above supplies the sufficient quantitative condition $n\ge 2v/[{\delta }^2(1-ϵ)]$. No assumption that $S_n$ itself is a typical set is needed; its intersection with one provides the bound.

Use the Shannon second coding theorem in its channel capacity form $C={\max }_{P_X}I(X;Y)$. The finite-alphabet erasure channel erases independently of the input. On an unerased output Bob knows $X$ exactly; on the erasure output his posterior distribution is still $P_X$. Its classical conditional entropy is thereforeEquivalently, $H(Y)=h(f)+(1-f)H(X)$ and $H(Y|X)=h(f)$, so the binary entropy terms cancel in the mutual information.

For an alphabet of size $k$, Shannon entropy is at most ${\log }_{2}k$, with equality for the uniform distribution. Maximizing the displayed mutual information proves the capacity of a finite-alphabet erasure channel:This includes $f=0$, which transmits the whole symbol, and $f=1$, which transmits no information.