3. Typical Sets

Typical Sets

A typical set is an exponentially smaller subset of the space of all $n$-length sequences ${\mathcal{X}}^n$ (where $|{\mathcal{X}}^n|=2^{n{\log }_2|\mathcal{X}|}$), which captures most of the probability mass of the source as $n$ grows large. Formally, the $ϵ$-typical set $A_{ϵ}^{(n)}\subset {\mathcal{X}}^n$ is the set of $n$-length sequences $X^n=X_1,\dots ,X_n$, such that each sequence has a uniform probability of approximately $2^{\mathbb{E}[{\log }_2{p}_X(X^n)]}=2^{-nH(x)}$:
$A_{ϵ}^{(n)}=\{X^n\in {\mathcal{X}}^n:2^{-n(H(X)+ϵ)}\le p_{X^n}(x_1,\dots ,x_n)\le 2^{-n(H(X)-ϵ)}\},$
where $|A_{ϵ}^{(n)}|\approx 2^{nH(X)}$.

As $n$ grows large, sequences in the (much smaller) typical set $A_{ϵ}^{(n)}$ contain virtually all the probability mass of ${\mathcal{X}}^n$. Mathematically, this means that ${\lim }_{n\to \infty }\mathbb{P}(A_{ϵ}^{(n)})=1$. This property of typical sets is known as asymptotic equipartition, and is the LLN-equivalent analogue in information theory. Mathematically,
$-\frac{1}{n}{\log }_2{p}_{X^n}(X_1,\dots ,X_n)\to H(X)\text{in probability},$
meaning that the per-symbol self-information of a sequence converges to the entropy.

Properties

Examples

Biased Coin Flips

You flip $100$ coins with probability $1/4$ of coming up heads.

What is the size of the sample space? $H$ or $T$. For 100 coins, this becomes $|\Omega |=2^{100}$.

We know that each coin can either land on

What is the size of the typical set, and how do the two sizes compare? $H(X)=0.25\log 4+0.75\log \frac{4}{3}=0.811\text{ bits per coinflip.}$ Therefore, the size of the typical set is $\approx 2^{81}$, or $\frac{2^{81}}{2^{100}}=\frac{1}{2^{19}}$ of the size of the sample space.

We can calculate the entropy of each coin as