FIND ME ON

GitHub

LinkedIn

Typical Set

🌱

Definition
InfoTheory

For a DMS {Xi}i=1\{X_i\}_{i=1}^\infty with pmf pXp_X on X\mathcal{X} and entropy H(X)H(X), given integer n1n\ge 1 and ϵ>0\epsilon>0, the typical set Aϵ(n)A_\epsilon^{(n)} with respect to the source is Aϵ(n)={anXn:1nlog2(pXn(an))H(X)ϵ}={anXn:2n(H(X)+ϵ)pXn(an)2n(H(X)ϵ)}\begin{align*} A_\epsilon^{(n)}&=\left\{a^{n}\in X^{n}:\left|-\frac{1}{n}\log_2(p_{X^{n}}(a^{n}))-H(X)\right|\le\epsilon\right\}\\\\ &=\left\{a^{n}\in X^{n}:2^{-n(H(X)+\epsilon)}\le p_{X^{n}}(a^{n})\le2^{-n(H(X)-\epsilon)}\right\} \end{align*} or the typical set is the set of all n-tuples an=(a1,,an)a^n=(a_1,\cdots,a_n) drawn iid from X\mathcal{X} according to pXp_X whose probability is roughly 2nH(X)2^{-nH(X)}; or whose “apparent entropy” is within the “true entropy” H(X)H(X).