Asymptotic Equipartition Property - AEP

In information theory, the analog of the law of large numbers is the asymptotic equipartition property (AEP). It is a direct consequence of the weak law of large numbers.

Asymptotic Equipartition Property Theorem

AEP theorem

AEP. If $X_1,X_2,\dots X_n$ are i.i.d. $\sim p(x)$ , then

$$-\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)\stackrel{p}{\to }H(X)$$

Proof. Functions of independent random variables are also independent random variables. Thus, since the $X_i$ are i.i.d., so are $\log p(X_i)$. Hence, by the weak law of large numbers

$$\begin{array}{rl}-\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)& =-\frac{1}{n}\sum _i\log p(X_i)\\ & \stackrel{p}{\to }-\mathbb{E}\left[\log p(X)\right]\\ & =H(X)\end{array}$$

Typical set

The typical set $A_{ϵ}^{(n)}$ with respect to $p(x)$ is the set of sequences $(x_1,x_2,\dots ,x_n)\in {\mathcal{X}}^n$ with the property

$$2^{-n(H(X)+ϵ)}\le p(x_1,x_2,\dots ,x_n)\le 2^{-n(H(X)-ϵ)}$$

As consequence of the AEP, we can show that the set $A_{ϵ}^{(n)}$ has the following properties:

1. If $(x_1,x_2,\dots ,x_n)\in A_{ϵ}^{(n)}$, then $H(X)-ϵ\le -\frac{1}{n}\log p(x_1,\dots ,x_n)\le H(X)+ϵ$
2. $P(A_{ϵ}^{(n)})\ge 1-ϵ$ for $n$ sufficiently large.
3. $\left|A_{ϵ}^{(n)}\right|\le 2^{n(H(X)+ϵ)}$, where $\left|A\right|$ denotes the number of elements in the set $A$.
4. $\left|A_{ϵ}^{(n)}\right|\ge (1-ϵ)2^{n(H(X)-ϵ)}$ for $n$ sufficiently large.

Thus, the typical set has probability nearly $1$, all elements of the typical set are nearly equiprobable, and the number of elements in the typical set is nearly $2^{nH}$

Consequences of the AEP : Data Compression

Let $X_1,X_2,\dots ,X_n$ be independent, identically distributed random variables drawn from the probability mass function $p(x)$. We wish to find short descriptions for such sequences of random variables. We divide all sequences in ${\mathcal{X}}^n$ into two sets: the typical set $A_{ϵ}^{(n)}$ and its complement.

We order all elements in each set according to some order (e.g. lexicographic order). Then we can represent each sequence of $A_{ϵ}^{(n)}$ by giving the index of the sequence in the set. Since there are $\le 2^{n(H(X)+ϵ)}$ sequences in $A_{\epsilon }^{(n)}$, the indexing requires no more than $n(H+ϵ)+1$ bits (the extra bit may be necessary because $n(H+ϵ)$ may not be an integer). We prefix all these sequences by a $0$, giving a total length of $\le n(H+ϵ)+2$ bits. Similarly, we can index each sequence not in $A_{ϵ}^{(n)}$ by using not more than $n\log \left|\mathcal{X}\right|+1$ bits. Prefixing these indices by $1$, we have a code for all the sequences in ${\mathcal{X}}^n$.

We use the notation $x^n$ to denote a sequence $x_1,\dots ,x_n$. Let $l(x^n)$ be the length of the codeword corresponding to $x^n$. If $n$ is sufficiently large so that $P(A_{ϵ}^{(n)})$, the expected length of the codeword is

$$\begin{array}{rl}\mathbb{E}\left[l(X^n)\right]& =\sum _{x^n}p(x^n)l(x^n)\\ & =\sum _{x^n\in A_{ϵ}^{(n)}}p(x^n)l(x^n)+\sum _{x^n\in {A_{ϵ}^{(n)}}^c}p(x^n)l(x^n)\\ & \le \sum _{x^n\in A_{ϵ}^{(n)}}p(x^n)(n(H+\epsilon )+2)+\sum _{x^n\in {A_{ϵ}^{(n)}}^c}p(x^n)(n\log \left|\mathcal{X}\right|+2)\\ & =P(A_{ϵ}^n)(n(H+\epsilon )+2)+P({A_{ϵ}^{(n)}}^c)(n\log \left|\mathcal{X}\right|+2)\\ & \le n(H+ϵ)+ϵn(\log \left|\mathcal{X}\right|)+2\\ & =n(H+{ϵ}^{\prime })\end{array}$$

