= Solution
Fix $0\leq\epsilon<1$ and $\delta>0$. By the <asymptotic equipartition property>, all sufficiently large $n$ satisfy $\Pr(Z^{(n)}\notin T_\delta^n)\leq(1-\epsilon)/2$. For any <epsilon-sufficient set> $S_n$,
$$
\Pr(Z^{(n)}\in S_n\cap T_\delta^n)\geq\Pr(Z^{(n)}\in S_n)-\Pr(Z^{(n)}\notin T_\delta^n)\geq\frac{1-\epsilon}{2}.
$$
Each word in this intersection has probability at most $2^{-n(H(Z)-\delta)}$. Hence
$$
\frac{1-\epsilon}{2}\leq|S_n\cap T_\delta^n|\,2^{-n(H(Z)-\delta)}\leq|S_n|\,2^{-n(H(Z)-\delta)},
$$
which gives the <minimum size of a sufficient set for an IID source>:
$$
\boxed{|S_n|\geq\frac{1-\epsilon}{2}\,2^{n(H(Z)-\delta)}.}
$$
The <Chebyshev inequality> used above supplies the sufficient quantitative condition $n\geq2v/[\delta^2(1-\epsilon)]$. No assumption that $S_n$ itself is a <typical set> is needed; its intersection with one provides the bound.
Back to article page
