シャノン研究ノート - クロード・シャノンによる情報源の定常性とエルゴード性：その数学的定義と情報源符号化定理への応用

クロード・シャノンによる情報源の定常性とエルゴード性：その数学的定義と情報源符号化定理への応用

Tags: 情報源, 定常性, エルゴード性, 情報源符号化, AEP

はじめに

クロード・シャノンの記念碑的な論文『A Mathematical Theory of Communication』は、情報理論の基礎を確率論の上に構築しました。この理論体系の中核をなす概念の一つに「情報源（Information Source）」があり、その出力は確率的な系列としてモデル化されます。特に、情報源符号化定理（Source Coding Theorem）、あるいはより深くは漸近等分割性（Asymptotic Equipartition Property, AEP）の議論において、情報源が持つ特定の確率的な性質、すなわち「定常性（Stationarity）」と「エルゴード性（Ergodicity）」が極めて重要な役割を果たします。

これらの性質は、情報源から得られる長い系列の統計的性質が時間的に変化せず、かつ、一つの典型的な長い系列から情報源全体の統計的性質を推定できることを保証します。これは、無限の長さを持ちうる情報源の出力系列を、有限の観測に基づいて解析し、効率的な圧縮符号を設計するための数学的な基盤を提供します。本稿では、シャノンの情報理論における定常性およびエルゴード性の定義、その数学的意義、そして情報源符号化定理への具体的な応用について掘り下げて解説いたします。

情報源の数学的モデル化と確率過程

シャノンは情報源の出力を、記号の系列を生成する確率的なメカニズムとしてモデル化しました。離散無記憶情報源のように最も単純なモデルでは、各記号が独立かつ同一の確率分布に従って生成されます。しかし、多くの現実の情報源（例えば自然言語のテキストや音声信号）は、記号間に統計的な依存関係を持ちます。このような情報源は、より一般的に確率過程として記述されます。

離散時間確率過程 ${X_i}{i \in \mathbb{Z}}$ は、各時刻 $i$ において、あるアルファベット $\mathcal{A}$ から値をとる確率変数 $X_i$ の列です。情報源は、この確率過程が生成する無限の系列 $x_1, x_2, \dots$ を出力すると考えられます。情報源の統計的性質は、この確率過程を完全に記述する結合確率分布 $P(X{i_1}=x_{i_1}, X_{i_2}=x_{i_2}, \dots, X_{i_n}=x_{i_n})$ によって特徴づけられます。

定常性の定義と情報理論における意義

定常性は、情報源の確率的な性質が時間と共に変化しないことを意味します。厳密には、いくつかの異なる定義が存在しますが、情報理論で主に扱われるのは狭義の定常性（Strict Stationarity）です。

狭義の定常性

確率過程 ${X_i}_{i \in \mathbb{Z}}$ が狭義定常であるとは、任意の正の整数 $n$、任意の時刻の集合 $i_1, i_2, \dots, i_n \in \mathbb{Z}$、および任意の時間シフト $\tau \in \mathbb{Z}$ に対して、同時確率分布が以下を満たすことをいいます。

$P(X_{i_1}=x_1, X_{i_2}=x_2, \dots, X_{i_n}=x_n) = P(X_{i_1+\tau}=x_1, X_{i_2+\tau}=x_2, \dots, X_{i_n+\tau}=x_n)$

これは、情報源から観測される任意の有限長系列 $x_{i_1}, \dots, x_{i_n}$ の出現確率が、その系列がどの時間帯（$i_1$ から始まるか、$i_1+\tau$ から始まるか、など）で観測されたかに依存しないことを意味します。簡単に言えば、情報源は常に同じ統計的な「振る舞い」をするということです。

情報理論において定常性は非常に重要です。なぜなら、情報源から出力される系列の統計的性質を時間を通じて一定とみなせる場合、長期的な平均挙動（例えばエントロピー率）を議論することが可能となるからです。これにより、無限長の系列に対する符号化の性能限界を、有限長の系列の統計量に基づいて推論する道が開かれます。

広義の定常性（弱定常性）

補足として、信号処理などで用いられる広義の定常性（Wide-Sense Stationarity, WSS）にも触れておきます。これは、平均と自己相関関数が時間によらず一定であるという性質です。

