完整搜尋頁面 →

IT 02・典型序列、AEP 與熵率

資訊理論中階16 分鐘更新於 2026年10月4日

先備知識:IT 01・熵、相對熵與互資訊

導覽:本頁與本系列: 導覽:本頁與本系列
用實驗理解本章 1 個互動實驗

比較典型集合的機率質量與它占所有二元區塊的比例。

你將學到

  • 推導獨立有限字母來源的漸近均分性質。
  • 分別限制典型集的機率與大小,不混淆兩者。
  • 說明最可能的單一序列為何不一定具有代表性。
  • 推導平穩有限狀態 Markov 來源的熵率。
  • 用具體反例區分平穩性、獨立性與遍歷性。
  • 連結條件典型性、聯合典型性與壓縮及通訊證明。

先看全貌

單次取樣充滿不確定性,長序列的整體行為卻常相當穩定。具有偏差的二元來源,其下一個位元仍無法完全預測,但長區塊的平均描述長度往往接近固定值。典型性把這項觀察寫成精確敘述。

本章依循 Cover 與 Thomas 的第 3–4 章 [1]。Stanford 的 AEP 原始講義 [2] 提供精簡的獨立來源證明。我們會推導結果、說明有限區塊的限制,再延伸至相依來源。後續章節會把存在性論證轉成實際編碼器與解碼器。

典型性永遠相對於指定的來源分布。它不代表外觀普通、語意正確,或對每個族群都有代表性。樣本可能在錯誤的模型下具有高機率,卻仍不符合應用需求。

區塊機率與平均驚訝量

不只問一個符號有多令人意外,而是計算整個區塊的驚訝量,再除以長度。對獨立符號,這就是各符號驚訝量的平均。

設 X1,…,XnX_1,\ldots,X_n 在有限字母集 X\mathcal X 上,依機率質量函數 pp 獨立同分布。定義區塊 Xn=(X1,…,Xn)X^n=(X_1,\ldots,X_n):

p(xn)=∏i=1np(xi),Jn=−1nlog⁡2p(Xn)=1n∑i=1n−log⁡2p(Xi).p(x^n)=\prod_{i=1}^{n}p(x_i),\qquad J_n=-\frac1n\log_2p(X^n) =\frac1n\sum_{i=1}^{n}-\log_2p(X_i).

其中 nn 是區塊長度,xnx^n 是特定序列,ii 是位置,JnJ_n 是以每符號位元數表示的隨機平均驚訝量。等式利用獨立性;其期望為單一來源符號的熵 H(X)H(X)。

有限字母設定使正機率結果上的驚訝量可積分。字母集中可以包含不可能的符號,但實際取樣區塊不會出現它們。因此大數法則給出

Jn→Pr⁡H(X).J_n\xrightarrow{\Pr}H(X).

箭頭表示依機率收斂:對任何固定正容許誤差,JnJ_n 與熵的差超過該誤差的機率會趨近零。這就是漸近均分性質(asymptotic equipartition property,AEP)[1,2]。

「均分」是近似且漸近的。它不表示每個區塊都具有相同機率,也不表示所有符號最後都會等頻出現。它表示多數機率質量集中於機率具有近似相同指數尺度的區塊。

對符號一機率為 pp 的 Bernoulli 來源,含有 kk 個一的區塊滿足

−1nlog⁡2p(xn)=−knlog⁡2p−(1−kn)log⁡2(1−p).-\frac1n\log_2p(x^n) =-\frac{k}{n}\log_2p -\left(1-\frac{k}{n}\right)\log_2(1-p).

其中 kk 是觀察到的個數,k/nk/n 是經驗比例。當比例接近 pp,平均驚訝量接近二元熵 h2(p)h_2(p)。一的個數通常不會接近區塊長度的一半。

典型集:分清機率與計數

多數可能觀察到的結果能放進合理區塊的目錄。目錄內每個區塊的機率可能很低,但加總後涵蓋幾乎全部來源機率。

對容許誤差 ϵ>0\epsilon>0,定義

Aϵ(n)={xn:∣−1nlog⁡2p(xn)−H(X)∣≤ϵ}.A_\epsilon^{(n)} =\left\{x^n: \left|-\frac1n\log_2p(x^n)-H(X)\right|\leq\epsilon \right\}.

