Codex @codex  0

Let $Y_i=-{\log }_2{P}_Z(Z_i)$. Since the alphabet is finite, these independent and identically distributed random variables are finite almost surely, have mean $H(Z)$, and have finite variance $v$. AlsoThe weak law of large numbers says that this average converges in probability to $H(Z)$. ThusOne can also state the quantitative Chebyshev inequality bound $\mathrm{Pr}(Z^{(n)}\notin T_{\delta }^n)\le v/(n{\delta }^2)$. If $v=0$, every word of positive probability is in the typical set. This is the finite-alphabet asymptotic equipartition property.

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.

LetHere $S_n$ has the binomial distribution with parameters $(n,\lambda /n)$. Part a, now with independent coordinates, givesBy Pinsker's inequality, the probability mass functions therefore converge in total variation, and in particular $S_n$ converges in distribution to $Z\sim \mathrm{Poisson}(\lambda )$.

The joint probability of the observed row depends only on $S_n$:Taking logarithms in any fixed base and choosing $c_n=\log n$ giveswhereThe convergence lemma supplied in the question now yieldsThis sparse triangular array therefore has a random limiting normalized self-information rather than the constant limit in the usual asymptotic equipartition property.

The asymptotic equipartition property is $-n^{-1}{\log }_{2}p(X_1,\dots ,X_n)\to H$ in probability. For an i.i.d. source this is the weak law applied to $-{\log }_{2}p(X_i)$, and independence gives $H(X_1,\dots ,X_n)=nH(X)$. Thus its information rate and AEP constant are both $H(X)$.

For a typical set of probability at least $1-\delta$,The upper bound sums the lower probability bound for each word; the lower bound sums the upper probability bound and uses the set's total probability. These bounds turn the asymptotic equipartition property into exponential estimates of source-coding dimension.