渐近等同分割特性

在信息论中，渐近等同分割特性（Asymptotic equipartition property，简称AEP）是随机源输出样本的普遍性质，它是数据压缩理论中典型集概念的基础。

简言之，该定理指出：尽管随机过程可能产生多种结果序列，但实际出现的结果极大概率来自一个松散定义的集合——该集合中所有结果成为现实的可能性基本均等（这是大数定律与遍历理论的推论）。尽管存在某些单个结果的概率高于此集合中的任意结果，但集合内庞大的结果数量几乎保证了最终结果必将源自该集合。克莱默大偏差定理为理解该特性提供了一种直观路径：偏离均值的程度越大，其概率随样本数量增加呈指数级衰减（这类现象由大偏差理论专门研究）。直观来说，大偏差现象可能违背等概率分配原则，但这类情况几乎不可能发生。

在伪随机数生成领域，如果候选生成器的输出序列质量不确定，且根据某些统计标准，其输出序列偏离典型值过远，则会被视为随机性不足而遭到拒绝。因此，尽管典型值的定义较为宽泛，但在实际应用中，关于充分典型性的概念已逐渐兴起。

## 定义

给定一个概率空间$(\Omega, B, p)$ 上的离散时间平稳遍历随机过程$X$，渐近均分性质断言：几乎必然，对于所有离散时间平稳过程（包括遍历过程）都有$n\to\infty$时，$$-\frac{1}{n} \log p(X_1, X_2, \dots, X_n) \to H(X)$$其中$H(X)$（简写为$H$）表示$X$的熵率。对于有限值（即$|\Omega| < \infty$ ) 平稳遍历随机过程的情况，渐近均分性质在香农-麦克米伦-布莱曼定理中使用遍历理论得以证明。对于任何独立同分布源，不论是在离散值情况下（其中$H$仅仅是符号的熵）还是在连续值的情况下（其中$H$是微分熵），该性质都可以直接使用大数定律得以证明。（见下文）渐近均分性质的定义也可以扩展到某些连续时间随机过程，这些过程在足够长的观察时间内存在一个典型集。在所有情况下，收敛性被证明是几乎必然的。

## 离散时间独立同分布源

令$X$是一个可以采用字母表$\mathcal{X}$中的值的独立同分布源，其时间序列$X_1,\ldots,X_n$独立同分布，熵为$H(X)$。可以由弱大数定律得到依概率收敛渐近均分性质，即$$\forall \varepsilon > 0, \qquad \lim_{n\to\infty}\Pr\left[\left|-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n) - H(X)\right|> \varepsilon\right]=0 .$$这是因为熵等于$$-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n).$$的期望。

强大数定律断言了更强的结论，$$-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n)$$几乎必然收敛于熵，即$$\Pr\left[\lim_{n\to\infty} - \frac{1}{n} \log p(X_1, X_2,\ldots, X_n) = H(X)\right]=1.$$L1意义上的趋同表明$$\mathbb{E} \left[\left|\lim_{n\to\infty} - \frac{1}{n} \log p(X_1, X_2,\ldots, X_n) - H(X)\right|\right]= 0$$

## 离散时间有限值平稳遍历源

下面考虑有限值样本空间$\Omega$的情况，即$|\Omega| < \infty$，对于在概率空间$(\Omega, B, p)$上定义的离散时间平稳遍历过程$X:=\{X_n\}$，由克劳德·香农、布罗克韦·麦克米伦和利奥·布莱曼提出的香农-麦克米伦-布莱曼定理指出，$$-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n).$$在L1意义上收敛于熵。钟开来将此定理推广到以下情况：$X$可以在可数无穷大集合中取值，前提是熵率仍然是有限的。