where ${ϵ}^{\prime }=ϵ+ϵ\log \left|\mathcal{X}\right|+\frac{2}{n}$ can be made arbitrarily small by an appropriate choice of $ϵ$ followed by an appropriate choice of $n$. Now we can have the following theorem

Let $X^n$ be i.i.d. $\sim p(x)$. Let $ϵ>0$. Then there exists a code that maps sequences $x^n$ of length $n$ into binary strings such that the mapping is one-to-one (and therefore invertible) and

$$\mathbb{E}\left[\frac{1}{n}l(X^n)\right]\le H(X)+ϵ$$

for $n$ sufficiently large. Thus, we can represent sequences $X^n$ using $nH(X)$ bits on the average.

High-Probability Sets and the Typical Set

It's clear that $A_{ϵ}^{(n)}$ is a fairly small set that contains most of the probability. But from the definition, it is not clear whether it si the smallest such set. We will prove that the typical set has essentially the same number of elements as the smallest set, to first order in the exponent.

For each $n=1,2,\dots$, let $B_{\delta }^{(n)}\subset {\mathcal{X}}^n$ be the smallest set with

$$P(B_{\delta }^{(n)})\ge 1-\delta$$

We argue that $B_{\delta }^{(n)}$ must have significant intersection with $A_{ϵ}^{(n)}$ and therefore must have about as many elements.

Let $X_1,X_2,\dots ,X_n$ be i.i.d. $\sim p(x)$. For $\delta <\frac{1}{2}$ and any ${\delta }^{\prime }>0$, if $P(B_{\delta }^{(n)})>1-\delta$, then

$$\frac{1}{n}\log \left|B_{\delta }^{(n)}\right|>H-{\delta }^{\prime },\text{for n sufficiently large}$$

Thus, $B_{\delta }^{(n)}$ must have at least $2^{nH}$ elements, to first order in the exponent. But $A_{ϵ}^{(n)}$ has $2^{n(H\pm ϵ)}$ elements. Therefore, $A_{ϵ}^{(n)}$ is about the same size as the smallest high-probability set.

Q & A

AEP和典型集

核心思想: 渐近均分割特性 (AEP)

理解典型集首先要理解 AEP 定理. AEP 定理告诉我们, 对于一个由独立同分布 (i.i.d.) 随机变量组成的很长的序列 $X_1,X_2,\dots ,X_n$ (每个变量都遵循概率分布 $p(x)$ ), 那么这个序列的实际联合概率 $p(X_1,X_2,\dots ,X_n)$ 会非常接近一个特定的值 $2^{-nH(X)}$ .

更准确地说, 表达式 $-\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)$ 会随着 $n$ 的增大, 在概率上收敛于香农熵 $H(X)$ . 这意味着, 对于任意小的 $ϵ>0$ , 当 $n$ 足够大时, 下式成立的概率非常接近 1:

$$\left|-\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)-H(X)\right|\le ϵ$$

这个不等式可以改写为:

$$H(X)-ϵ\le -\frac{1}{n}\log p(X_1,X_2,\dots ,X_n)\le H(X)+ϵ$$

两边乘以 $-n$ (注意不等号方向改变):

$$-n(H(X)+ϵ)\le \log p(X_1,X_2,\dots ,X_n)\le -n(H(X)-ϵ)$$

取以 2 为底的指数 (假设 $\log$ 是指 ${\log }_2$ , 这在信息论中很常见, 并且与定义中的 $2$ 的幂次一致):

$$2^{-n(H(X)+ϵ)}\le p(X_1,X_2,\dots ,X_n)\le 2^{-n(H(X)-ϵ)}$$

