茶年 · 中文维基百科

渐近等同分割特性

Wikipedia · 2026-06-01 维基百科 👁 1 阅读

在信息论中，渐近等同分割特性（，簡稱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| ) 平稳遍历随机过程的情况，渐近均分性质在香农-麦克米伦-布莱曼定理中使用遍历理论得以证明。对于任何独立同分布源，不论是在离散值情况下（其中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).的期望。钟开来将此定理推广到以下情况：X可以在可数无穷大集合中取值，前提是熵率仍然是有限的。
{{Math proof|title=证明简述

{{Math theorem
| math_statement = 若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收敛意味着几乎必然收敛，以概率1h_T(P) = \lim_n \frac 1n I_{P^{(n)}}(x).
| name = 定理
| note = 遍历情形
}}{{Math theorem
| math_statement = \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)

好的部分根据熵几乎均分：
\forall g\in G, \quad -\frac 1n \ln \mu(g) \in h_T(P) \pm \epsilon

| name = 推论
| note = 熵均分性质
}}

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

{{Math theorem
| math_statement = 设\mathcal I是由\Omega的所有T-不变子集生成的σ-代数

x \mapsto \frac 1n I_{P^{(n)}}(x)
L1收敛至

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

| name = 定理
| note = 一般情形
}}

当T遍历时， \mathcal I是平凡的，所以函数
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对应于时间的自由度。和是分别香农定义的单位时间熵和单位自由度熵。

此类连续时间平稳过程的一个重要类别是带限平稳遍历过程，其样本空间是连续\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)|.

参见

  • 克拉默定理（大偏差）
  • 噪声信道编码定理
  • 香农信源编码定理

注释
参考文献
期刊文章

教科书
*
*

#信息论 #统计定理

评论 (0)

  • 还没有评论，来抢沙发吧。