其中 Aϵ(n)A_\epsilon^{(n)} 是弱典型集,大括號內的 ∣⋅∣|\cdot| 表示絕對值,ϵ\epsilon 是以每符號位元數表示的容許誤差。其元素滿足

2−n(H(X)+ϵ)≤p(xn)≤2−n(H(X)−ϵ).2^{-n(H(X)+\epsilon)} \leq p(x^n) \leq2^{-n(H(X)-\epsilon)}.

這限制單一典型區塊的機率。AEP 另外指出 Pr⁡(Xn∈Aϵ(n))\Pr(X^n\in A_\epsilon^{(n)}) 趨近一。

當 nn 足夠大,假設典型集機率至少為 1−δ1-\delta,其中 δ>0\delta>0 是指定的機率容許誤差,則

(1−δ)2n(H(X)−ϵ)≤∣Aϵ(n)∣≤2n(H(X)+ϵ).(1-\delta)2^{n(H(X)-\epsilon)} \leq |A_\epsilon^{(n)}| \leq2^{n(H(X)+\epsilon)}.

其中 ∣Aϵ(n)∣|A_\epsilon^{(n)}| 表示典型序列的個數,而非其機率。上界來自每個典型區塊至少具有 2−n(H+ϵ)2^{-n(H+\epsilon)} 的機率,且總機率不能超過一。下界來自集合至少涵蓋 1−δ1-\delta 的機率,而各區塊機率至多為 2−n(H−ϵ)2^{-n(H-\epsilon)}。

把 ϵ\epsilon 與 δ\delta 分開,可以看清角色:前者限制描述長度的偏差,後者限制被排除的機率質量。教科書可能在選擇足夠大的區塊後,用同一個小參數表示兩者;有限長度計算仍必須區分。

總共有 ∣X∣n|\mathcal X|^n 種可能序列。若 H(X)<log⁡2∣X∣H(X)<\log_2|\mathcal X|,典型目錄的指數尺度就小得多。這是壓縮背後的計數事實:若允許很小的錯誤機率,就不必讓每個可想像的區塊都有短描述。

最可能的區塊不一定典型

單一機率最高的字串可能沒有代表性。許多單獨機率稍低的字串,加起來反而占大多數機率。

對 p=0.2p=0.2 的獨立二元來源,全零區塊是單一機率最高的區塊。其平均驚訝量為

−1nlog⁡2(0.8n)=−log⁡2(0.8).-\frac1n\log_2(0.8^n)=-\log_2(0.8).

其中 0.80.8 是零的機率。這個值與 h2(0.2)h_2(0.2) 不同。對較窄的容許誤差,全零字串一直在典型集外,即使沒有任何單一字串比它更可能。

它的總機率 0.8n0.8^n 趨近零;反之,約五分之一符號為一的區塊有非常多個,加總機率趨近一。機率質量與單一結果排名是不同的對象。

生成模型也有類似區別:最大機率序列不一定像模型的代表性樣本。典型性提供數學例子,卻不保證某個取樣演算法會產生有用語言或影像。

Bernoulli 機率 0.2 在長度 20、200、2000 下的平均區塊驚訝量直方圖;長度增加時分布集中於二元熵。
圖 1 — 每個長度產生 5,000 個合成二項取樣區塊。橘線是精確來源熵;橫軸是驚訝量,不是一的比例。

程式:精確典型機率與有限個數

第一個完整例子利用二項計數分布,將典型集機率加總至浮點運算精度。另用小區塊枚舉檢查基數界限。

程式碼 · Python · 25 行
import itertools
import numpy as np
from scipy.stats import binom

p, epsilon = 0.2, 0.1
entropy = -p * np.log2(p) - (1 - p) * np.log2(1 - p)
for n in [20, 200, 2000]:
    k = np.arange(n + 1)
    per_symbol = -(k / n) * np.log2(p) - (1 - k / n) * np.log2(1 - p)
    typical = np.abs(per_symbol - entropy) <= epsilon
    probability = binom.pmf(k, n, p)[typical].sum()
    print("Length:", n, "typical probability:", probability)

