Asymptotic Equipartition Property

Definition (Typical Set)

For a DMS $\{X_i\}_{i=1}^\infty$ with pmf $p_X$ on $\mathcal{X}$ and entropy $H(X)$ , given integer $n\ge 1$ and $\epsilon>0$ , the typical set $A_\epsilon^{(n)}$ with respect to the source is $\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 $a^n=(a_1,\cdots,a_n)$ drawn iid from $\mathcal{X}$ according to $p_X$ whose probability is roughly $2^{-nH(X)}$ ; or whose “apparent entropy” is within the “true entropy” $H(X)$ .

Theorem (Asymptotic Equipartition Property)

For a DMS $\{X_i\}_{i=1}^\infty$ with pmf $p_X$ and alphabet $\mathcal{X}$ , $-\frac{1}{n}\log_2(p_{X^n}(X^n))\xrightarrow{n\to\infty}H(X)\mbox{ in probability}$ for the average information of $X_i,n\ge1$ converges in probability to the entropy of $X$ . For a stationary ergodic source $\{X_i\}_{i=1}^\infty$ we have $-\frac{1}{n}\log_2(p_{X^n}(X^n))\xrightarrow{n\to\infty}H(\mathcal{X})\mbox{ in probability}$

Remark

AEP states that a subset $B_{\epsilon}^{(n)}$ of $\mathcal{X}^{n}$ given by $B_{\epsilon}^{(n)}=\{a^{n}\in\mathcal{X}^{n}:|- \frac{1}{n}\log_{2}p_{X^{n}}(a^{n})-H(X)|>\epsilon\}$ satisfies $\lim_{n\to\infty}P(B_{\epsilon}^{(n)})=0$

Theorem (Consequence of AEP)

For a DMS $\{X_i\}_{i=1}^\infty$ with pmf $p_X$ on $\mathcal{X}$ and entropy $H(X)$ , the typical set $A_\epsilon^{(n)}$ satisfies:

$\lim_{n\to\infty}P(A_\epsilon^{(n)})=1$
$|A_\epsilon^{(n)}|\le2^{n(H(X)+\epsilon)}$
$|A_\epsilon^{(n)}|\ge(1-\epsilon)2^{n(H(X)-\epsilon)}$ for $n$ sufficiently large

Definition (Joint typical set)

Let $\{(X_{i},Y_{i})\}^\infty_{i=1}$ be a |DMS with common pmf $p_{XY}$ on $\mathcal{X}\times\mathcal{Y}$ . Given $\delta>0$ and integer $n\ge1$ , the jointly typical set $A_\delta^{(n)}$ (or jointly $\delta$ -typical set) with respect to the source is $\begin{align*} A_{\delta}^{(n)}=\left\{(x^{n},y^{n})\in \mathcal{X}^{n}\times\mathcal{Y}^{n}:\left|-\frac{1}{n}\log_{2}(p_{X^{n}}(x^{n}))-H(X)\right|\le\delta,\right.\\ \left|-\frac{1}{n}\log_{2}(p_{Y^{n}}(y^{n}))-H(Y)\right|\le\delta,\\ \left.\left|-\frac{1}{n}\log_{2}(p_{X^{n}Y^{n}}(x^{n},y^{n}))-H(X,Y)\right|\le\delta \right\}\\ \end{align*}$

Theorem (Joint Asymptotic Equipartition Property)

For a DMS $\{(X_{i},Y_{i})\}^\infty_{i=1}$ with pmf $p_{XY}$ on $\mathcal{X}\times\mathcal{Y}$ , then the joint typical set $A_{\delta}^{(n)}$ defined with respect to source $p_{XY}$ satisfies:

$P_{X^{n}Y^{n}}(A_\delta^{(n)})=P((X^{n},Y^{n})\in A_{\delta}^{(n)})>1-\delta$ for $n$ sufficiently large
$|A_\delta^{(n)}|\le2^{n(H(X,Y)+\delta)}$
$|A_\delta^{(n)}|\ge(1-\delta)2^{n(H(X,Y)-\delta)}$ for $n$ sufficiently large

Definition (Typical set)

Fix $\epsilon>0$ and $n$ , the typical set $A_{\epsilon}^{(n)}$ for a CMS with pdf $f_{X}$ is given by $A_{\epsilon}^{(n)}=\{x^{n}\in S_{X^{n}}:|- \frac{1}{n}\log_{2}f_{X^{n}}(X^{n})-h(X)|\le\epsilon\}$

Theorem (AEP For Continuous IID RVs)

Let $\{X_{i}\}_{i=1}^{\infty}$ be a memoryless real-valued source, with common pdf $f_{X}$ with support $S_{X}\subset \mathbb{R}$ . Then $- \frac{1}{n}\log_{2}f_{X^{n}}(X_{1},\ldots,X_{n})\stackrel{ n\to\infty}\to E\left[-\log_{2}f_{X}(X)\right]=h(X)$ in probability.

Theorem (Consequence of the continuous AEP)

For the memoryless continuous source $\{X_{i}\}^\infty_{i=1}$ with pdf $f_{X}$ defined on $S_{X}\subset\mathbb{R}$ and differential entropy $h(X)$ , the following hold:

$\lim_{n\to\infty}P_{X^{n}}\left(A_{\epsilon}^{(n)}\right)=1,\ \mbox{ i.e. }P_{X^{n}}\left(A_{\epsilon}^{(n)}\right)>1-\epsilon \ \mbox{ for }n\mbox{ sufficiently large}$
$vol(A_{\epsilon}^{(n)})\le 2^{n(h(X))+\epsilon} \ \forall n$
$vol(A_{\epsilon}^{(n)}>(1-\epsilon)2^{n(h(X)-\epsilon)}) \ \mbox{for }n\mbox{ sufficiently large}$

Asymptotic Equipartition Property

Linked from