典型集的定义 典型集 $A_{ϵ}^{(n)}$ 正是包含了所有满足上述 AEP 结果 (在 $ϵ$ 容忍度内) 的具体序列 $(x_1,x_2,\dots ,x_n)$ 的集合. 也就是说, 一个序列 $(x_1,\dots ,x_n)$ 属于典型集 $A_{ϵ}^{(n)}$ , 当且仅当它的联合概率 $p(x_1,\dots ,x_n)$ 满足:

$$2^{-n(H(X)+ϵ)}\le p(x_1,x_2,\dots ,x_n)\le 2^{-n(H(X)-ϵ)}$$

直观上讲, 典型集就是那些 "看起来像是" 从 $p(x)$ 分布中生成的、具有 "预期" 概率的序列的集合.

典型集的关键性质 材料中列出的四个性质进一步阐明了典型集的特点:

1. 等价定义: 性质 1 只是将典型集定义的概率不等式转换回 AEP 定理中更常见的对数概率形式. 它确认了典型集中的序列确实是那些满足 AEP 条件的序列.
2. 高概率性: $P(A_{ϵ}^{(n)})\ge 1-ϵ$ (当 $n$ 足够大时). 这是 AEP 定理 (依概率收敛) 的直接结果. 它意味着, 如果你随机生成一个长序列 $X_1,\dots ,X_n$ , 这个序列落在典型集内的概率非常高 (接近 1). 绝大多数可能的序列都在典型集里.
3. 大小上界: $|A_{ϵ}^{(n)}|\le 2^{n(H(X)+ϵ)}$ . 典型集的大小 (包含的序列数量) 不会太大. 总共有 $|\mathcal{X}{|}^n$ 个可能的序列 (其中 $|\mathcal{X}|$ 是单个符号的字母表大小), 而典型集的数量级大约是 $2^{nH(X)}$ . 因为 $H(X)\le {\log }_2|\mathcal{X}|$ (通常严格小于, 除非是均匀分布), 所以典型集通常只占所有可能序列的很小一部分.
4. 大小下界: $|A_{ϵ}^{(n)}|\ge (1-ϵ)2^{n(H(X)-ϵ)}$ (当 $n$ 足够大时). 结合上界, 这表明典型集的大小确实非常接近 $2^{nH(X)}$ .

总结典型集的特点:

• 高概率: 几乎所有随机生成的序列都属于典型集.
• 小体积: 相对于所有可能的序列空间 ( ${\mathcal{X}}^n$ ), 典型集包含的序列数量相对较少 (大约 $2^{nH(X)}$ 个).
• 近似等概率: 典型集中的每个序列的概率都大致相等, 约为 $2^{-nH(X)}$ . 这是因为它们的概率都被限制在一个由 $ϵ$ 控制的狭窄区间内 $[2^{-n(H+ϵ)},2^{-n(H-ϵ)}]$ .

典型集的意义 (以数据压缩为例) AEP 和典型集的概念在信息论中至关重要, 尤其是在数据压缩方面. 其思想如下:

1. 既然几乎所有的序列都落在典型集 $A_{ϵ}^{(n)}$ 中 (性质 2), 并且这个集合相对较小 (大小约为 $2^{nH(X)}$ , 性质 3 和 4).
2. 我们可以设计一种编码方案:
   • 对于典型集中的序列: 我们只需要大约 ${\log }_2(|A_{ϵ}^{(n)}|)\approx {\log }_2(2^{nH(X)})=nH(X)$ 比特来唯一标识它们 (材料中给出的更精确的上界是 $n(H+ϵ)+1$ 比特). 我们可以给这些短码加上一个前缀 (如 '$0$').
   • 对于不在典型集中的序列: 这些序列非常罕见 (总概率小于 $ϵ$ ). 我们可以使用一种通用的、可能较长的方法来编码它们, 例如用 ${\log }_2(|\mathcal{X}{|}^n)=n{\log }_2|\mathcal{X}|$ 比特来表示 (材料中给出的上界是 $n\log |\mathcal{X}|+1$ 比特). 给这些长码加上另一个前缀 (如 '$1$').