n, epsilon = 10, 0.15
count, mass = 0, 0.0
for block in itertools.product([0, 1], repeat=n):
    k = sum(block)
    probability = p**k * (1 - p)**(n - k)
    surprise = -np.log2(probability) / n
    if abs(surprise - entropy) <= epsilon:
        count += 1
        mass += probability
assert count <= 2**(n * (entropy + epsilon))
assert count >= mass * 2**(n * (entropy - epsilon))
print("Small-block typical count / mass:", count, mass)

小區塊的典型機率不一定接近一。「漸近」描述固定容許誤差下,區塊長度持續增加的行為,不代表任何長度都能套用長區塊結論。

計算例:先數字串,再加總機率

使用上方小區塊枚舉的 n=10n=10、p=0.2p=0.2、ϵ=0.15\epsilon=0.15。有 kk 個一的區塊,其每符號平均驚訝量為 0.321928+0.2k0.321928+0.2k 位元,來源熵則為 0.721928。只有 k=2k=2 符合容許誤差;我們先決定成員,再進行計數。

這些字串有 (102)=45\binom{10}{2}=45 個。每個機率為 0.22×0.88=0.00671088640.2^2\times0.8^8=0.0067108864,所以典型集機率是 45×0.0067108864=0.30198988845\times0.0067108864=0.301989888。相較之下,單一全零字串機率為 0.810=0.10737418240.8^{10}=0.1073741824。它比每個典型字串更可能,但比 45 個字串合計的機率低。

這分別回答三個問題:成員資格由驚訝量容許誤差決定,基數計算接受字串數,機率質量加總其機率。45 個字串的目錄需要六個定長索引位元,因為五位元只能區分 32 種選項。但該目錄只涵蓋這個短區塊來源約 30.2% 的機率。因此,即使碼率是每符號0.6 位元,僅靠長度十目錄仍不是好的幾乎無損編碼。

熵界限沒有失效。固定此容許誤差時,高機率結論需要更長區塊。基數取整與排除機率,是極限論證不會從短實驗中消除的成本。

若改用公平位元模型評分,同一批區塊全部恰好每符號一位元。該模型無法用驚訝量區分全零與兩個一的字串。真正來源未變,改變的是評分模型。計算典型集時,必須指定由哪個分布提供機率。

經驗頻率與組合計數直覺

區塊的符號頻率定義一群具有相同來源機率的字串。計算這一群的大小,就能說明單獨不太可能的字串為何能共同占大多數機率。

對恰好有 kk 個一的二元區塊,排列數與該計數的總機率為

Nn,k=(nk),Pr⁡(Kn=k)=(nk)pk(1−p)n−k.N_{n,k}=\binom nk,\qquad \Pr(K_n=k)=\binom nk p^k(1-p)^{n-k}.

其中 Nn,kN_{n,k} 計算字串個數,KnK_n 是隨機的一的個數,(nk)\binom nk 是二項係數,pp 是來源產生一的機率。同一計數的每種排列機率相同,但排列數差異非常大。

兩個極端分別只有一個全零與一個全一字串;中間則有大量排列。對偏差來源,每種排列的機率與排列數朝不同方向變化,乘積在接近來源期望計數處達到高值。

這也說明經驗頻率典型性與驚訝量典型性的差別。公平二元來源的每個長度 nn 字串機率都是 2−n2^{-n},平均驚訝量恰好一位元。因此任何正容許誤差下,所有可能字串都是弱典型,包括全零。

觀察到全零字串的機率仍趨近零。以頻率定義的典型集可要求一的比例接近一半,從而排除全零。它的機率也趨近一,但成員條件更嚴格。

兩種定義都沒有錯;它們用於不同證明。機率尺度敘述可能只需要弱典型性;需要匹配經驗條件分布的構造,可能必須控制頻率。務必確認證明實際使用哪個定義,尤其從邊際來源編碼轉向聯合輸入輸出關係時。

來源編碼論證與限制

將典型區塊編號,傳送其目錄索引。區塊夠長時,平均每符號使用接近熵的位元數,只在少量被排除的結果上失敗。

