= Typical sets with an additional high-probability constraint
{title2=$|A^{n,\varepsilon}\cap B_n|\geq2^{n(H-\varepsilon)-\delta}$}
Let $A^{n,\varepsilon}$ be the weak <typical set> of a <finite alphabet> <independent and identically distributed> source with <Shannon entropy> $H$, and let $B_n$ be any sets with $\Pr(X^n\in B_n)\to1$. The <asymptotic equipartition property> and <union bound> give $\Pr(X^n\in A^{n,\varepsilon}\cap B_n)\to1$. Every word in the intersection has <probability mass> between $2^{-n(H+\varepsilon)}$ and $2^{-n(H-\varepsilon)}$. Summing these bounds gives
$$
\Pr(X^n\in A^{n,\varepsilon}\cap B_n)\,2^{n(H-\varepsilon)}
\leq|A^{n,\varepsilon}\cap B_n|\leq2^{n(H+\varepsilon)}.
$$
For every fixed $\delta>0$, the first <probability> eventually exceeds $2^{-\delta}$, proving the title bound. A <sample mean> within a fixed positive tolerance of the <expected value> supplies $B_n$ by the <strong law of large numbers>.
Back to article page