3. 由于典型序列出现的概率极高, 这种策略的平均编码长度将非常接近 $nH(X)$ 比特, 即每个源符号平均需要 $H(X)$ 比特. 这表明 $H(X)$ 是无损压缩的理论极限.

简而言之, 典型集是一个虽然体积相对较小 (约 $2^{nH(X)}$ 个序列), 但几乎包含了所有可能发生情况 (概率接近 1) 的序列集合. 集合中的每个序列都具有大致相同的概率 (约 $2^{-nH(X)}$ ). 这个概念解释了为什么我们可以将数据压缩到接近其熵 $H(X)$ 比特/符号的程度.

---

高概率集

材料解读 我们知道典型集 $A_{ϵ}^{(n)}$ 概率很高 (接近 1) 并且大小约为 $2^{nH(X)}$ . 但它是不是达到这个高概率的 "最小" 集合呢? 也就是说, 会不会存在另一个概率同样很高的集合, 但它包含的序列数量远少于 $2^{nH(X)}$ 个? 这段话旨在说明, 典型集 $A_{ϵ}^{(n)}$ 在指数级别上, 基本上就是满足高概率条件的最小集合.

为了论证这一点, 材料引入了一个新的集合:

• $B_{\delta }^{(n)}$ : 对于给定的概率阈值 $1-\delta$ (其中 $\delta$ 是一个小的正数), $B_{\delta }^{(n)}$ 是所有 ${\mathcal{X}}^n$ 的子集中, 包含序列数量最少但其总概率 $P(B_{\delta }^{(n)})$ 至少为 $1-\delta$ 的那个集合.
  • 如何构造 $B_{\delta }^{(n)}$: 想象一下将 ${\mathcal{X}}^n$ 中的所有 $|\mathcal{X}{|}^n$ 个序列按照它们的概率 $p(x_1,\dots ,x_n)$ 从大到小排序. 然后, 从概率最大的序列开始, 依次将序列加入集合, 直到集合的总概率首次达到或超过 $1-\delta$ . 这样构成的集合就是 $B_{\delta }^{(n)}$ .

材料接着指出 $B_{\delta }^{(n)}$ 和 $A_{ϵ}^{(n)}$ 必须有显著的交集 (significant intersection). 这是因为 $A_{ϵ}^{(n)}$ 的概率接近 1 (比如 $>1-ϵ$ ), $B_{\delta }^{(n)}$ 的概率也接近 1 ( $\ge 1-\delta$ ). 两个概率都接近 1 的集合, 它们的交集的概率也必然接近 1 (至少是 $1-ϵ-\delta$ ). 这意味着它们共享了大部分高概率的序列.

核心定理及其意义 核心论证依赖于以下定理 (材料中陈述但未证明):

定理: 设 $X_1,X_2,\dots ,X_n$ 是独立同分布 $\sim p(x)$ . 对于任意 $\delta$ 使得 $0<\delta <1$ (通常我们关心 $\delta$ 很小, 例如小于 $1/2$ 如材料所述, 但这对于证明不是本质要求) 且对于任意 ${\delta }^{\prime }>0$ , 如果 $B_{\delta }^{(n)}$ 是 ${\mathcal{X}}^n$ 中满足 $P(B_{\delta }^{(n)})\ge 1-\delta$ 的最小集合, 那么当 $n$ 足够大时, 有

$$\frac{1}{n}\log \left|B_{\delta }^{(n)}\right|\ge H(X)-{\delta }^{\prime }$$

注: 原文定理用的是严格大于号 $>$ , 但用 $\ge$ 也可以说明问题, 并且更容易从下面的证明推导出来. 在 $n$ 足够大时, 两者差别不大. 原文的 $\delta <1/2$ 条件可能在某些更精细的证明或上下文中需要, 但对于我们这里的证明不是必须的. 这里假设 $\log$ 是以 2 为底的对数.