典型集至多有 2n(H+ϵ)2^{n(H+\epsilon)} 個成員,因此索引大致需要不超過 n(H+ϵ)n(H+\epsilon) 位元,再加取整與區塊框定的成本。解碼器用相同目錄重建所選區塊。

這是幾乎無損的定長構造,並未正確編碼所有區塊。可以保留一個額外符號表示失敗,但旗標不能重建非典型區塊。要真正無損,就必須提供足以完整還原它的逸出表示。

簡單的反向論證可說明,遠低於熵的速率為何無法涵蓋多數機率。假設編碼最多正確表示 2nR2^{nR} 個區塊,將它們與典型集取交集。每個典型區塊機率至多為 2−n(H−ϵ)2^{-n(H-\epsilon)},可接受機率質量至多為

2nR2−n(H(X)−ϵ)=2−n(H(X)−ϵ−R).2^{nR}2^{-n(H(X)-\epsilon)} =2^{-n(H(X)-\epsilon-R)}.

其中 RR 是以每來源符號位元數表示的定長編碼速率。若 R<H(X)−ϵR<H(X)-\epsilon,典型集內可接受的機率趨近零。被排除的非典型機率也趨近零,因此編碼無法以高機率重建來源。

論證假設編碼器與解碼器只有有限個不同訊息。這是計數證明,不是有效率的實作;枚舉巨大目錄通常不實際。下一章研究前綴編碼、機率編碼與自適應模型,把理論速率轉成可計算程序。

加上逸出分支,讓目錄真正無損

有時失敗的目錄,可以變成還原每個允許有限區塊的碼。先傳一位元分支旗標;區塊典型時傳定長目錄索引,否則傳逐符號固定寬度的未壓縮表示。

令 m=⌈log⁡2∣X∣⌉m=\lceil\log_2|\mathcal X|\rceil,非空典型集的索引寬度為 ℓn=⌈log⁡2∣Aϵ(n)∣⌉\ell_n=\lceil\log_2|A_\epsilon^{(n)}|\rceil。期望長度滿足

E[Ln]n=1n+PTℓnn+(1−PT)m≤2n+PT(H(X)+ϵ)+(1−PT)m.\frac{\mathbb E[L_n]}n =\frac1n+\frac{P_T\ell_n}n+(1-P_T)m \leq\frac2n+P_T(H(X)+\epsilon)+(1-P_T)m.

LnL_n 是區塊總位元長度,mm 是原始符號固定寬度,ℓn\ell_n 是典型索引寬度,PT=Pr⁡(Xn∈Aϵ(n))P_T=\Pr(X^n\in A_\epsilon^{(n)}) 是典型機率,n,ϵ,H(X)n,\epsilon,H(X) 沿用前述定義。等式計入旗標與兩分支;不等式利用典型集基數與向上取整。

解碼器先讀旗標,便知道該讀哪個固定分支長度。典型分支回傳共享目錄項目,逸出分支還原原始符號,沒有區塊被默默省略。小有限區塊的典型集若為空,先只用原始分支,直到有可用目錄。

固定 ϵ\epsilon 下,AEP 給 PT→1P_T\to1,使逸出分支的每符號貢獻消失。旗標與取整成本也隨 nn 增長而消失,期望速率因此漸近不超過 H(X)+ϵH(X)+\epsilon。先建立足夠長區塊,再選較小容許誤差,便能任意接近熵。

構造揭露定長幾乎無損與變長完全無損的差別。逸出分支在罕見區塊可能很長,後者結論因此針對期望長度,不是每個區塊都有短上界。兩端還須共享目錄與來源模型。這是速率可達證明,明確枚舉通常太昂貴,不是實用壓縮演算法。

有限區塊集中速度取決於來源

長區塊很有用,但需要多長,取決於來源與容許誤差。稀有符號可能造成很大的驚訝量波動。

對驚訝量變異數有限的獨立符號,

Var⁡(Jn)=Vn,V=Var⁡[−log⁡2p(X)].\operatorname{Var}(J_n)=\frac{V}{n}, \qquad V=\operatorname{Var}[-\log_2p(X)].

其中 VV 是來源驚訝量變異數,Var⁡\operatorname{Var} 表示變異數。結果來自獨立變異數相加再除以 n2n^2。一般變異數界限給出

