= Solution
For fixed $\varepsilon>0$, the <asymptotic equipartition property> gives $\Pr(X^n\notin A^{n,\varepsilon})\to0$. The <strong law of large numbers> applied to $X_i$, which are bounded because their numerical <alphabet> is finite, gives $\Pr(X^n\notin B^{n,\varepsilon})\to0$. The <union bound> therefore yields
$$
\Pr(X^n\in S_n)\geq1-\Pr(X^n\notin A^{n,\varepsilon})-\Pr(X^n\notin B^{n,\varepsilon})\longrightarrow1.
$$
Since $\delta>0$, eventually $\Pr(X^n\in S_n)\geq2^{-\delta}$. Each word in $S_n$ has <probability mass> at most $2^{-n(H(p)-\varepsilon)}$, so
$$
2^{-\delta}\leq\Pr(X^n\in S_n)
\leq |S_n|2^{-n(H(p)-\varepsilon)}.
$$
Rearranging proves
$$
\boxed{|A^{n,\varepsilon}\cap B^{n,\varepsilon}|\geq2^{n(H(p)-\varepsilon)-\delta}}
$$
for 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>.
Back to article page
