2.1 為什麼資訊理論需要機率#

導言：不確定性是資訊的本體#

「資訊」在日常語言中指有意義的內容；在資訊理論中，資訊是不確定性的消除量。一則訊息之所以攜帶資訊，是因為在收到之前，我們無法確定它會是什麼。若訊息的結果早已註定（機率為 1），收到它等於什麼也沒學到。反之，結果越難預料，收到的訊息越「有料」。

這個直覺要變成數學，必須借助機率論：只有當訊息的產生是一個隨機現象，我們才能量化它的不確定性。本章（以及第 3 章）的全部內容，都建立在這個觀念上：信源是隨機變數（或隨機過程），而資訊度量是不確定性的函數。

從擲骰子到信源#

考慮幾個實驗：

這個表格揭示兩個原則：

1. 不確定性隨結果數目增加（銅板 < 骰子）。
2. 不確定性隨機率分散程度增加（公平骰子 > 灌鉛骰子）。

任何合格的「不確定性度量」都必須同時滿足這兩條。第 3.1 節將證明：唯一（在合理公理下）滿足的函數就是熵 \(H(X) = -\sum_x p(x)\log_2 p(x)\) 。但要走到那裡，我們得先重溫機率論的工具箱。

機率論的快速複習#

樣本空間與事件#

一個隨機實驗的樣本空間 \(\Omega\) 是所有可能結果的集合；事件是 \(\Omega\) 的子集；機率測度 \(P\) 是對事件賦予 \([0,1]\) 之間實數、滿足可加性的函數。

隨機變數#

隨機變數 \(X\) 是從 \(\Omega\) 映到實數（或符號集 \(\mathcal{X}\) ）的函數。在資訊理論中，信源的每個輸出就是一個隨機變數的取值。離散隨機變數由機率質量函數（pmf）描述：

期望值#

熵、互資訊、相對熵——資訊理論的三大度量——全部都是期望值。這是機率論進入資訊理論的第一扇門：我們先定義「單一結果的不確定量」 \(g(x) = -\log_2 p(x)\) ，再取期望。2.2 節將正式定義這個量。

例題：英文字母的機率模型#

統計大樣本英文文本，可得字母頻率（近似）：

把英文信源建模為「獨立同分佈抽字母」的隨機變數 \(X\) ，其機率分佈 \(p_X\) 完全決定了它的可壓縮性：熵 \(H(X)\) （3.1 節）約為 \(4.18\) bits，遠低於 \(\log_2 26 \approx 4.70\) bits。這個差距正是 Morse 碼（1.1 節）與所有壓縮器的獲利空間。

為什麼「等可能」不夠：Hartley 的缺口#

1.2 節的 Hartley 度量 \(H = \log_2 M\) 只看結果數目，不看機率分佈。用上面的原則檢驗，它違反第二原則：灌鉛骰子與公平骰子都有 \(M = 6\) 個結果，Hartley 給出相同的「不確定性」，但直觀上灌鉛骰子的結果好猜得多。

更嚴重的問題：真實信源（語言、影像、感測器）的機率分佈幾乎從不均勻。一個理論若只能處理均勻分佈，就無法解釋為什麼英文文本可以壓縮到每字母約 \(1.5\) 位元（LZ77 實測值），而 Hartley 極限是 \(4.7\) 位元。機率是把「統計結構」變成「可壓縮資源」的橋樑。

例題：不均勻分佈的威力#

信源 \(X\) ： \(P(X = a) = 0.99\) ， \(P(X = b) = 0.01\) 。傳送一千個樣本，幾乎全是 \(a\) 。聰明的編碼者只需標記「 \(b\) 出現的位置」，平均花費遠低於每樣本 1 bit。這個例子預告了 2.2 節自資訊的核心公式： \(I(a) = -\log_2 0.99 \approx 0.014\) bits（幾乎不攜帶資訊）， \(I(b) = -\log_2 0.01 \approx 6.64\) bits（很驚訝）。

隨機過程：信源的完整模型#

一則訊息不是一個符號，而是符號序列。英文文本、語音波形取樣後的樣本串、影片的像素流，都是隨機過程 \(\{X_1, X_2, X_3, \dots\}\) 。不同的隨機過程模型導致不同的理論分支：

漸近等分性質（AEP）是資訊理論的柱石：對 i.i.d. 信源，當 \(n\) 大時，幾乎所有長度 \(n\) 的序列都落在「典型集」內，其機率約 \(2^{-nH}\) ，典型集約有 \(2^{nH}\) 個成員。因此每個典型序列可以用 \(nH\) 個位元標記——這就是熵 = 壓縮極限的證明骨幹（3.1 節詳述）。而 AEP 本身就是大數法則的應用。

例題：用大數法則數典型序列#

信源 \(P(a) = 0.75\) 、 \(P(b) = 0.25\) 。熵

長度 \(n = 100\) 的序列中， \(a\) 的個數以高機率接近 \(75\) （大數法則）。這類「約有 75 個 a」的序列機率為