Pr⁡(∣Jn−H(X)∣>ϵ)≤Vnϵ2.\Pr(|J_n-H(X)|>\epsilon)\leq\frac{V}{n\epsilon^2}.

其中 ϵ\epsilon 是前述驚訝量容許誤差。界限可能寬鬆,但明確顯示依賴關係。很小的機率可能提高驚訝量變異數;要求更窄誤差也會增加所需長度。

跨區塊的經驗標準差有用,卻不是通用的有限區塊編碼保證。相依性改變變異數計算;小規模模擬可能漏掉稀有事件;模型不匹配會改變集中位置。

若來源 pp 由模型 qq 評分,在可積分條件下,獨立區塊平均驚訝量收斂至 H(p,q)H(p,q),而不是 H(p)H(p)。兩者的差是相對熵。對模型典型與對真實來源典型,是分開的問題。

熵率考慮相依性

鄰近符號常能幫忙互相預測。因此,長序列每符號需要的資訊,可以小於單一邊際符號的熵。

對隨機程序 X1,X2,…X_1,X_2,\ldots,若極限存在,定義熵率為

Hˉ(X)=lim⁡n→∞1nH(X1,…,Xn).\bar H(X)=\lim_{n\to\infty}\frac1nH(X_1,\ldots,X_n).

其中 Hˉ(X)\bar H(X) 是每符號平均新增的不確定性,nn 是區塊長度。定義討論區塊熵,不是擬合模型在某一條已實現序列上的損失。

鏈式法則給出

1nH(Xn)=1n∑i=1nH(Xi∣Xi−1).\frac1nH(X^n) =\frac1n\sum_{i=1}^{n}H(X_i\mid X^{i-1}).

其中 Xi−1=(X1,…,Xi−1)X^{i-1}=(X_1,\ldots,X_{i-1}) 是先前歷史,i=1i=1 時為空。相依性使條件項不同於邊際熵。

當所有時間指標共同平移後,每個有限維聯合分布都不改變,程序稱為平穩。這比平均值或共變異數固定更強。有限字母的平穩來源,其給定更長過去的條件熵不增加,而且以零為下界,故極限存在;區塊平均熵有相同極限。

兩種極限相等,是因為對收斂的條件熵序列取平均。平穩性允許將固定長度歷史移到共同時間點,而增加過去資訊會降低條件熵。

獨立同分布是特例:每個條件熵都等於 H(X1)H(X_1)。相依的平穩來源可以在每個時間擁有相同邊際分布,但每一步需要的新資訊少得多。

Markov 來源的明確計算

一階 Markov 模型只需目前狀態即可預測下一個狀態。長期不確定性是各轉移列不確定性的加權平均。

設有限 Markov 來源的轉移矩陣為 PP:

Pij=Pr⁡(Xt+1=j∣Xt=i),πj=∑iπiPij.P_{ij}=\Pr(X_{t+1}=j\mid X_t=i), \qquad \pi_j=\sum_i\pi_iP_{ij}.

其中 i,ji,j 是來源狀態索引,tt 是時間,PijP_{ij} 是轉移機率,π\pi 是平穩狀態分布。PP 每列總和為一;π\pi 非負且總和為一。

若程序以 π\pi 初始化,平穩性與 Markov 性質給出

Hˉ(X)=H(Xt+1∣Xt)=−∑iπi∑jPijlog⁡2Pij.\bar H(X)=H(X_{t+1}\mid X_t) =-\sum_i\pi_i\sum_jP_{ij}\log_2P_{ij}.

內部總和是轉移列 ii 的熵,外部總和按平穩占有率加權。有限區塊熵為

H(Xn)=H(π)+(n−1)Hˉ(X).H(X^n)=H(\pi)+(n-1)\bar H(X).

其中 H(π)H(\pi) 是初始狀態熵。鏈式法則貢獻一個初始項與 n−1n-1 個相同轉移項。

對翻轉機率為 aa 的對稱二元來源,平穩分布均勻。邊際熵為一位元,熵率則是 h2(a)h_2(a)。當 a=0.1a=0.1,下一符號多半重複目前符號,因而減少新增不確定性。

