漸近等同分割特性

在信息論中，漸近等同分割特性（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})|.}$$

參見

• 克拉默定理（大偏差）
• 噪聲信道編碼定理
• 香農信源編碼定理