Asymptotic Equipartition Property

Sources:

1. EE 376A: Information Theory. Winter 2018. Lecture 4. - Stanford University
2. EE 376A: Information Theory. Winter 2017. Lecture 4. - Stanford University
3. Elements of Information Theory

Intro

In information theory, the analog of the law of large numbers(LLN) is the asymptotic equipartition property (AEP).

It is a direct consequence of the weak law of large numbers.

The law of large numbers states that for iid random variables, $\frac{1}{n}\sum _{i=1}^n{X}_i$ is close to its expected value $E(X)$ for large values of $n$.

The AEP states that $\frac{1}{n}\log \frac{1}{p(X_1,X_2,\dots ,X_n)}$ is close to the entropy $H$, where $X_1,X_2,\dots ,X_n$ are i.i.d. random variables and $p(X_1,X_2,\dots ,X_n)$ is the probability of observing the sequence $X_1,X_2,\dots ,X_n$. Thus, the probability $p(X_1,X_2,\dots ,X_n)$ assigned to an observed sequence will be close to $2^{-nH}$ $$\begin{array}{r}\frac{1}{n}\log \frac{1}{p(X_1,X_2,\dots ,X_n)}\to H\\ p(X_1,X_2,\dots ,X_n)\to 2^{-nH}\end{array}$$

This enables us to divide the set of all sequences into two sets, the typical set, where the sample entropy is close to the true entropy, and the nontypical set, which contains the other sequences.

Most of our attention will be on the typical sequences. Any property that is proved for the typical sequences will then be true with high probability and will determine the average behavior of a large sample.

Notation

1. Memoryless source: $X_1,X_2,\dots$ iid $\sim X$, where $X$ denotes one PMF of arbitory $X_i$. Note that "memoryless" is used here because samples are drawn iid and have no dependence on past realizations.

   • Note: All i.i.d. r.v. have the same probability distribution and the same entropy.

2. Alphabet: $\mathcal{X}=\{1,2,\dots ,r\}$ specifies the possible values that each symbol $X_i$ can take on. The size of $\mathcal{X}$ is denoted $|\mathcal{X}|$.

3. Source sequence: $X^n=(X_1,\dots ,X_n)$ denotes the $n$-tuple that specifies a sequence of $n$ source symbols. In other words, $X^n$ is a stochastic process. Further note that ${\mathcal{X}}^n$ indicates the set of all possible source sequences of length $n$.

   • Since the source symbols are memoryless here. $X^n$ is an iid stochastic process. It's also denoted as $\left\{X_i\right\}$ in some literatures.

4. Probability of $X^n$ where $X_i$ are i.i.d. : The probability assigned to a source sequence $X^n$ is given by $P\left(X^n\right)=\prod _{i=1}^n{P}_{\mathcal{X}}\left(X_i\right)$. Since we implicitly evaluate the probabilities over the alphabet $\mathcal{X}$, we may also omit $\mathcal{X}$ amd write $$\begin{array}{}\text{(1)}& P\left(X^n\right)=\prod _{i=1}^{n}P\left(X_i\right).\end{array}$$

The $ϵ$-typical Set

Definition: For some $ϵ>0$, the source sequence $X^n$ is $ϵ$-typical if, $$\begin{array}{}\text{(2)}& |-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ.\end{array}$$

Let $A_{ϵ}^{(n)}$ denote the " $ϵ$-typical set", that is the set of all source sequences $X^n$ that are $ϵ$-typical.

即: $X^n\in A_{ϵ}^{(n)}$ <==> $X^n$ is an $ϵ$-typical set <==> $|-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ$.

Furthermore, note the following equivalent ways of defining $ϵ$-typicality:

1. $\text{(2)}$

---

2. $$\begin{array}{rl}& H(X)-ϵ\\ \text{(3)}& \le & -\frac{1}{n}\log P\left(X^n\right)\le & H(X)+ϵ\end{array}$$

---