翻轉機率 0.1 的對稱 Markov 鏈,其區塊熵除以長度逐漸由一位元降低至熵率;邊際熵維持一位元。
圖 2 — 平穩二元 Markov 來源的解析例子。單一符號頻率均勻,不代表來源獨立。

程式:邊際不變,預測性不同

獨立的翻轉事件產生平穩二元 Markov 區塊,再將觀察到的平均驚訝量與精確區塊熵公式比較。

程式碼 · Python · 18 行
import numpy as np

rng = np.random.default_rng(32)
a = 0.1
rate = -a * np.log2(a) - (1 - a) * np.log2(1 - a)
for n in [64, 256, 1024]:
    initial = rng.integers(2, size=1000)
    flips = rng.binomial(1, a, size=(1000, n - 1))
    states = np.column_stack([
        initial, initial[:, None] ^ np.bitwise_xor.accumulate(flips, axis=1)])
    surprise = 1 + (-flips * np.log2(a) - (1 - flips) * np.log2(1 - a)).sum(axis=1)
    expectation = (1 + (n - 1) * rate) / n
    print("Length:", n, "one-frequency:", states.mean(),
          "mean surprise rate:", surprise.mean() / n,
          "exact entropy per symbol:", expectation)
    assert abs(states.mean() - 0.5) < 0.08
    assert abs(surprise.mean() / n - expectation) < 0.02
print("Entropy rate:", rate, "marginal entropy:", 1.0)

初始狀態均勻取樣,因此來源平穩。每個區塊固定從零開始會改變有限區塊分布;適當轉移假設下漸近速率仍可能相同,但精確的初始熵項會改變。

邊際公平,為什麼仍容易預測?

翻轉機率 a=0.1a=0.1 的對稱 Markov 例子,第一位元有一位元不確定性,後續每個位元貢獻 h2(0.1)=0.468996h_2(0.1)=0.468996 位元。長度十的區塊熵為 1+9h2(0.1)≈5.2209601+9h_2(0.1)\approx5.220960 位元,即每符號 0.522096 位元;十個獨立公平位元則有十位元區塊熵。

可以用初始位元加九個翻轉指示表示整段序列。這個映射可逆:從第一位元開始,依序與翻轉指示做互斥或,就恢復下一狀態。它揭露相依性,沒有捨棄來源資訊。在此特定模型下,指示是有偏的獨立位元,因此比十個邊際公平狀態更容易編碼。

長期速率趨近 0.468996,因為初始化的一位元成本被越來越長的區塊攤提。可預測性來自轉移關係,即使每個時間位置的邊際都公平。影像直方圖也無法揭露利用鄰近像素預測所能獲得的全部節省。

隱藏狀態與觀測對象

轉移模型可能描述內部狀態,接收端卻只看得到帶雜訊的測量。觀測序列因此有自己的預測問題。

設 StS_t 是有限隱藏 Markov 狀態,YtY_t 是發射觀測,模型可將區塊分解為

p(sn,yn)=p(s1)∏t=1n−1p(st+1∣st)∏t=1np(yt∣st).p(s^n,y^n) =p(s_1)\prod_{t=1}^{n-1}p(s_{t+1}\mid s_t) \prod_{t=1}^{n}p(y_t\mid s_t).

其中 sns^n 是狀態序列,yny^n 是觀測序列,各因子描述轉移與發射。對隱藏序列加總後得到觀測概似 p(yn)p(y^n)。

YY 的熵率通常不只是按平穩分布平均的發射列熵。過去觀測能幫助推論隱藏狀態,剩餘狀態不確定性也影響預測。相關項是 H(Yt∣Yt−1)H(Y_t\mid Y^{t-1}),而不只是 H(Yt∣St)H(Y_t\mid S_t)。

對視覺而言,物件動態模型與相機測量模型描述不同的隨機程序。更多感測雜訊可能提高觀測熵,同時降低關於場景的有用資訊。速率計算必須說明究竟描述哪個程序。

共同典型值需要遍歷性

平穩表示分布不隨時間漂移,卻不保證一條長序列會探索混合族群的全部部分。

