シャノンによる定常エルゴード情報源とそのエントロピー率：漸近等分割性 (AEP) の基盤
はじめに：情報源の多様性と理論の一般化
クロード・シャノンの「A Mathematical Theory of Communication」は、情報理論の体系を確立する上で不可欠な基盤を提供しました。その中で、情報源（Source）のモデリングは理論の出発点の一つです。最も単純な情報源として独立同分布（i.i.d.）源やマルコフ源が議論されますが、より現実世界の複雑な情報生成プロセスを捉えるためには、より一般的な確率過程として情報源をモデル化する必要があります。シャノンは、特に定常性（Stationarity）とエルゴード性（Ergodicity）という確率過程の性質に着目し、これらの性質を持つ情報源に対するエントロピー率の概念を導入しました。本記事では、シャノンの情報理論における定常エルゴード情報源の重要性、そのエントロピー率の定義と意義、そしてソース符号化の根幹をなす漸近等分割性（Asymptotic Equipartition Property, AEP）との関連性について深く掘り下げます。
情報源の確率過程モデル：定常性とエルゴード性
情報源 $\mathcal{X}$ は、離散時間パラメータ $t \in \mathbb{Z}$ または $t \in \mathbb{N}$ に対する確率変数の列 ${X_t}_{t}$ としてモデル化されます。各確率変数 $X_t$ は、有限または可算なアルファベット $\mathcal{A}$ から値を取るとします（離散情報源の場合）。
定常性 (Stationarity)
確率過程 ${X_t}{t}$ が定常であるとは、その統計的性質が時間によって変化しないことを意味します。より厳密には、任意の $n \ge 1$ と任意の時点 $t_1, \dots, t_n$ および時間シフト $h$ に対して、同時確率分布が等しい場合に定常であるといいます。 $$P(X{t_1} = x_1, \dots, X_{t_n} = x_n) = P(X_{t_1+h} = x_1, \dots, X_{t_n+h} = x_n)$$ これは、有限次元分布が時間シフトに対して不変であることを意味します。情報理論において定常性は、情報源の統計的構造が安定しているという仮定であり、長期的な振る舞いを分析する上で不可欠な性質です。
エルゴード性 (Ergodicity)
エルゴード性は定常性よりも強い性質であり、確率過程の時間平均がアンサンブル平均に一致するという性質と関連しています。直感的には、十分長い時間観測された系列が、情報源の全ての可能な典型的な振る舞いを代表していることを意味します。より厳密な数学的定義は確率測度論に基づきますが、情報理論におけるエルゴード性の意義は、特に長い系列 $(X_1, X_2, \dots, X_n)$ の統計的性質が、サンプル系列が異なっても漸近的に同じになるという点にあります。シャノンは、エルゴード的な情報源においては、ある系列の確率 $-\frac{1}{n}\log P(X_1, \dots, X_n)$ が $n \to \infty$ の極限で定数に収束することを示唆しました。この性質がAEPの基礎となります。
定常エルゴード情報源のエントロピー率
定常エルゴード情報源は、定常性と共にエルゴード性を持つ情報源です。シャノンは、このような情報源に対して、その不確実性の度合いを測る尺度としてエントロピー率 (Entropy Rate) を定義しました。
情報源 $\mathcal{X} = {X_t}{t}$ のエントロピー率は、以下のように定義されます。 $$H(\mathcal{X}) = \lim{n \to \infty} \frac{1}{n} H(X_1, \dots, X_n)$$ ここで $H(X_1, \dots, X_n)$ は $n$ 個の確率変数の結合エントロピーです。この極限は、定常情報源に対して存在することが知られています。さらに、シャノンは定常エルゴード情報源に対して、別の形のエントロピー率の極限も存在し、上の定義と一致することを示唆しました（シャノンの原論文 [Part II, Theorem 3] を参照）。 $$H'(\mathcal{X}) = \lim_{n \to \infty} H(X_n | X_1, \dots, X_{n-1})$$ このエントロピー率は、過去の系列が与えられた下での次のシンボルの条件付きエントロピーの極限であり、情報源が長期的に生成するシンボル1つあたりの平均的な不確実性を表します。定常エルゴード情報源にとって、この $H(\mathcal{X})$ または $H'(\mathcal{X})$ が、その情報源の統計的構造によって本質的に決まる「真の情報量レート」となります。
漸近等分割性 (AEP) と定常エルゴード情報源
シャノンの情報理論における最も強力な結果の一つである漸近等分割性（AEP）は、特に定常エルゴード情報源に対して成り立ちます。AEPは、十分に長い系列を観測したとき、その観測される系列のほとんどが「典型的な系列 (Typical Sequence)」と呼ばれる特定の性質を持つ集合に属するという性質です。
具体的には、定常エルゴード情報源 ${X_t}_{t}$ から生成される長さ $n$ の系列 $(X_1, \dots, X_n)$ について、AEPは以下の性質が成り立つことを主張します。 $$-\frac{1}{n} \log P(X_1, \dots, X_n) \to H(\mathcal{X}) \quad \text{in probability as } n \to \infty$$ これは、系列 $(X_1, \dots, X_n)$ の結合確率 $P(X_1, \dots, X_n)$ が、長い系列においては漸近的に $2^{-n H(\mathcal{X})}$ に近い値を取ることを意味します。
AEPの核となるのは典型集合 (Typical Set) の概念です。ある $\epsilon > 0$ に対して、長さ $n$ の系列 $x = (x_1, \dots, x_n)$ の典型集合 $A_\epsilon^{(n)}$ は、以下の条件を満たす系列の集合として定義されます。 $$A_\epsilon^{(n)} = \left{ x \in \mathcal{A}^n : \left|-\frac{1}{n}\log P(x_1, \dots, x_n) - H(\mathcal{X})\right| \le \epsilon \right}$$ AEPが定常エルゴード情報源に対して成り立つことから、以下の重要な性質が導かれます。 1. 典型集合 $A_\epsilon^{(n)}$ に属する系列の確率の合計は、 $n \to \infty$ のとき1に収束します。つまり、情報源から生成されるほとんど全ての長い系列は典型集合に属します。 2. 典型集合のサイズ $|A_\epsilon^{(n)}|$ は、 $n \to \infty$ のとき漸近的に $2^{n H(\mathcal{X})}$ に近い値を取ります。より正確には、 $(1-\epsilon') 2^{n(H(\mathcal{X})-\epsilon)} \le |A_\epsilon^{(n)}| \le 2^{n(H(\mathcal{X})+\epsilon)}$ for large $n$.
これらの性質は、ソース符号化、すなわち情報源の可逆圧縮の理論的限界を示すソース符号化定理（シャノンの原論文 [Part II, Theorem 4]）の証明において中心的な役割を果たします。
ソース符号化への応用と理論的意義
ソース符号化（データ圧縮）の目的は、情報源から生成される系列を、できるだけ少ないビット数で、可能な限り忠実に表現することです。可逆圧縮の場合、復元時に元の系列を完全に再現できる必要があります。
シャノンのソース符号化定理は、レート $R$ での情報源 $\mathcal{X}$ の可逆圧縮が可能である必要十分条件は $R \ge H(\mathcal{X})$ であると述べています。ここでレート $R$ は、系列1シンボルあたりに割り当てられる平均ビット数です。
この定理の証明では、AEPが決定的に利用されます。AEPによれば、長い系列はほとんど全て典型集合 $A_\epsilon^{(n)}$ に属し、そのサイズは約 $2^{n H(\mathcal{X})}$ です。したがって、典型集合に属する各系列に一意な符号語を割り当てることで圧縮を達成できます。典型集合に属さないごく少数の系列は、特別な符号語で処理するか、無視することができます（無視した場合、復元は不可能になりますが、長い系列ではその確率が非常に小さいため、平均的な誤り確率は小さく抑えられます）。
符号語の数として典型集合のサイズ $|A_\epsilon^{(n)}|$ を用いると、必要とされるビット数は $\log_2 |A_\epsilon^{(n)}|$ となり、AEPからこれは約 $n H(\mathcal{X})$ となります。したがって、シンボルあたりの平均ビット数は $\frac{1}{n} \log_2 |A_\epsilon^{(n)}| \approx H(\mathcal{X})$ となり、これが可逆圧縮の理論的な下限、すなわち情報源のエントロピー率であることが示されます。レートがエントロピー率より小さい場合、典型集合を全て符号化することは不可能であり、したがって任意に小さな誤り確率で復元することはできないことが示されます。
このように、定常エルゴード性という確率過程の性質が、エントロピー率という情報量の尺度を定義可能にし、さらにAEPを通じて可逆圧縮の理論的な限界を明確に定めているのです。
当時の背景と現代への影響
シャノンが定常エルゴード情報源に注目した背景には、現実世界の通信システムにおける情報源（例えば、音声信号、画像データ、テキストなど）の複雑な統計的構造を、単純なi.i.d.やマルコフモデルだけでなく、より普遍的な枠組みで捉えようという意図があったと考えられます。定常性とエルゴード性は、多くの現実的な情報源が満たすと期待される基本的な性質であり、これらの性質を持つ情報源に対して普遍的に適用できる理論を構築することは、情報理論の実用性にとって極めて重要でした。
シャノンによる定常エルゴード情報源の分析とAEPの確立は、その後の情報理論、特に情報源符号化理論の発展に不可欠な基礎を与えました。現代の情報科学においても、統計的モデリング、時系列解析、信号処理、自然言語処理、そして機械学習におけるデータ生成プロセスの理解において、定常性やエルゴード性といった概念は依然として中心的な役割を果たしています。情報源のエントロピー率を推定することは、データの圧縮限界を知る上で重要であり、また情報源の複雑性を測る指標としても利用されます。AEPは、統計的推論や学習理論における漸近的な性質の解析においても、情報理論的な視点を提供しています。
結論
クロード・シャノンの情報理論における定常エルゴード情報源の概念は、情報源の不確実性を測るエントロピー率の定義を可能にし、ソース符号化理論の根幹をなす漸近等分割性（AEP）の基盤を提供しました。定常性とエルゴード性という確率過程の性質を導入することで、シャノンはi.i.d.やマルコフ源といった単純なモデルを超え、より一般的で現実的な情報源クラスに対して普遍的に適用可能な理論的枠組みを構築しました。
定常エルゴード情報源のエントロピー率は、情報源のシンボル1つあたりが持つ本質的な情報量であり、その情報源の可逆圧縮の理論的な限界値となります。AEPは、このエントロピー率に基づいて典型系列の統計的性質を明らかにし、効率的なソース符号化方式の存在可能性を示しました。
シャノンによるこれらの概念の導入と分析は、情報理論を単なる数学的な抽象論に留めず、現実世界の通信やデータ処理の問題に応用可能な強力なツール体系たらしめる上で、極めて重要な貢献であったといえます。定常エルゴード情報源に関するシャノンの洞察は、現代においても様々な分野の研究においてその価値を保ち続けています。