漸近等同分割特性

在資訊理論中，漸近等同分割特性（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。