クロード・シャノンによる漸近等分割性 (AEP)：情報理論の基礎をなす統計的性質
はじめに：情報理論における確率的性質の重要性
情報理論の確立において、クロード・シャノンは通信における情報の定量化と信頼性の限界を確率論的な枠組みで鮮やかに示しました。その理論の多くの核心部分を支える重要な概念の一つに、「漸近等分割性 (Asymptotic Equipartition Property, AEP)」があります。AEPは、確率的な情報源から生成される長い記号列が持つ統計的な性質、すなわち「ほとんど全ての列が似たような統計構造を持つ」という直感を数学的に厳密に定式化したものです。
この性質は、一見抽象的に見えるエントロピーという情報量が、なぜデータ圧縮の限界や通信路容量と直接結びつくのかを深いレベルで理解するための鍵となります。本稿では、シャノンのオリジナルの論文におけるAEPの位置づけに触れつつ、その概念、厳密な定式化、そしてソース符号化定理やチャネル符号化定理への応用について詳細に掘り下げていきます。
情報源、記号列の確率、そしてエントロピー
AEPを理解するためには、まず情報源とそこから生成される記号列、そしてエントロピーの概念を確認する必要があります。離散的無記憶情報源 (Discrete Memoryless Source, DMS) は、アルファベット $\mathcal{X} = {x_1, x_2, \dots, x_m}$ から独立に確率分布 $P(X)$ に従って記号を生成します。ここで、$P(X=x_i) = p_i > 0$ であり、$\sum_{i=1}^m p_i = 1$ です。
この情報源から生成される長さ $n$ の記号列 $x^n = (x_1, x_2, \dots, x_n)$ の確率は、記号が独立に生成されるため、各記号の確率の積として与えられます。 $$P(x^n) = P(x_1, x_2, \dots, x_n) = \prod_{i=1}^n P(x_i)$$ 特に、記号 $x_i$ が列 $x^n$ の中に $N_i(x^n)$ 回出現する場合、$P(x^n)$ は以下のように書けます。 $$P(x^n) = \prod_{j=1}^m p_j^{N_j(x^n)}$$ ここで $\sum_{j=1}^m N_j(x^n) = n$ です。
エントロピー $H(X)$ は、この情報源が生成する記号あたりの平均情報量、あるいは不確かさを表し、以下で定義されます。 $$H(X) = -\sum_{i=1}^m p_i \log_2 p_i$$ 対数の底は通常2が用いられ、単位はビットです。
漸近等分割性 (AEP) の核心：典型的な挙動
AEPが主張するのは、十分に長い記号列 $X^n$ をDMSから生成したとき、そのほとんど全ての列が、確率的に非常に小さい値を持つにも関わらず、その確率値の「対数」のスケールがエントロピーと密接に関係するという性質です。具体的には、列 $X^n$ の確率 $P(X^n)$ の対数は $-\frac{1}{n} \log P(X^n)$ で正規化すると、列の長さ $n \to \infty$ の極限で情報源のエントロピー $H(X)$ に確率収束するというものです。 $$-\frac{1}{n} \log P(X^n) \xrightarrow{P} H(X) \quad \text{as } n \to \infty$$ これは大数の法則の一種であり、記号列が長くなるにつれて、各記号の出現頻度はその確率 $p_i$ に近づくという性質に基づいています。つまり、$N_i(X^n)/n \approx p_i$ となるため、 $$-\frac{1}{n} \log P(X^n) = -\frac{1}{n} \log \left( \prod_{i=1}^m p_i^{N_i(X^n)} \right) = -\sum_{i=1}^m \frac{N_i(X^n)}{n} \log p_i \approx -\sum_{i=1}^m p_i \log p_i = H(X)$$ となるわけです。
この収束から、長い記号列の確率 $P(X^n)$ は、およそ $2^{-nH(X)}$ に近い値をとることが示唆されます。 $$P(X^n) \approx 2^{-nH(X)}$$ そして、重要な結論は、このような「典型的な」確率値を持つ記号列の集合（典型集合と呼ばれます）が、可能な全ての長さ $n$ の記号列の中で、ほとんど全ての確率質量（合計確率が1に近い部分）を占めるということです。さらに、この典型集合に含まれる記号列の数は、およそ $2^{nH(X)}$ 個であることも示されます。
ε-典型集合による厳密な定式化
AEPの厳密な定式化には、ε-典型集合 (ε-typical set) の概念が用いられます。ある ε > 0 に対して、長さ $n$ の記号列 $x^n$ が ε-典型集合 $A_\varepsilon^{(n)}$ に含まれるとは、以下の条件を満たす場合を言います。 $$| - \frac{1}{n} \log P(x^n) - H(X) | \le \varepsilon$$ これは、$-\frac{1}{n} \log P(x^n)$ が $H(X)$ の ε 近傍にあることを意味します。言い換えれば、 $$2^{-n(H(X)+\varepsilon)} \le P(x^n) \le 2^{-n(H(X)-\varepsilon)}$$ となる列の集合です。
AEPは、ε-典型集合に関して以下の性質が成り立つことを主張します。
-
確率質の集中: 任意の ε > 0 に対して、十分に大きな $n$ を選べば、生成される記号列 $X^n$ が ε-典型集合 $A_\varepsilon^{(n)}$ に含まれる確率は1に任意に近づきます。 $$P(X^n \in A_\varepsilon^{(n)}) \to 1 \quad \text{as } n \to \infty$$
-
集合のサイズの範囲: 任意の ε > 0 に対して、十分に大きな $n$ を選べば、ε-典型集合 $A_\varepsilon^{(n)}$ に含まれる列の数 $|A_\varepsilon^{(n)}|$ は、以下の範囲に収まります。 $$(1-\varepsilon') 2^{n(H(X)-\varepsilon)} \le |A_\varepsilon^{(n)}| \le 2^{n(H(X)+\varepsilon)}$$ ここで $\varepsilon'$ は $n \to \infty$ で0に収束する値です。より簡潔には、$|A_\varepsilon^{(n)}| \approx 2^{nH(X)}$ と考えられます。
これらの性質の証明は、確率変数 $-\frac{1}{n} \log P(X^n)$ に対する大数の法則（正確には、サンペドロの定理やエルゴード定理など、より一般的な確率過程に対するもの）を適用することで得られます。$X_1, X_2, \dots$ が独立同分布 (i.i.d.) である場合、$-\log P(X_i)$ はi.i.d.確率変数となり、その期待値は $E[-\log P(X)] = -\sum p_i \log p_i = H(X)$ です。$-\frac{1}{n} \sum \log P(X_i)$ に大数の法則を適用することで、上記の確率収束が得られます。
ソース符号化定理への洞察
AEPは、シャノンのソース符号化定理（無損失データ圧縮の限界を示す定理）の直感的な理解と厳密な証明に不可欠な役割を果たします。ソース符号化定理は、DMSから生成される記号列を可逆圧縮する場合、記号あたりの平均符号長は情報源のエントロピー $H(X)$ より短くはできないことを示します。逆に、$H(X)$ に任意に近くまで圧縮可能であることも示されます。
AEPによれば、長さ $n$ の記号列のほとんど全ては ε-典型集合 $A_\varepsilon^{(n)}$ に含まれます。そして、この典型集合のサイズは $n$ が大きいとき約 $2^{nH(X)}$ です。符号化器は、可能な全ての $m^n$ 個の記号列の中から、典型集合に含まれる約 $2^{nH(X)}$ 個の列だけを区別して符号化すれば、ほとんど全ての確率（1に近い確率）で元の情報を復元できます。
$2^{nH(X)}$ 個の異なるアイテムを区別するために必要な最小のビット数は、$\lceil \log_2 2^{nH(X)} \rceil = \lceil nH(X) \rceil$ です。したがって、これらの典型的な列を符号長約 $nH(X)$ の符号語にマップすることで、非常に高い確率で可逆圧縮が実現できます。非典型的な列が発生する確率は $n \to \infty$ で0に収束するため、これらの列をどのように符号化するかは平均符号長にほとんど影響を与えません。この考え方が、ソース符号化定理（特に存在証明の部分）の根幹をなしています。
チャネル符号化定理への洞察
AEPは、シャノンのチャネル符号化定理（ノイズのある通信路を通した信頼できる通信の限界を示す定理）にも同様に深い洞察を与えます。チャネル符号化定理は、通信路容量 $C$ が、任意に低い誤り確率で通信できる最大レートであることを示します。
通信路を通じた通信では、送信された符号語 $x^n$ と受信される列 $y^n$ の間に統計的な依存関係があります。AEPの概念を拡張すると、送信系列 $x^n$ と受信系列 $y^n$ のペア $(x^n, y^n)$ が持つ結合確率 $P(x^n, y^n)$ や条件付き確率 $P(y^n|x^n)$ に関しても、長い列の対数確率はそれぞれの結合エントロピー $H(X,Y)$ や条件付きエントロピー $H(Y|X)$ に確率収束するという性質（結合AEP、または逐次AEP）が成り立ちます。
特に、送信系列 $X^n$ を独立同分布なランダム系列として選び、それが通信路を通って受信系列 $Y^n$ となった場合、ペア $(X^n, Y^n)$ の同時確率は約 $2^{-n H(X,Y)}$ となります。このような「結合典型的 (jointly typical)」なペア $(x^n, y^n)$ の集合は、送信された $x^n$ が与えられたときに受信される可能性のある $y^n$ の集合の中から、統計的に尤もらしいものを選び出す際に中心的な役割を果たします。受信側では、受け取った $y^n$ に対して、どの送信符号語 $x^n$ が最も結合典型的であるか（または、どの送信符号語が最も高い条件付き確率 $P(y^n|x^n)$ をもたらすか）を判断することで復号を行います。
チャネル符号化定理の証明（特にランダム符号化を用いる場合）では、多数の符号語をランダムに生成し、それらを典型集合の性質を用いて分析します。送信レート $R$ が通信路容量 $C$ より小さい場合、ランダムに選ばれた送信符号語 $X^n$ とそれに対応する受信系列 $Y^n$ のペア $(X^n, Y^n)$ が結合典型的となる確率が非常に高くなることを示します。これにより、受信系列 $Y^n$ を観測した際に、誤って別の送信符号語 $X'^n \ne X^n$ と結合典型的になってしまう確率が指数関数的に減少することを示し、信頼性の高い通信が可能であることを結論づけます。ここでも、結合典型集合のサイズが相互情報量 $I(X;Y)$ と関連すること（約 $2^{nI(X;Y)}$）が重要な役割を果たします。
歴史的背景と現代における意義
シャノンがAEPに相当する概念を用いたのは、彼の1948年の画期的な論文「通信の数学的理論」のセクション3、「離散的な情報源を持つチャネル容量」の議論です。彼は、長い記号列の確率分布がエントロピーによって特徴づけられること、そしてそれが通信容量の限界を決定する上でいかに基本的であるかを示しました。当時の情報理論は全く新しい分野であり、確率論と情報概念を結びつけるAEPのような性質の発見は、理論全体の数学的厳密性を担保する上で極めて重要でした。
AEPは、情報理論の基礎をなすだけでなく、その後多くの分野に応用されるようになりました。統計学における推定理論、機械学習における確率モデル、圧縮センシング、複雑ネットワーク分析など、確率的なデータや現象を扱う多くの分野で、AEPから派生した概念や手法が利用されています。例えば、機械学習における尤度関数の分析やモデル選択規準（AICやBICなど）の理論的基礎にも、情報量規準やエントロピーの考え方が深く関わっており、その背景にはAEPのような漸近的な確率的性質の理解があります。
AEPはまた、「強く典型的な集合 (strongly typical set)」といった、より厳密な、あるいは異なる種類の典型集合の研究にもつながりました。これらの発展は、特定の応用（例えば、レート歪み理論）においてより精密な限界を導出するために重要となります。
このような性質は、例えばPythonを用いて長い記号列の頻度分布をシミュレーションし、その対数確率の平均がエントロピーに収束することを確認するなど、計算科学的なアプローチからもその妥当性を確認することが可能です。
結論
クロード・シャノンによる漸近等分割性 (AEP) は、情報理論における最も基本的かつ強力な概念の一つです。それは、確率的な情報源から生成される長い記号列が持つ統計的な規則性を明らかにし、エントロピーが情報量の適切な尺度であること、そしてそれがデータ圧縮と通信の信頼性の限界を決定する上で中心的な役割を果たすことを数学的に裏付けました。
AEPは、単に抽象的な数学的性質に留まらず、シャノンのソース符号化定理とチャネル符号化定理という、情報理論の二大定理の直感的な理解と厳密な証明の両方において不可欠な基盤を提供します。情報科学分野の研究者にとって、AEPの深い理解は、情報理論の古典的な成果を正しく解釈し、現代の様々な応用分野における情報論的なアプローチを開発・分析する上で不可欠な出発点となると言えるでしょう。AEPによって示される確率質の集中という性質は、情報理論における指数関数的な振る舞いや、漸近的な解析の強力さを示す典型的な例でもあります。
本稿が、シャノンの遺したこの深遠な概念への理解の一助となれば幸いです。