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

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.