- 设x表示某个可测集，其中$A \in B$，$x = X(A)$.
- 将联合概率用n和x参数化为$$j(n,x):=p\left(x_0^{n-1} \right).$$
- 将条件概率用i，k和x参数化为$$c(i,k,x) := p \left (x_i\mid x_{i-k}^{i-1} \right).$$
- 取条件概率在k → ∞时的极限，并将其表示为$$c(i,x):=p \left(x_i\mid x_{-\infty}^{i-1} \right ).$$
- 论证$$\lim_{n\to\infty} \frac{1}{n} \mathrm{E}[-\log j(n,X)]\quad \text{and} \quad \lim_{n\to\infty} \mathrm{E}[-\log c(n,n,X)]$$两种熵率存在，且对于包括平稳遍历过程X内的任何平稳过程相等.记为H.
- 论证$$\begin{align} c(i,k,X) &:= \left \{p \left(X_i\mid X_{i-k}^{i-1} \right ) \right \} \\ c(i,X) &:= \left \{p \left (X_i\mid X_{-\infty}^{i-1} \right ) \right \} \end{align}$$均为平稳遍历过程，其中i是时间指标，其样本均值几乎必然收敛到某些值，分别用$H^k$和$H^{\infty}$表示.
- 将概率的k阶马尔可夫近似$a(n,k,x)$定义为 $$a(n,k,x) := p \left(X_0^{k-1} \right) \prod_{i=k}^{n-1}p \left (X_i\mid X_{i-k}^{i-1} \right )=j(k,x)\prod_{i=k}^{n-1} c(i,k,x)$$.
- 从有限值假设论证$a(n,k,X(\Omega))$是有限的.
- 用$c(i,k,X)$的样本均值来表示$-\frac1n\log a(n,k,X)$，并证明其几乎必然收敛到Hk.
- 定义概率测度$$a(n,x):=p \left (x_0^{n-1}\mid x_{-\infty}^{-1} \right ).$$
- 用$c(i,X)$的样本均值表示$-\frac1n\log a(n,X)$并证明其几乎必然收敛到H∞.
- 利用过程的平稳性，论证k → ∞时$H^k\searrow H$.
- 利用Lévy鞅收敛定理和有限值假设论证H = H∞.
- 证明$$\mathrm{E}\left[\frac{a(n,k,X)}{j(n,X)}\right]=a(n, k,X(\Omega))$$如前所述，它是有限的.
- 通过以无穷历史$X_{-\infty}^{-1}$为条件并迭代期望，证明$$\mathrm{E}\left[\frac{j(n,X)}{a(n,X)}\right]=1$$.
- 使用马尔可夫不等式和先前推导出的期望证明$$\forall \alpha\in\mathbb{R} \ : \ \Pr\left[\frac{a(n,k,X)}{j(n,X)}\geq \alpha \right]\leq \frac{a(n, k,X(\Omega))}{\alpha}$$.
- 类似地，证明$$\forall \alpha\in\mathbb{R} \ : \ \Pr\left[\frac{j(n,X)}{a(n,X)}\geq \alpha \right]\leq \frac{1}{\alpha},$$该式等价于$$\forall \alpha\in\mathbb{R} \ : \ \Pr\left[\frac1n\log\frac{j(n,X)}{a(n,X)}\geq \frac{1}{n}\log\alpha \right]\leq \frac{1}{\alpha}.$$
- 设对于任意β > 1，α = nβ，应用波莱尔-坎泰利引理，证明$$\frac1n \log \frac{a(n,k,X)}{j(n,X)} \quad \text{and} \quad \frac{1}{n} \log\frac{j(n,X)}{a(n,X)}$$的上确界几乎肯定为非正的.
- 通过分解前面结果中的对数，证明$$-\frac{1}{n} \log j(n,X)$$的上下确界分别由H∞和 Hk约束.
- 通过指出当k→∞时上限和下限趋近于H来完成证明.

## 产生独立符号的非平稳离散时间源

平稳性/遍历性/随机变量同分布的假设对于渐近均分性质的成立并非必要条件。事实上，正如直观上显而易见的那样，渐近均分性质只需要某种形式的大数定律成立，这相当具有普遍性。但在这种情况下，渐进等同分割性质的表达式需要适当推广，条件也需要精确地表述。