典型序列總數約 \(2^{81.1}\) 個，遠少於全部 \(2^{100}\) 個可能序列。只需 \(\log_2 2^{81.1} = 81.1\) 位元即可標記任何一個典型序列——壓縮率 \(0.811\) bits/symbol 就這樣從機率中浮現。

歷史前因後果#

機率論何時成熟#

機率從十七世紀 Pascal 與 Fermat 的賭博書信，經 Bernoulli（大數法則，1713）、Laplace（古典機率）、到 Kolmogorov（1933 公理化）才成為嚴格數學。Shannon 1948 恰好站在 Kolmogorov 公理化之後，得以直接使用堅實的測度論基礎——雖然他的論文行文極少用測度論，保持工程可讀性。

誰把機率帶進通訊#

• Wiener（1942，防空砲火預測）：用隨機過程建模雜訊，發展濾波與預測理論。Wiener 與 Shannon 幾乎同時但獨立工作；Wiener 的「控制論」強調回饋與語義，Shannon 的「資訊論」專注統計傳輸。
• Kolmogorov（1958–1965）：演算法資訊理論（Kolmogorov 複雜度），把資訊量定義為最短描述長度，補足了 Shannon 理論不考慮「可計算性」的面向（10.3 節）。

解決了什麼問題、引發什麼新問題#

機率建模解決了「如何客觀描述信源」的問題，使壓縮與傳輸的極限可計算。新問題隨之而來：

1. 分佈未知：實際系統不知道 \(p(x)\) ，要邊傳邊學——通用壓縮（5.3 節）。
2. 模型錯誤：i.i.d. 假設對語言不成立（字母之間有強相依），催生上下文模型與率失真理論。
3. 主觀機率 vs 客觀頻率：貝葉斯觀點與頻率觀點在資訊理論中並存，至今仍在辯論。

與其他領域的關聯#

統計力學#

Boltzmann 的熵度量氣體微觀狀態的不確定性；Shannon 的熵度量信源符號的不確定性。兩者在數學上同構（3.1 節），並共享最大熵原理：給定約束下，最「無偏」的分佈是熵最大的分佈（Jaynes, 1957）。

決策理論與統計推論#

「收到訊息 = 更新信念」是貝葉斯更新：先驗 \(p(x)\) 乘以似然得到後驗。互資訊（3.3 節）正是「先驗不確定性 − 後驗不確定性」的期望值。資訊理論與統計學由此血脈相連。

計算機科學#

隨機演算法、蒙特卡羅方法、密碼學的不可預測性——都需要不確定性的度量。Kolmogorov 複雜度 \(K(x)\) （最短程式長度）與 Shannon 熵 \(H(X)\) 在期望上吻合： \(E[K(X_n)] \approx nH + O(\log n)\) 。

小結與思考題#

資訊理論之所以需要機率，是因為資訊 = 不確定性的消除，而不確定性只有機率論能精確描述。本節確立了兩個原則（結果越多越不確定、分佈越散越不確定）與兩個工具（pmf、期望值），下一節將用它們定義單一結果的資訊量。

思考題

1. 比較兩個信源的不確定性：甲 \(\{0.5, 0.5\}\) ，乙 \(\{0.5, 0.25, 0.25\}\) 。直觀上哪個更不確定？（注意乙有三個結果但並不更不確定——這暗示度量必須對分佈敏感，而非只數結果。）
2. 英文字母加上空格共 27 個符號，Hartley 極限為 \(\log_2 27 \approx 4.75\) bits。實測英文每字母熵約 \(4.18\) bits（不計上下文）與約 \(1.5\) bits（計入上下文）。兩者的差從哪裡來？
3. 大數法則說「頻率趨近機率」。用這句話解釋：為什麼長序列的「典型性」幾乎必然發生？
4. 若信源分佈是確定性的（ \(p(x_0) = 1\) ），熵會是多少？這與 1.1 節「太陽從東方升起」的例子呼應嗎？

下一節，我們把「單一結果的不確定量」寫成公式：自資訊 \(I(x) = -\log_2 p(x)\) 。

深入探討：機率建模的方法論與陷阱#

一、信源建模的三個層次#

把真實信源（一段英文、一段語音）寫成機率模型，有從粗到細的三層選擇，每一層對應資訊理論的一個分支：

選模的工程原則：模型複雜度每升一級，可壓縮性估計更準，但估計模型本身要花資料與運算。這個取捨的形式化就是 MDL（最小描述長度）：選使「模型描述長度 + 資料編碼長度」總和最小的模型層次——它是 3.3 節相對熵的統計化身，也是 5.3 節上下文模型的設計準則。

二、AEP 的嚴格化：三個性質的證明骨架#

2.1 節陳述了典型集的直觀，這裡給出完整證明（i.i.d. 情形），因為它是所有編碼定理的第一座橋。

定義： \(A_\epsilon^{(n)} = \{x^n : |-\frac{1}{n}\log_2 p(x^n) - H| \le \epsilon\}\) 。

性質 1（典型集承載機率）：由大數法則， \(\frac{1}{n}I(x^n) = -\frac{1}{n}\sum_i \log_2 p(x_i) \xrightarrow{P} H\) 。故 \(P(x^n \in A_\epsilon^{(n)}) \to 1\) 。