平均：$E[X_i] = \mu$ （任意の $i$ に対して一定）
自己相関関数：$R(i, j) = E[X_i X_j] = E[X_{i+k} X_{j+k}] = R(j-i)$ （時間の差のみに依存）

狭義定常性は広義定常性よりも強い条件ですが、ガウス過程の場合は狭義定常性と広義定常性が等価になります。シャノンの情報理論では、一般的には狭義定常性が仮定されることが多いです。

エルゴード性の定義と情報理論における意義

定常性だけでは不十分な場合があります。例えば、ある情報源が2つの異なる統計的性質を持つ状態を一定の確率でとり、一度どちらかの状態に入ると二度と他方の状態に移らないような場合を考えます。これは定常過程になりえますが、単一の長い系列を観測しても、どちらの状態が選ばれたかによってその統計的性質は異なり、情報源全体の平均的な性質（例えば、2つの状態のエントロピー率の平均）を推定することはできません。

ここでエルゴード性が登場します。エルゴード性とは、確率過程の「時間平均」が「アンサンブル平均」に一致するという性質です。

アンサンブル平均: ある固定時刻 $i$ における確率変数 $X_i$ の期待値 $E[X_i]$ や、複数の時刻にわたる結合分布の期待値など、確率空間全体にわたって平均をとった値です。
時間平均: ある一つの実現した長い系列 $x_1, x_2, \dots$ に沿って、ある統計量（例えば記号の出現頻度）の平均をとった値です。例えば、系列の最初の $N$ 個の記号 $x_1, \dots, x_N$ における特定の記号 $a \in \mathcal{A}$ の出現頻度は $\frac{1}{N} \sum_{i=1}^N \mathbf{1}_{x_i=a}$ です。

エルゴード過程においては、十分長い系列を観測することで得られる時間平均が、その過程の確率分布全体から計算されるアンサンブル平均に確率的に収束します。数学的には、任意の関数 $f$ に対して、もし期待値 $E[f(X_i, X_{i+1}, \dots, X_{i+k})]$ が存在すれば、多くの場合、以下の形式で表現されるエルゴード定理が成り立ちます。

$\lim_{N \to \infty} \frac{1}{N} \sum_{i=1}^N f(X_i, X_{i+1}, \dots, X_{i+k}) = E[f(X_0, X_1, \dots, X_k)]$ (確率収束や概収束の意味で)

情報理論においてエルゴード性は、情報源の統計的性質を推定する上で極めて重要です。例えば、情報源のエントロピー率 $H(\mathcal{X})$ はアンサンブル平均に関する概念です。エルゴード性が成り立てば、一つの長い観測系列 $x_1, \dots, x_N$ から計算される経験的エントロピー（経験的確率分布に基づくエントロピー）が、真のエントロピー率に収束することが保証されます。

$\lim_{N \to \infty} -\frac{1}{N} \log_2 P(x_1, \dots, x_N) = H(\mathcal{X})$ (確率収束の意味で、定常エルゴード情報源に対して)

これは漸近等分割性（AEP）の核心部分であり、情報源符号化定理の証明に不可欠な性質です。

定常エルゴード情報源と漸近等分割性 (AEP)

シャノンの情報源符号化定理は、定常かつエルゴード性の仮定の下で証明されます。この定理は、情報源のエントロピー率 $H$ が、系列を可逆的に圧縮する際の理論的な限界（ビット/記号）を与えることを主張します。この証明の中心的なツールがAEPです。

AEPは、定常エルゴード情報源から生成される十分長い系列のほとんどが、「典型集合（Typical Set）」と呼ばれる小さな集合の中に含まれることを示します。長さ $N$ の系列 $x_1, \dots, x_N$ が典型集合に属するための条件は、おおよそ以下のように記述されます。

$-\frac{1}{N} \log_2 P(x_1, \dots, x_N) \approx H(\mathcal{X})$

すなわち、典型系列は、その対数確率が情報源のエントロピー率によって特徴づけられる系列です。AEPが示す重要な性質は以下の通りです。

ほとんどの系列は典型的である: 長さ $N$ の系列が典型的である確率は、$N \to \infty$ のとき1に近づきます。
典型集合のサイズ: 典型集合に含まれる系列の数は、おおよそ $2^{N H(\mathcal{X})}$ です。
典型集合の全確率: 典型集合の系列の合計確率は、1に非常に近いです。