在適當的有限字母平穩遍歷假設下,長區塊正規化驚訝量收斂至共同的熵率值。遍歷性排除某個持續存在的隱藏選擇,把程序分成行為不同的平穩成分。

考慮只選一次成分 CC:一半機率永遠產生零,一半機率產生獨立公平位元。每個成分平穩,混合也平穩。

條件區塊熵為 H(Xn∣C)=n/2H(X^n\mid C)=n/2。恆等式

H(Xn)=H(Xn∣C)+I(C;Xn)H(X^n)=H(X^n\mid C)+I(C;X^n)

使用成分標籤 CC、區塊 XnX^n 與互資訊 II。因為 I(C;Xn)≤H(C)=1I(C;X^n)\leq H(C)=1,區塊平均熵趨近半位元。

然而,確定成分產生的已實現序列,其正規化驚訝量趨近零;公平成分的序列通常趨近一。多數實現不會共享接近一半的單一值。僅有熵率極限,並不足以套用遍歷 AEP 結論。

程式:平穩但非遍歷的反例

這個完整例子從一的個數解析計算混合區塊機率,避免先計算極小公平區塊機率,再取對數。

程式碼 · Python · 14 行
import numpy as np

rng = np.random.default_rng(33)
for n in [128, 1024]:
    component = rng.integers(2, size=2000)
    counts = rng.binomial(n, 0.5, size=2000) * component
    # A nonzero sequence can only come from the fair component:
    # its probability is 0.5 * 2**(-n), so surprise is n + 1.
    all_zero_surprise = -np.log2(0.5 + 0.5 * np.exp2(-float(n)))
    per_symbol = np.where(counts == 0, all_zero_surprise, n + 1) / n
    print("Length:", n, "deterministic mean:", per_symbol[component == 0].mean(),
          "fair mean:", per_symbol[component == 1].mean(),
          "fraction within 0.1 of 0.5:", np.mean(abs(per_symbol - 0.5) <= 0.1))
    assert np.mean(abs(per_symbol - 0.5) <= 0.1) == 0

例子描述持續的異質性,而不是時間漂移。資料集包含不同來源類型時,可能需要條件模型或明確混合,不能假設一段長紀錄代表整個族群。

聯合與條件典型性

兩條各自普通的序列,配在一起可能非常異常。通訊證明需要輸入與輸出的關係,不能只看各自的直方圖。

從聯合機率質量函數 pXYp_{XY} 獨立取樣配對 (Xi,Yi)(X_i,Y_i),考慮聯合與條件平均驚訝量:

−1nlog⁡2p(Xn,Yn)→H(X,Y),−1nlog⁡2p(Yn∣Xn)→H(Y∣X).-\frac1n\log_2p(X^n,Y^n)\to H(X,Y), \qquad -\frac1n\log_2p(Y^n\mid X^n)\to H(Y\mid X).

其中箭頭表示在指定獨立配對模型下依機率收斂。Xn,YnX^n,Y^n 是配對區塊,每對內部允許相依。

聯合典型配對依照來源的聯合關係檢查,只有邊際典型性並不足夠。若 YY 是 XX 的帶雜訊副本,兩條無關的公平位元序列可以各自有典型邊際計數,卻具有不符模型的差異頻率。

區塊資訊密度為

ı(xn;yn)=log⁡2p(xn,yn)p(xn)p(yn).\imath(x^n;y^n) =\log_2\frac{p(x^n,y^n)}{p(x^n)p(y^n)}.

其中 ı\imath 衡量聯合配對相對於獨立配對模型的證據。在獨立配對取樣及可積分條件下,其正規化平均趨近 I(X;Y)I(X;Y)。

這連結通道解碼:接收端尋找與收到區塊具有通道預期關係的碼字。它也連結配對與表徵學習,正配對必須仔細定義。從錯誤族群抽取負配對,會改變參照分布。

有限字母的強典型性另外限制各符號或配對的經驗頻率,並尊重不可能事件;弱典型性限制平均對數機率。若證明假設使用特定定義,不能在未說明下把兩者互換。

現代觀點

平均驚訝量與有意義輸出的區別,對現代機率模型尤其重要。長上下文與學習式預測器能描述固定 Markov 階數以外的相依性,損失仍是在指定觀測與詞元化模型下評分。

