= Solution
Every member of the <typical set> has probability at least $2^{-n(H(X)+\varepsilon)}$. Summing these probabilities gives
$$
1\geq\sum_{x^n\in T_\varepsilon^{(n)}}p(x^n)
\geq|T_\varepsilon^{(n)}|\,2^{-n(H(X)+\varepsilon)},
$$
so
$$
\boxed{|T_\varepsilon^{(n)}|\leq2^{n(H(X)+\varepsilon)}}.
$$
The upper bound itself holds at every block length. For sufficiently large $n$, the high-probability property also gives the companion lower bound
$$
1-\delta\leq\mathbb P(T_\varepsilon^{(n)})
\leq|T_\varepsilon^{(n)}|\,2^{-n(H(X)-\varepsilon)},
$$
hence $|T_\varepsilon^{(n)}|\geq(1-\delta)2^{n(H(X)-\varepsilon)}$. Together these are the <typical-set cardinality bounds> underlying <Shannon source coding theorem>.
Back to article page