定理的意义: 这个定理说明, 即使是设计出来的最小的、能包含至少 $1-\delta$ 概率的集合 $B_{\delta }^{(n)}$ , 它的大小 $|B_{\delta }^{(n)}|$ 在指数上也必须至少是 $2^{n(H-{\delta }^{\prime })}$ . 因为 ${\delta }^{\prime }$ 可以任意小, 这意味着 $|B_{\delta }^{(n)}|$ 的增长率下界基本上由 $2^{nH(X)}$ 控制.

将定理与典型集比较: 我们知道典型集 $A_{ϵ}^{(n)}$ 的性质:

1. $P(A_{ϵ}^{(n)})\ge 1-ϵ$ (对于足够大的 $n$ )
2. $|A_{ϵ}^{(n)}|\le 2^{n(H+ϵ)}$
3. $|A_{ϵ}^{(n)}|\ge (1-ϵ)2^{n(H-ϵ)}$ (对于足够大的 $n$ )

定理告诉我们, 任何概率至少为 $1-\delta$ 的集合 (包括最小的那个 $B_{\delta }^{(n)}$ ), 其大小至少约为 $2^{nH(X)}$ . 而典型集 $A_{ϵ}^{(n)}$ 的大小也正好约为 $2^{nH(X)}$ .

结论: 这说明典型集 $A_{ϵ}^{(n)}$ 的大小与满足高概率条件的最小集合的大小, 在指数级别上是相同的 ( $nH(X)$ ). 典型集虽然不是通过 "最小化大小" 来定义的, 但它自然地实现了接近最优的大小压缩, 同时保持了极高的概率覆盖.

定理的证明 我们可以利用典型集 $A_{ϵ}^{(n)}$ 的性质来证明关于 $B_{\delta }^{(n)}$ 大小的定理. 思路是考察这两个集合的交集 $A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}$ .

1. 交集的概率下界: 我们知道 $P(A\cup B)=P(A)+P(B)-P(A\cap B)$ . 因为 $P(A\cup B)\le 1$ , 所以 $P(A\cap B)\ge P(A)+P(B)-1$ . 对于 $A_{ϵ}^{(n)}$ 和 $B_{\delta }^{(n)}$ , 当 $n$ 足够大时, $P(A_{ϵ}^{(n)})\ge 1-ϵ$ . 我们已知 $P(B_{\delta }^{(n)})\ge 1-\delta$ . 因此, 交集的概率满足:

$$P(A_{ϵ}^{(n)}\cap B_{\delta }^{(n)})\ge (1-ϵ)+(1-\delta )-1=1-ϵ-\delta$$

只要我们选择 $ϵ$ 和 $\delta$ 足够小, 使得 $ϵ+\delta <1$ , 这个交集的概率就是正的, 并且可以很接近 1.

2. 利用典型集性质限制交集概率: 考虑交集中的任意序列 $x^n=(x_1,\dots ,x_n)\in A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}$ . 因为它属于典型集 $A_{ϵ}^{(n)}$ , 根据典型集的定义 (或性质 1) , 它的概率满足:

$$p(x^n)\le 2^{-n(H(X)-ϵ)}$$

3. 联系交集概率和 $B_{\delta }^{(n)}$ 的大小: 我们可以将交集的总概率表示为其中所有序列概率的总和:

$$P(A_{ϵ}^{(n)}\cap B_{\delta }^{(n)})=\sum _{x^n\in A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}}p(x^n)$$

由于交集 $A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}$ 是 $B_{\delta }^{(n)}$ 的一个子集, 我们可以用 $B_{\delta }^{(n)}$ 中的序列数量 $|B_{\delta }^{(n)}|$ 和这些序列概率的上界来放缩:

$$\sum _{x^n\in A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}}p(x^n)\le \sum _{x^n\in A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}}{2}^{-n(H(X)-ϵ)}$$

因为 $A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}$ 中的序列个数不可能超过 $B_{\delta }^{(n)}$ 的总序列个数 $|B_{\delta }^{(n)}|$ , 所以:

$$\sum _{x^n\in A_{ϵ}^{(n)}\cap B_{\delta }^{(n)}}{2}^{-n(H(X)-ϵ)}\le |B_{\delta }^{(n)}|\cdot 2^{-n(H(X)-ϵ)}$$