3. $$\begin{array}{rl}& -n(H(X)+ϵ\\ \text{(4)}& \le & \log \left(P\left(X^n\right)\right)\le & -n(H(X)-ϵ)\end{array}$$

---

4. $$\begin{array}{rl}& 2^{-n(H(X)+ϵ)}\\ \text{(5)}& \le & P\left(X^n\right)\le & 2^{-n(H(X)-ϵ)}\end{array}$$

---

We have $\text{(2)}$ <==> $\text{(3)}$ <==> $\text{(4)}$ <==> $\text{(5)}$.

From $\text{(5)}$ we can say that every $ϵ$-typical set has probability roughly $2^{-nH(X)}$.

Theorem: $P(X^n\in A_{ϵ}^{(n)})\approx 1$

Theorem: $\mathrm{\forall }ϵ>0,P(X^n\in A_{ϵ}^{(n)})\stackrel{n\to \mathrm{\infty }}{⟶}1$.

Proof

1. Note that $X^n\in A_{ϵ}^{(n)}$ <==> $X^n$ is an $ϵ$-typical set <==> $|-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ$. So we have $$P(X^n\in A_{ϵ}^{(n)})=P(|-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ)$$

2. Also, we know that $P\left(X^n\right)=\prod _{i=1}^{n}P\left(X_i\right)$. Then the right term can be reformed to $$P(|-\frac{1}{n}\log \left[\prod _{i=1}^{n}P\left(X_i\right)\right]-H(X)|\le ϵ).$$ By $\text{(1)}$, it then can be reformed to $$P(|\frac{1}{n}\sum _{i=1}^n\log \frac{1}{P\left(X_i\right)}-H(X)|\le ϵ)$$ As a result, we have $$P(X^n\in A_{ϵ}^{(n)})=P(|\frac{1}{n}\sum _{i=1}^n\log \frac{1}{P\left(X_i\right)}-H(X)|\le ϵ).$$

3. Note that since $X_i$ are iid, $\log \frac{1}{P\left(X_i\right)}$ are iid. Then by the weak law of large numbers (LLN), $$P(|\frac{1}{n}\sum _{i=1}^n\log \frac{1}{P\left(X_i\right)}-E(\log \frac{1}{P(X)})|\le ϵ)\stackrel{n\to \mathrm{\infty }}{⟶}1.$$ Here we just treat $\log \frac{1}{P\left(X_i\right)}$ as iid r.v, then apply the LLN.

   Recalling that by the definition of entrypy, $H(X)\triangleq E(\log \frac{1}{P(X)})$, so $$P(|\frac{1}{n}\sum _{i=1}^n\log \frac{1}{P\left(X_i\right)}-H(X)|\le ϵ)\stackrel{n\to \mathrm{\infty }}{⟶}1.$$ To conclude,

$$P(X^n\in A_{ϵ}^{(n)})=P(|\frac{1}{n}\sum _{i=1}^n\log \frac{1}{P\left(X_i\right)}-H(X)|\le ϵ)\stackrel{n\to \mathrm{\infty }}{⟶}1.$$

Note: Since $P(X^n\in A_{ϵ}^{(n)})\approx 1$ and $A_{ϵ}^{(n)}$ is comprised of sequences each with probability roughly $2^{-nH(X)}$ of being observed(See $\text{(5)}$), then $\left|A_{ϵ}^{(n)}\right|\approx 2^{nH(X)}$. We'll provide more rigorous bounds on $\left|A_{ϵ}^{(n)}\right|$ in the following theorem.

AEP

From Theorem: $P(X^n\in A_{ϵ}^{(n)})\approx 1$, we know that for any $ϵ>0$, the probabilistic mass in ${\mathcal{X}}^n$ is almost entirely concentrated in $A_{ϵ}^{(n)}$.

From $\text{(2)}$, we know that if $X^n\in A_{ϵ}^{(n)}$, then for a fixed(given in $A_{ϵ}^{(n)}$) $ϵ>0$, we have $|-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ$.

As a result,

for $X_1,X_2,\dots$ iid $\sim X$, for any $ϵ>0$, we have $|-\frac{1}{n}\log P\left(X^n\right)-H(X)|\le ϵ$. In otherwords, $$-\frac{1}{n}\log p(X^n)\stackrel{n\to \mathrm{\infty }}{⟶}H(X).$$ This is called asymptotic equipartition property (AEP).

Thus, AEP enables us to partition the sequence $X^n$ into

• Typical set: Containing sequences with probability close to $2^{nH(X)}$.
• Atypical set: Containing the other sequences.

AEP

Note: the notation $p(X_1,X_2,\cdots ,X_n)$ in the above figure is denoted as $p(X^n)$ is this post.

Theorem: Bound of $\left|A_{ϵ}^{(n)}\right|$

Theorem: $\mathrm{\forall }ϵ>0$ and $n$ sufficiently large, $$\begin{array}{rl}& (1-ϵ)\cdot 2^{n(H(X)-ϵ)}\\ \text{(6)}& \le & \left|A_{ϵ}^{(n)}\right|\le & 2^{n(H(u)+ϵ)}.\end{array}$$

Proof

Upper bound:

See following equation: $$\begin{array}{rl}\text{(7)}& 1& \ge P(X^n\in A_{ϵ}^{(n)})\text{(8)}& & \ge \sum _{X^n\in A_{ϵ}^{(n)}}{2}^{-n(H(X)+ϵ)}& =2^{-n(H(X)+ϵ)}\cdot \left|A_{ϵ}^{(n)}\right|.\end{array}$$

$\text{(7)}$ is due to the non-negativity of any probability.

$\text{(8)}$ is due to $\text{(5)}$.

According to $\text{(???)}$, we have $$\left|A_{ϵ}^{(n)}\right|\le 2^{n(H(X)+ϵ)}.$$

---

Lower bound:

See following equation: $$\begin{array}{rl}\text{(9)}& 1-ϵ& \le P(X^n\in A_{ϵ}^{(n)})& \le \sum _{u^n\in A_{ϵ}^{(n)}}{2}^{-n(H(X)-ϵ)}\\ \text{(10)}& & =2^{-n(H(X)-ϵ)}\cdot \left|A_{ϵ}^{(n)}\right|.\end{array}$$

The starting equation $\text{(9)}$ in the lower bound proof is a consequence of Theorem: $P(X^n\in A_{ϵ}^{(n)})\approx 1$.

Since $P(X^n\in A_{ϵ}^{(n)})\stackrel{n\to \mathrm{\infty }}{⟶}1$, we can choose a sufficiently large $n$ such that $P(X^n\in A_{ϵ}^{(n)})\ge 1-ϵ,\mathrm{\forall }ϵ>0$.

According to $\text{(10)}$, we have $$\left|A_{ϵ}^{(n)}\right|\ge (1-ϵ)\cdot 2^{n(H(X)-ϵ)}.$$

Theorem: $A_{ϵ}^{(n)}$ is an exponentially smaller than ${\mathcal{X}}^n$

The space of all possible source sequences ${\mathcal{X}}^n$ has exponential size $\left|{\mathcal{X}}^n\right|=r^n$, and the $ϵ$-typical set $A_{ϵ}^{(n)}$ comprises a tiny fraction of ${\mathcal{X}}^n$ with size $\left|A_{ϵ}^{(n)}\right|\approx 2^{nH(X)}$.

In fact, $A_{ϵ}^{(n)}$ is an exponentially smaller than ${\mathcal{X}}^n$, as indicated by the ratio of their sizes, except when $\mathrm{X}$ is uniformly distributed. $$\begin{array}{rl}\frac{\left|A_{ϵ}^{(n)}\right|}{\left|{\mathcal{X}}^n\right|}& \approx \frac{2^{nH(X)}}{r^n}\\ & =\frac{2^{nH(X)}}{2^{n\log r}}\\ & =2^{-n(\log r-H(X))}.\end{array}$$

Despite the small size of $A_{ϵ}^{(n)}$, the probabilistic mass in ${\mathcal{X}}^n$ is almost entirely concentrated in $A_{ϵ}^{(n)}$. The forthcoming theorem illustrates the point that any subset of ${\mathcal{X}}^n$ that's smaller than $A_{ϵ}^{(n)}$ fails to capture almost all of its probabilistic mass. Thus, $A_{ϵ}^{(n)}$ is minimal.

Theorem: $A_{ϵ}^{(n)}$ is minimal

Theorem: Fix $\delta >0$ and $B_{\delta }^{(n)}\subseteq {\mathcal{X}}^n$ such that $\left|B_{\delta }^{(n)}\right|\le 2^{n(H(X)-\delta )}$. Then $$\begin{array}{}\text{(11)}& \underset{n\to \mathrm{\infty }}{lim}P(X^n\in B_{\delta }^{(n)})=0\end{array}$$

Proof

$$ $$\begin{array}{rl}& P(X^n\in B_{\delta }^{(n)})\\ \text{(12)}& & =P(X^n\in B_{\delta }^{(n)}\cap A_{ϵ}^{(n)})+P(X^n\in B_{\delta }^{(n)}\cap \complement A_{ϵ}^{(n)})\text{(13)}& & \le P(X^n\in B_{\delta }^{(n)}\cap A_{ϵ}^{(n)})+P(X^n\notin A_{ϵ}^{(n)})\text{(14)}& & =\sum _{X^n\in B_{\delta }^{(n)}\cap A_{ϵ}^{(n)}}P\left(X^n\right)+P(X^n\notin A_{ϵ}^{(n)})\text{(15)}& & \le \sum _{u^n\in B_{\delta }^{(n)}\cap A_{ϵ}^{(n)}}{2}^{-n(H(X)-ϵ)}+P(X^n\notin A_{ϵ}^{(n)})\text{(16)}& & =|B_{\delta }^{(n)}\cap A_{ϵ}^{(n)}|\cdot 2^{-n(H(X)-ϵ)}+P(X^n\notin A_{ϵ}^{(n)})\text{(17)}& & \le \left|B_{\delta }^{(n)}\right|\cdot 2^{-n(H(X)-ϵ)}+P(X^n\notin A_{ϵ}^{(n)})\text{(18)}& & \le 2^{n(H(X)-\delta )}\cdot 2^{-n(H(X)-ϵ)}+P(X^n\notin A_{ϵ}^{(n)})\text{(19)}& & =\underset{\to 0\text{ as }n\to \mathrm{\infty }}{\underbrace{2^{-n(\delta -ϵ)}}}+\underset{\to 0\text{ as }n\to \mathrm{\infty }}{\underbrace{P(X^n\notin A_{ϵ}^{(n)})}}\end{array}$$ $$

Explaination:

1. $\text{(12)}$ is derived from a basic theorem of sets. That is, given arbitary sets $B,A$, $$\begin{array}{}\text{(20)}& B=(B\cap A)\cup (B\cup \complement A)\end{array}$$ The proof is in appendix.

   Then, we have $$B_{\delta }^{(n)}=(B_{\delta }^{(n)}\cap A_{ϵ}^{(n)})\cup (B_{\delta }^{(n)}\cap (\complement A_{ϵ}^{(n)})$$

2. $\text{(13)}$ is because given arbitary sets $A,B$, $$A\cap B\subseteq A$$ Then we have $$B_{\delta }^{(n)}\cap \complement A_{ϵ}^{(n)}\subseteq \complement A_{ϵ}^{(n)}$$ And we also know $X^n\in \complement A_{ϵ}^{(n)}=X^n\notin A_{ϵ}^{(n)}$.

   Then $$P(X^n\in B_{\delta }^{(n)}\cap \complement A_{ϵ}^{(n)})\le P(X^n\notin A_{ϵ}^{(n)})$$

3. $\text{(14)}$ is because all $X^n$ are independent? //TODO

4. $\text{(15)}$ is due to $\text{(5)}$.

5. $\text{(16)}$ is a common computation.

6. $\text{(17)}$ is because given arbitary sets $A,B$, $$A\cap B\subseteq A$$ Then we have $$(B_{\delta }^{(n)}\cap A_{ϵ}^{(n)})\subseteq B_{\delta }^{(n)}$$

7. $\text{(18)}$ is due to the prerequisite $\left|B_{\delta }^{(n)}\right|\le 2^{n(H(X)-\delta )}$.

8. The limit in $\text{(18)}$ is easy to understand. Because $$\mathrm{\forall }ϵ>0,P(X^n\in A_{ϵ}^{(n)})\stackrel{n\to \mathrm{\infty }}{⟶}1$$ Then we have $$\mathrm{\forall }ϵ>0,P(X^n\notin A_{ϵ}^{(n)})\stackrel{n\to \mathrm{\infty }}{⟶}0$$

From the theorems proven above, we understand $A_{ϵ}^{(n)}$ as a subset of ${\mathcal{X}}^n$ that most efficiently contains virtually all of the source sequences that can be drawn from ${\mathcal{X}}^n$. The following section confirms the intuition that, when developing a scheme which encodes sequences from ${\mathcal{X}}^n$, we should focus our efforts towards the sequences that lie in $A_{ϵ}^{(n)}$.

Appendix

• Proof of $\text{(20)}$ "Given arbitary sets $A,B$, $B=(B\cap A)\cup (B\cup \complement A)$":

  • Inclusion ($\subseteq$):

    Let $x$ be an arbitrary element in $B$. We want to show that $x$ is also in the right-hand side of the equation.

    • If $x\in B\cap A$: $x$ is in the intersection of $B$ and $A$.
    • If $x\in B\cap \complement A$: $x$ is in the intersection of $B$ and the complement of $A$.

    Therefore, $B\subseteq (B\cap A)\cup (B\cup \complement A)$.

  • Inclusion ($\supseteq$):

    Let $y$ be an arbitrary element in $(B\cap A)\cup (B\cup \complement A)$. We want to show that $y$ is also in $B$.

    • If $y\in B\cap A$: $y$ is in the intersection of $B$ and $A$, so yy is in $B$.
    • If $y\in B\cap \complement A$: $y$ is in the intersection of $B$ and the complement of $A$, so $y$ is in $B$.

    Since $y$ could be in either $B\cap A$ or $B\cap \complement A$, we can conclude that $y$ is in $B$.

    Therefore, $(B\cap A)\cup (B\cup \complement A)\subseteq B$.

    Combining both inclusions, we have $B=(B\cap A)\cup (B\cup \complement A)$.