性質 2（典型集很小）：對 \(x^n \in A_\epsilon^{(n)}\) ， \(p(x^n) \ge 2^{-n(H+\epsilon)}\) ，故

性質 3（典型集不小）：對 \(n\) 足夠大， \(P(A_\epsilon) > 1 - \delta\) ，故

推論（壓縮的可行性）：只需 \(n(H + \epsilon)\) 位元即可一一標記典型集；非典型序列全部映射到一個「失敗」碼字（機率 \(\le \delta\) ）。取 \(\epsilon, \delta \to 0\) 得壓縮率極限 \(H\) 。這 12 行證明是全書最重要的技術——4.3 節通道編碼、5.1 節碼長定理、10.3 節網路定理全部重演此腳本。

三、機率模型的常見誤區#

初學者（與一些論文）在信源建模上犯的典型錯誤，值得提前列出：

1. 把樣本當總體：用一段文本的頻率估計熵時，忽略有限樣本偏差——實測熵 \(\hat H\) 系統性低估真實熵（未見符號的貢獻為零）。修正：Miller–Madow 補正 \(\hat H + \frac{M-1}{2n}\) （ \(M\) 為字母數、 \(n\) 為樣本數）；或用 Good–Turing 平滑。
2. 假設 i.i.d. 而實際強相依：英文若按 i.i.d. 估計熵率為 4.18 bits，真實約 1.5 bits——高估近 3 倍，直接導致壓縮器設計錯誤（浪費碼表空間）。
3. 忽略非平穩性：語音的分佈隨說話者與情緒漂移。對策：自適應模型（滑動窗、指數遺忘），5.3 節的自適應編碼。
4. 混淆熵與最小描述長度：熵是期望量（隨機變數的函數）， \(K(x)\) 是逐樣本量（字串的函數）。序列「平均可壓到 \(nH\) 」不等於「每個序列都壓得到」。

四、機率論工具箱的速查表#

本書會用到的機率結果，一次列出供查閱：

五、一個完整的統計實驗：實測英文的熵#

設計一個讀者可在電腦上完成的實驗，體會 2.1 節各概念的實際數值：

1. 取材：取約 1 MB 的英文文本，轉小寫、保留字母與空格（27 符號）。
2. 一階頻率：統計各符號頻率 \(\hat p_i\) ，計算 \(\hat H = -\sum \hat p_i \log_2 \hat p_i\) 。典型值約 4.1–4.3 bits。
3. 一階馬可夫：統計 27×27 轉移矩陣，計算條件熵 \(H(X_2|X_1) = -\sum_{ij} \hat \pi_i T_{ij} \log_2 T_{ij}\) 。典型值約 3.3–3.6 bits。
4. 二階：統計 3 元組條件分佈，條件熵降至約 2.8–3.1 bits。
5. 觀察：每加一階上下文，條件熵下降但估計方差急升（稀疏的三元組）——這就是 5.3 節 PPM 的「逃脫機率」要解決的問題：上下文越深，未見事件越多。

這個實驗把「熵率隨上下文遞減、模型估計隨維度發散」的張力變成親手可觸的數字，是理解通用壓縮（5.3）與語言模型困惑度（10.3）的直接準備。

六、機率詮釋的哲學分歧：頻率派 vs 貝葉斯派#

資訊理論對機率的詮釋採取刻意中立： \(p(x)\) 可以是頻率（重複產生信源的長期比例）、可以是主觀信念（解碼器對發送符號的信心）。兩種詮釋在具體應用中的分工：

• 頻率詮釋適合信源統計（英文頻率、通道錯誤率）——有可重複的物理過程。
• 貝葉斯詮釋適合解碼與推論（後驗 \(p(x|y)\) 、先驗 \(p(x)\) ）——信念隨證據更新，2.3 節的貝葉斯解碼。
• 主觀資訊的難題：同一段密文，知道金鑰的人獲得全部資訊、不知道的人獲得零資訊——資訊量相對於觀察者的知識狀態而定。這正是 9.3 節完美保密定義 \(I(M;C) = 0\) 的深層理由：資訊 = 信念的改變量，密碼學就是管理信念改變的技術。

七、補充思考題#

1. 對 2.1 節的信源 \(P(a)=0.75, P(b)=0.25\) ：取 \(n = 50\) ，用 Chernoff 界估計「 \(a\) 出現次數超過 47 次」的機率。
2. 用 Miller–Madow 補正修正第五節實驗的一階熵估計（ \(M = 27\) 、 \(n = 10^6\) ），補正量是多少 bits？可忽略嗎？
3. 一個信源分佈未知但保證屬於集合 \(\{p_1, p_2\}\) 之一。設計一個編碼器在兩種情況下都接近最優（提示：最大最小率 = 兩熵的最大值，即 5.3 節「通用編碼」的最簡單例子）。
4. 為什麼「樣本均值趨於期望」的 LLN 不直接給出「壓縮率趨於熵」？中間還需要哪一步（提示：典型集的可數性/可編碼性——知道典型集存在還不夠，要能一一標記它）。