结合步骤 1 的结果, 我们得到:

$$1-ϵ-\delta \le P(A_{ϵ}^{(n)}\cap B_{\delta }^{(n)})\le |B_{\delta }^{(n)}|\cdot 2^{-n(H(X)-ϵ)}$$

4. 导出 $|B_{\delta }^{(n)}|$ 的下界: 从上面的不等式, 我们可以解出 $|B_{\delta }^{(n)}|$ 的下界:

$$|B_{\delta }^{(n)}|\ge (1-ϵ-\delta )\cdot 2^{n(H(X)-ϵ)}$$

现在, 我们对两边取 $\frac{1}{n}{\log }_2$ :

$$\frac{1}{n}{\log }_2|B_{\delta }^{(n)}|\ge \frac{1}{n}{\log }_2(1-ϵ-\delta )+H(X)-ϵ$$

5. 处理极限和 ${\delta }^{\prime }$: 这个不等式对于任意满足 $ϵ+\delta <1$ 的 $ϵ>0,\delta >0$ 以及足够大的 $n$ 都成立.

我们要证明的是: 对于给定的 $\delta$ 和任意 ${\delta }^{\prime }>0$ , 当 $n$ 足够大时, $\frac{1}{n}\log |B_{\delta }^{(n)}|\ge H(X)-{\delta }^{\prime }$ . 在上面的不等式中, 当 $n\to \infty$ 时, $\frac{1}{n}{\log }_2(1-ϵ-\delta )\to 0$ (因为 ${\log }_2(\cdot )$ 是一个常数).

因此, 对于任意给定的 $ϵ>0$ , 当 $n$ 足够大时, $\frac{1}{n}{\log }_2(1-ϵ-\delta )$ 会比 $ϵ$ 小很多. 更具体地, 对于我们想要的任何 ${\delta }^{\prime }>0$ , 我们可以选择一个 $ϵ$ 使得 $0<ϵ<{\delta }^{\prime }$ . 例如, 取 $ϵ={\delta }^{\prime }/2$ (并确保 ${\delta }^{\prime }/2+\delta <1$ , 这对于小的 $\delta ,{\delta }^{\prime }$ 通常满足).

那么, 对于这个选定的 $ϵ={\delta }^{\prime }/2$ , 存在一个 $N$ , 使得对于所有 $n>N$ , 有:

$$\left|\frac{1}{n}{\log }_2(1-ϵ-\delta )\right|<ϵ(\text{即 }<{\delta }^{\prime }/2)$$

这意味着:

$$\frac{1}{n}{\log }_2(1-ϵ-\delta )>-ϵ=-{\delta }^{\prime }/2$$

代入之前的 $\frac{1}{n}{\log }_2|B_{\delta }^{(n)}|$ 的不等式:

$$\frac{1}{n}{\log }_2|B_{\delta }^{(n)}|\ge \frac{1}{n}{\log }_2(1-ϵ-\delta )+H(X)-ϵ>-ϵ+H(X)-ϵ=H(X)-2ϵ$$

将 $ϵ={\delta }^{\prime }/2$ 代入:

$$\frac{1}{n}{\log }_2|B_{\delta }^{(n)}|>H(X)-2({\delta }^{\prime }/2)=H(X)-{\delta }^{\prime }$$

这就证明了定理 (我们得到了严格大于号, 如果需要大于等于号, 论证会更宽松) .

总结证明思路: 我们利用了典型集 $A_{ϵ}^{(n)}$ 的两个核心属性: 它的概率接近 1, 并且其中每个序列的概率都有一个上界 $2^{-n(H-ϵ)}$ . 通过考察 $A_{ϵ}^{(n)}$ 和最小高概率集 $B_{\delta }^{(n)}$ 的交集, 我们可以将 $B_{\delta }^{(n)}$ 的大小 $|B_{\delta }^{(n)}|$ 与 $H(X)$ 联系起来, 最终证明 $|B_{\delta }^{(n)}|$ 的增长率下界也是由 $nH(X)$ 决定的.