これらの性質は、エルゴード定理を用いて厳密に証明されます。エルゴード性は、長い系列における特定のパターンの出現頻度（時間平均）が、そのパターンのアンサンブル平均的な確率に収束することを保証します。この収束を用いて、系列全体の同時確率の対数 $-\frac{1}{N} \log_2 P(x_1, \dots, x_N)$ が、エントロピー率 $H(\mathcal{X})$ に収束することが導かれます。これは、古典的な大数の法則の確率過程への拡張と見なすこともできます。

AEPが情報源符号化にどのように応用されるかというと、まず情報源が生成しうる全 $ |\mathcal{A}|^N $ 個の系列のうち、符号化対象とするのは典型集合内の系列のみとします。典型集合のサイズは約 $2^{N H(\mathcal{X})}$ であるため、これらの系列を一意に識別するためには、約 $N H(\mathcal{X})$ ビットが必要です。これにより、記号あたり約 $H(\mathcal{X})$ ビットでの符号化が可能となります。典型集合に含まれない非典型系列の確率は非常に小さいため、これらの系列を無視するか、あるいは特定の符号語を割り当てることで、全体の平均符号長はほぼ $H(\mathcal{X})$ に抑えられ、かつ誤り確率を任意に小さくすることが可能です。これがシャノンの情報源符号化定理の基本的なアイデアです。

歴史的背景と現代における意義

シャノンが情報理論を構築する上で、定常性とエルゴード性の概念を援用したのは自然な流れでした。これらの概念は、既に統計力学や確率論において、系の時間平均的な挙動とアンサンブル平均的な挙動の関係を説明するために用いられていたからです。特にボルツマンのエントロピー概念やエルゴード仮説との間には深い関連があります。シャノンはこれらの数学的ツールを情報通信という全く新しい分野に応用し、理論の厳密な基礎を築きました。

現代の情報科学においても、定常性とエルゴード性は基本的な概念であり続けています。

データ圧縮: Ziv-Lempel符号化のような適応的な圧縮アルゴリズムは、明示的に定常性やエルゴード性を仮定しない場合でも、観測データから統計的性質（例えば記号の出現確率や文脈における条件付き確率）を推定し、それに基づいて符号を構築します。これは、基礎となる情報源が（局所的にでも）定常またはエルゴード的であるという仮定や期待に基づいています。
時系列解析: 金融データ、音声信号、脳波などの時系列データを分析する際、定常性の有無はモデル選択や解析手法の重要な判断基準となります。エルゴード性は、単一の時系列データから統計的な性質を推定できるかどうかの基盤となります。
機械学習: 特に確率モデルや強化学習の分野では、データ生成過程の定常性やマルコフ性（これはより単純な依存構造を持つ確率過程の一種であり、適切な条件下でエルゴード性を持つ）がしばしば仮定されます。状態空間モデルや隠れマルコフモデルなどは、確率過程の理論に基づいています。

定常性やエルゴード性が成り立たない情報源に対しては、その統計的性質が時間と共に変化したり、単一の系列から全体の統計量を推定できなかったりするため、異なるアプローチが必要となります。非定常情報源や非エルゴード情報源に対する符号化や解析は、より複雑な課題となります。

結論

クロード・シャノンが情報理論の基礎を確立するにあたり導入した情報源のモデル化において、定常性とエルゴード性は不可欠な数学的性質でした。定常性は情報源の統計的性質が時間的に不変であることを、エルゴード性は時間平均とアンサンブル平均の一致を保証します。これらの性質は、情報源符号化定理（AEP）の証明において、無限長の系列から生成される典型的な有限長系列が持つ統計的性質を定量化し、可逆圧縮の限界であるエントロピー率を厳密に定義するための基盤を提供しました。

定常エルゴード情報源という理想化されたモデルは、多くの現実の情報源の振る舞いを理解し、効率的なデータ圧縮や通信方式を設計するための出発点となります。これらの基本的な概念は、現代の情報科学、統計学、さらには物理学における確率過程の理解においても、その重要性を失っていません。シャノンの理論における定常性とエルゴード性の位置づけを深く理解することは、情報理論および関連分野の研究を進める上で、今なお非常に重要であると言えるでしょう。