考虑一个产生独立符号的源，该源每个时刻可能输出不同的统计量，并且该过程的统计量完全已知，也就是说，该过程在每个时刻的边际分布是已知的。联合分布就是边际分布的乘积。然后，在以下条件下（可以放宽）：对于所有i，都有$\mathrm{Var}[\log p(X_i)]<M$，对于某些M>0，下式（AEP）成立： $$\lim_{n\to\infty}\Pr\left[\,\left|-\frac{1}{n} \log p(X_1, X_2, \ldots, X_n) - \overline{H}_n(X)\right|< \varepsilon\right]=1\qquad \forall \varepsilon > 0$$其中$$\overline{H}_n(X)=\frac{1}{n}H(X_1,X_2,\ldots,X_n)$$ 该项证明是由马尔可夫不等式的一个简单应用导出的（应用于$\log(p(X_i)$的二阶矩）.

$$\begin{align} \Pr \left[\left|-\frac{1}{n} \log p(X_1, X_2,\ldots, X_n) -\overline{H}(X)\right|> \varepsilon\right] &\leq \frac{1}{n^2 \varepsilon^2} \mathrm{Var} \left [\sum_{i=1}^n \left(\log(p(X_i) \right)^2 \right ]\\ &\leq \frac{M}{n \varepsilon^2} \to 0 \text{ as } n\to \infty \end{align}$$

显然，若任意矩$\mathrm{E} \left [|\log p(X_i)|^r \right ]$对r>1一致有界（同样由应用于第r个矩的马尔可夫不等式导出）. Q.E.D.

上述条件其实也不是必要的，但给定一个非平稳随机过程，使用上述方法检验渐进等同分割性质会比较容易。

### 应用

非平稳离散时间独立过程的渐近均分性质可以推导出非平稳源（具有独立输出符号）的信源编码定理和非平稳无记忆信道的噪声信道编码定理，还能推导出一些其他的结论。

## 测度论形式

$T$是概率空间$\Omega$上的一个保测度映射。

如果$P$是$\Omega$的有限或可数划分，那么它的熵为$H(P) := -\sum_{p \in P} \mu(p) \ln\mu(p)$，习惯上规定$0\ln 0 = 0$。

我们只考虑熵有限的划分，亦即$H(P) < \infty$。

若$P$是$\Omega$的有限或可数划分，我们通过迭代映射构建一个划分序列： $$<pre> P^{(n)} := P \vee T^{-1}P \vee \dots \vee T^{-(n- 1)}P$$其中$P \vee Q$是最小上界划分，即能细化$P$和$Q$的最低细化划分： $$P\vee Q := \{p \cap q: p \in P, q \in Q\}$$记$x$所处的$P$中的集合为$P(x)$。例如，$P^{(n)}(x)$是$x$的$(P, T)$名称的前$n$符号初始段。

如果我们知道$x$落在划分$P$的哪个元素中，令$I_{P}(x)$为我们可以恢复的关于$x$的信息量（以纳特为单位）： $$I_{P} := -\ln \mu(P(x))$$类似地，划分$P$以划分$Q$为条件关于$x$的条件信息是$$I_{P|Q}(x) := -\ln \frac{P\vee Q(x)}{Q(x)}$$ $h_T(P)$是Kolmogorov-Sinai熵（测度论熵）$$<pre> h_T(P) := \lim_n \frac 1n H(P^{(n)}) = \lim_n E_{x\sim \mu}\left[\frac 1n I_{P^{(n)}}(x)\right]$$换句话说，根据定义，期望存在收敛。SMB定理指出，当$T$是遍历的，在L1中收敛。

若$T$是遍历的，则$$x \mapsto \frac 1n I_{P^{(n)}}(x)$$在L1中收敛于常数函数$x \mapsto h_T(P)$. 换而言之，$$E_{x\sim \mu}\left[ \left|\lim_n \frac 1n I_{P^{(n)}}(x) - h_T(P)\right|\right] = 0$$. 特别的，由于L1收敛意味着几乎必然收敛，以概率1$$h_T(P) = \lim_n \frac 1n I_{P^{(n)}}(x)$$.$\forall \epsilon > 0, \exists N, \forall n \geq N$，我们可以将划分$\vee_{k=0}^{n-1} T^{-k}P$分成两部分，“好（good）”部分$G$和“坏（bad）”部分 $B$. 坏的部分很小：$$\sum_{b \in B}\mu(b) < \epsilon$$ 好的部分根据熵几乎均分：$$\forall g\in G, \quad -\frac 1n \ln \mu(g) \in h_T(P) \pm \epsilon$$

如果𝑇不一定具有遍历性，那么基础概率空间将被分解为多个在𝑇下不变的子集。在这种情况下，我们仍能获得向某个函数的L1收敛，但该函数不再是一个常值函数。

设$\mathcal I$是由$\Omega$的所有$T$-不变子集生成的σ-代数$$<pre> x \mapsto \frac 1n I_{P^{(n)}}(x)$$L1收敛至

$$<pre> x \mapsto E\left[\lim_n I_{P | \vee_{k = 1}^n T^{-k}P} \big|\; \mathcal I \right]$$

当$T$遍历时， $\mathcal I$是平凡的，所以函数$$<pre> x \mapsto E\left[ \lim_n I_{P | \vee_{k = 1}^n T^{-k}P} \big|\; \mathcal I \right]$$简化为常数函数$x\mapsto E\left[ \lim_n I_{P | \vee_{k = 1}^n T^{-k}P} \right]$，根据定义，上式等于$\lim_n H(P | \vee_{k = 1}^n T^{-k}P)$，根据命题，它等于$h_T(P)$。

## 连续时间平稳遍历源

离散时间函数可以插值为连续时间函数。若此类插值函数f可测，则我们可将插值后的连续时间平稳过程定义为$\tilde{X}:=f\circ X$。若离散时间过程（如上文所示的独立同分布或有限值平稳遍历情形）满足渐近等同分割特性，则该特性自然地适用于通过可测插值导出的连续时间平稳过程，即$$-\frac{1}{n} \log p(\tilde{X}_0^\tau) \to H(X)$$其中n对应于时间τ的自由度。nH(X)/τ和H(X)是分别香农定义的单位时间熵和单位自由度熵。

此类连续时间平稳过程的一个重要类别是带限平稳遍历过程，其样本空间是连续$\mathcal{L}_2$函数的子集。若该过程为白过程（此时时间样本呈独立同分布），或存在T > 1/2W（其中W为标称带宽）使得T间隔时间样本取值于有限集合（此时转化为离散时间有限值平稳遍历过程），则渐近等同分割特性成立。

任何时不变操作也会保留渐近均分性质、平稳性和遍历性，并且我们可以通过消除过程中有限数量的时间样本，轻松地将平稳过程转变为非平稳过程，而不会丢失渐近均分性质。

## 范畴论

格罗莫夫给出了渐近等同分割特性的范畴论定义。给定测度空间P的笛卡尔幂序列$P^N=P\times \cdots \times P$，该序列允许一个渐近等价的齐性测度空间序列HN （即所有集合具有相同的测度；所有态射在自同构群下不变，因此可分解为指向终对象的态射）。

上述内容需要定义渐近等价性。该定义通过一个距离函数给出，用于度量单射对应与同构之间的差异。单射对应$\pi: P\to Q$是一个部分定义的双射映射；也就是说，它是子集$P'\subset P$和$Q'\subset Q$之间的双射。然后定义$$|P-Q|_\pi = |P \setminus P'| + |Q \setminus Q'|,$$其中|S|表示集合S的测度。在下文中，默认P和Q的测度取1，因此这些测度空间都是概率空间。该距离$|P-Q|_\pi$通常被称为动土距离或沃瑟斯坦度量。

类似地，定义$$|\log P:Q|_\pi = \frac{\sup_{p\in P'}|\log p - \log \pi(p)|}{\log \min \left(|\operatorname{set}(P')|,|\operatorname{set}(Q')|\right)}.$$其中$|\operatorname{set}(P)|$被视为P上的计数测度。因此，此定义要求P为有限测度空间。最后，令$$\text{dist}_\pi(P,Q) = |P-Q|_\pi +|\log P:Q|_\pi.$$

那么当$$\text{dist}_{\pi_N}(P_N,Q_N) \to 0 \quad\text{ as }\quad N\to\infty.$$时，单射对应$\pi_N:P_N\to Q_N$是渐近等价的。

给定一个渐近等价于PN的齐次空间序列HN，则P的熵H(P)可以取为$$H(P) = \lim_{N\to\infty}\frac{1}{N} |\operatorname{set}(H_N)|.$$

## 参考文献

### 期刊文章

- 克劳德·E·香农。“ 通信的数学理论”。贝尔系统技术期刊，1948年7/10月。
- Sergio Verdú和Te Sun Han。“ 渐近均分性质在无噪声源编码中的作用”。IEEE信息理论汇刊， 43 (3): 847–857，1997 年。doi : 10.1109/18.568696。