渐近等同分割特性

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

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

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

定义

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

离散时间独立同分布源

令${\displaystyle X}$是一个可以采用字母表${\displaystyle {\mathcal {X}}}$中的值的独立同分布源 ，其时间序列${\displaystyle X_{1},\ldots ,X_{n}}$独立同分布，熵为${\displaystyle H(X)}$。可以由弱大数定律得到依概率收敛渐近均分性质，即$${\displaystyle \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.}$$这是因为熵等于$${\displaystyle -{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n}).}$$的期望。^[1]

强大数定律断言了更强的结论，$${\displaystyle -{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})}$$几乎必然收敛于熵， 即$${\displaystyle \Pr \left[\lim _{n\to \infty }-{\frac {1}{n}}\log p(X_{1},X_{2},\ldots ,X_{n})=H(X)\right]=1.}$$L1意义上的趋同表明$${\displaystyle \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}$$

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

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

证明简述^[3]

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

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

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

考虑一个产生独立符号的源，该源每个时刻可能输出不同的统计量，并且该过程的统计量完全已知，也就是说，该过程在每个时刻的边际分布是已知的。联合分布就是边际分布的乘积。然后，在以下条件下（可以放宽）：对于所有i，都有${\displaystyle \mathrm {Var} [\log p(X_{i})]<M}$，对于某些M>0，下式（AEP）成立： $${\displaystyle \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}$$其中$${\displaystyle {\overline {H}}_{n}(X)={\frac {1}{n}}H(X_{1},X_{2},\ldots ,X_{n})}$$

证明

该项证明是由马尔可夫不等式的一个简单应用导出的（应用于${\displaystyle \log(p(X_{i})}$的二阶矩）. $${\displaystyle {\begin{aligned}\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{aligned}}}$$

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

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

应用

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

测度论形式

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

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

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

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

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

定理 （遍历情形） — 若${\textstyle T}$是遍历的，则$${\displaystyle x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)}$$在L1中收敛于常数函数${\textstyle x\mapsto h_{T}(P)}$.

换而言之，$${\displaystyle E_{x\sim \mu }\left[\left|\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)-h_{T}(P)\right|\right]=0}$$.

特别的，由于L1收敛意味着几乎必然收敛，以概率1$${\displaystyle h_{T}(P)=\lim _{n}{\frac {1}{n}}I_{P^{(n)}}(x)}$$.

推论 （熵均分性质） — ${\textstyle \forall \epsilon >0,\exists N,\forall n\geq N}$，我们可以将划分${\textstyle \vee _{k=0}^{n-1}T^{-k}P}$分成两部分，“好（good）”部分${\textstyle G}$和“坏（bad）”部分 ${\textstyle B}$.

坏的部分很小：$${\displaystyle \sum _{b\in B}\mu (b)<\epsilon }$$

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

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

定理 （一般情形） — 设${\textstyle {\mathcal {I}}}$是由${\textstyle \Omega }$的所有${\textstyle T}$-不变子集生成的σ-代数 $${\displaystyle x\mapsto {\frac {1}{n}}I_{P^{(n)}}(x)}$$L1收敛至
$${\displaystyle x\mapsto E\left[\lim _{n}I_{P|\vee _{k=1}^{n}T^{-k}P}{\big |}\;{\mathcal {I}}\right]}$$

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

连续时间平稳遍历源

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

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

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

范畴论

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

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

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

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

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

参见

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