Past exam of the information theory course of the University of Oxford / 2023 / 2 / c

For every $x^n\in A^{n,\epsilon }$, the defining typical set constraint impliesLet $S_n=A^{n,\epsilon }\cap B^{n,\epsilon }$. Summing the lower probability mass bound over $S_n$ givesThereforeThe sample mean constraint can only shrink the typical set, so this cardinality upper bound holds for every positive integer $n$.

For fixed $\epsilon >0$, the asymptotic equipartition property gives $\mathrm{Pr}(X^n\notin A^{n,\epsilon })\to 0$. The strong law of large numbers applied to $X_i$, which are bounded because their numerical alphabet is finite, gives $\mathrm{Pr}(X^n\notin B^{n,\epsilon })\to 0$. The union bound therefore yieldsSince $\delta >0$, eventually $\mathrm{Pr}(X^n\in S_n)\ge 2^{-\delta }$. Each word in $S_n$ has probability mass at most $2^{-n(H(p)-\epsilon )}$, soRearranging provesfor sufficiently large $n$. The key is that the factor $2^{-\delta }$ is a fixed number below one, however small $\delta$ is. This is an instance of typical sets with an additional high-probability constraint.