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

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.