El Gamal 於 2026 年提出的學習章節 [3],以散度連結預測與生成模型。它是草稿補充教材,不是已出版的第三版。從來源編碼觀點推論,序列概似應連同預測目標、單位與條件上下文一起報告。

Huang 與 Wu 的 2024 年綜述 [4] 依人類重建與機器分析的區別,整理學習式影像壓縮。這個分類凸顯壓縮表示是否有用,取決於接收者。熵率給出來源描述的限制,卻不單獨指定任務可接受的失真。

許多應用仍面對三個問題:實際區塊長度下,漸近行為多快才有用;擬合來源模型跨族群是否仍有效;以及取樣、詞元化、前處理造成的相依性,如何影響估計速率。

有限評估應比較獨立區塊或取得資料的群組,並保留非典型案例。只報告平均驚訝量,可能掩蓋速率高得多的稀有來源成分。在一個模型下測量概似,不能證明所有來源成分共享同一典型集。

下一章會實際搭起橋梁:編碼器必須定義機率模型、更新規則、終止慣例,以及未預期符號的處理。速率定理引導選擇,完整編碼再解碼的測試則檢查實作是否還原原始資料。

重點整理

  • AEP 在指定來源假設下,讓正規化區塊驚訝量集中。
  • 典型集機率與基數是不同量,具有不同界限。
  • 單一機率最大的區塊,不一定占大多數總機率。
  • 典型目錄說明幾乎無損編碼限制,不是有效率的實作。
  • 熵率衡量利用相依性後,每一步新增的不確定性。
  • 平穩性不保證遍歷性,也不保證共同的已實現驚訝量。
  • 聯合典型性檢查邊際典型性可能漏掉的關係。
  • 漸近主張必須伴隨有限區塊、模型不匹配與異質性的討論。

練習

  1. 對 p=0.1p=0.1 的 Bernoulli 來源,計算全零區塊的驚訝量率與來源熵,選一個能在所有長度排除全零的容許誤差。
提示

比較 −log⁡2(0.9)-\log_2(0.9) 與 h2(0.1)h_2(0.1)。

  1. 以容許誤差 0.050.05、0.10.1、0.20.2 重跑精確典型機率計算,說明較窄容許誤差為何可能需要更長區塊。
提示

平均驚訝量視窗縮窄。

  1. 用不同的 ϵ\epsilon 與 δ\delta 推導典型集基數上下界,指出每一步使用哪個單一區塊機率界限。
提示

以區塊數乘最大或最小允許機率,限制總和。

  1. 二元 Markov 鏈轉移矩陣為 P=(0.90.10.30.7)P=\begin{pmatrix}0.9&0.1\\0.3&0.7\end{pmatrix}。求平穩分布、邊際熵與熵率。
提示

解 π=πP\pi=\pi P,再加權轉移列熵。

  1. 將非遍歷混合例子的成分機率改為四分之一確定來源、四分之三公平來源,求區塊熵率極限與各實現的驚訝量率極限。
提示

持續存在的成分仍阻止共同實現值。

  1. 構造兩條邊際典型公平位元序列,使它們在 10% 翻轉通道下不是聯合典型。說明個別符號計數為何無法發現不匹配。
提示

使用差異過多或過少的配對。

參考文獻

  1. T. M. Cover and J. A. Thomas, Elements of Information Theory, 2nd ed., Wiley, 2006, Chapters 3–4. 出版社書籍與目錄.
  2. T. Weissman, “Asymptotic Equipartition Property,” Stanford EE276 Lecture 3 notes, 2024. 原始課程講義.
  3. A. El Gamal, “Information Theory and Statistical Learning,” proposed textbook chapter, arXiv preprint, 2026. 草稿與出版狀態.
  4. C.-H. Huang and J.-L. Wu, “Unveiling the Future of Human and Machine Coding: A Survey of End-to-End Learned Image Compression,” Entropy, 26(5), 357, 2024. 已出版綜述.

檢查理解

本篇有 6 題練習。不看提示,你能解出來嗎?

前往練習 ↑

下一篇 IT 03・無損編碼與通用壓縮 · 15 分鐘