3.4 エルゴード性と時間平均

ここまでは期待値の話だった．ブロックエントロピーも条件付きエントロピーも，情報源の分布から計算される数であって，実際に出てきた 1 本の系列を見て決まる量ではない．第2章の漸近等分配性（定理 2.1.4）は，そこを一歩進めて「実現ごとの値が $𝐻 (𝑋)$ に近づく」と述べていた．同じことを定常情報源で言いたい．

しかし定常性だけでは言えない．定常性は「窓をどこに置いても分布は同じ」としか言っておらず，「1 本の系列が情報源の全体を代表する」とは言っていないからである．この二つは別のことで，食い違う情報源を作るのは難しくない．時間平均が実現ごとに違う値に落ち着いてしまえば，それが期待値に一致するはずもない．足りない仮定を補うのが本節のエルゴード性である．

定義

定義 3.4.1（エルゴード性）. 情報源の実現 $𝑋 : = (𝑋 0, 𝑋 1, 𝑋 2, \dots)$ は無限系列の集合 $X ℕ$ に値をとる．先頭の 1 文字を捨てる写像

𝜎 (𝑥 0, 𝑥 1, 𝑥 2, \dots) : = (𝑥 1, 𝑥 2, 𝑥 3, \dots)

を シフト という．集合 $𝐵 \subseteq X ℕ$ が不変であるとは，任意の $𝑥 \in X ℕ$ について $𝑥 \in 𝐵$ と $𝜎 𝑥 \in 𝐵$ が同値であることをいう．定常情報源が エルゴード的 であるとは，確率の定まる不変集合 $𝐵$ がつねに $P r [𝑋 \in 𝐵] \in {0, 1}$ を満たすことをいう．

不変集合とは「先頭を何文字捨てても所属が変わらない」性質のことである．たとえば「 $1$ の相対頻度が $0.5$ に収束する系列の全体」は不変である．有限個の文字を落としても極限は動かないからである．エルゴード性は，そういう性質がどれも「ほとんどすべての系列がもつ」か「ほとんどどの系列ももたない」かのどちらかだ，と要求している．禁じているのは中間（たとえば半分の系列だけがもつ性質）が現れることである．

形式化: ErgodicProcess (ソース)

例 3.4.2（定常だがエルゴードでない情報源）. 公平なコインを最初に一度だけ投げる．表が出たら，以後は公平なコインを投げ続けて出目をそのまま出力する．裏が出たら，以後は $1$ の出る確率が $0.1$ に偏ったコインを投げ続ける．二つの分布をそれぞれ $𝑝 1 (1) = 0.5$ ， $𝑝 2 (1) = 0.1$ と書く．

定常である. ブロックの確率は，どの $ℓ$ についても

P r [𝑋 ℓ = 𝑥 0, \dots, 𝑋 ℓ + 𝑛 - 1 = 𝑥 𝑛 - 1] = 12 𝑛 - 1 \prod 𝑖 = 0 𝑝 1 (𝑥 𝑖) + 12 𝑛 - 1 \prod 𝑖 = 0 𝑝 2 (𝑥 𝑖)

である．最初のコインの結果を固定すればそのあとは i.i.d. で，i.i.d. 情報源は定常（例 3.1.2）だからで， $ℓ$ に依らない式になっている．

エルゴード的でない. $𝐵$ を「 $1$ の相対頻度が $0.5$ に収束する系列の全体」とすると，有限個の文字を落としても極限は動かないので $𝐵$ は不変である．第2章で借りた大数の強法則より，最初のコインが表なら確率 1 で $𝑋 \in 𝐵$ ，裏なら相対頻度が $0.1$ に収束するので確率 1 で $𝑋 \notin 𝐵$ である．よって $P r [𝑋 \in 𝐵] = 1 / 2$ で， $0$ でも $1$ でもない．

1 本の系列は全体を代表しない. 例 3.4.2 では，実現ごとに「自分がどちらの世界にいるか」が最初に決まってしまい，あとからどれだけ長く観測してもその決定は覆らない．時間平均は $0.5$ か $0.1$ のどちらかで，情報源全体の平均 $0.3$ はどの実現にも現れない．定常性は守られているのに，時間平均と期待値が食い違っている．エルゴード性はこの食い違いを，定義のうえで直接禁じたものである．

どんな情報源がエルゴード的か. i.i.d. 情報源はエルゴード的である．また例 3.1.5 のように，どの状態からどの状態へも有限歩で到達できるマルコフ情報源もエルゴード的である．どちらも本書では証明せず，形式化もされていない（前者は独立列の 0-1 法則から，後者は到達可能性から従う）．どちらも本章の主張の根拠には使わず，第2章との関係を述べるためだけに置く．第2章の情報源はすべて前者にあたるので，本章は第2章の設定を真に広げていることになる．

時間平均と期待値

道具を一つ借りる．Birkhoff の個別エルゴード定理，すなわち「エルゴード的な定常情報源では，実現の関数の時間平均がその期待値に確率 1 で収束する」という定理である．使う形を書いておく．

${𝑋 𝑖}$ をエルゴード的な定常情報源， $𝑋$ をその実現とする．実現の動く空間は片側の系列 $X ℕ$ でも，3.5 節で使う「負の時刻まで延ばした両側の系列」 $X ℤ$ でもよく， $𝜎$ はそのシフトとする．系列の関数 $𝑓$ は， $𝑓 (𝑋)$ がふたたび確率変数になるものとする．この $𝑓$ が確率 1 で有限な値をとり $𝔼 [| 𝑓 (𝑋) |] < \infty$ を満たすなら，確率 1 で

1 𝑛 𝑛 - 1 \sum 𝑖 = 0 𝑓 (𝜎 𝑖 𝑋) ⟶ 𝔼 [𝑓 (𝑋)] (𝑛 \to \infty) .

本章の主張がこの定理に依拠するのは 3.5 節の補題 3.5.6 と補題 3.5.8 の二つの証明だけで，他の主張はすべてこの二つを経由してのみ依存する（以下の二段落は，定理の読み方を説明するために当てて見せるだけで，本章の主張の根拠にはならない）．章の外では，第15章定理 15.6.1 の証明がこの定理を直接当て，同章 15.7 節が借りる無限の過去を使う戦略の収束と記憶が伸びる戦略の収束の筋書きもこれを当てる．どちらもアルファベットが株価比の有限集合になるだけで，上に書いた形の射程は広がらない．

時間平均と空間平均. 左辺は 1 本の系列に沿って時刻を動かした平均で，右辺は情報源のすべての実現にわたる平均である．前者は観測から計算できるが，後者は分布を知らないと計算できない．定理はこの二つが一致すると言っている．長く観測することが，多数の実現を集めることの代わりになる，ということである．統計にとってはこれが基本の一手で，1 本の時系列から情報源の性質を推定してよい根拠がここにある．

第2章の道具の一般化. $𝑓 (𝑥) : = 𝑔 (𝑥 0)$ ，すなわち先頭の文字だけで決まる関数をとると，左辺は $1 𝑛 \sum 𝑛 - 1 𝑖 = 0 𝑔 (𝑋 𝑖)$ ，右辺は $𝔼 [𝑔 (𝑋 0)]$ になる．i.i.d.情報源に当てはめれば，これは第2章が借りた大数の強法則そのものである．Birkhoff の定理は独立性という仮定を定常性とエルゴード性に置き換えたもので，第2章が借りた道具を，本章はより弱い仮定のもとで借り直したことになる．

エルゴード性がどこで効くか. 例 3.4.2 の情報源にこの定理を当てようとすると， $𝑓 (𝑥) : = 𝑥 0$ で左辺は $0.5$ か $0.1$ ，右辺は $0.3$ となって成り立たない．定理が言っているのは時間平均が定数に収束するということで，定数になるのは不変な量が確率 1 で一つの値しかとらないときに限る．それがエルゴード性の内容そのものである．

本書ではこの定理を証明しない．標準的な証明は極大エルゴード不等式（有限個の部分和の上限が正になる集合の上では，平均をとる関数の積分が非負になる）を経由するもので，形式化も同じ道をとっている．「本書で証明しない」ことと「形式化されていない」ことは別である．本節が借りた定理は，本書が証明を載せないだけで，無条件の機械検証済みの定理として形式化されている．

形式化: birkhoff_ergodic_ae，極大エルゴード不等式 maximal_ergodic_inequality (ソース)

形式化上の注記. 形式化は 3.1 節と同じ測度保存力学系の形をとるので，この定理も「 $𝜇$ を保つエルゴード的な写像 $𝑇$ と可積分な $𝑓 : Ω \to ℝ$ 」に対する主張として書かれている．本文の $𝑓 (𝜎 𝑖 𝑋)$ は，そちらでは $𝑓 (𝑇 𝑖 𝜔)$ にあたる．

時間平均の分母は $𝑛 + 1$ で， $𝑖$ は $0$ から $𝑛$ まで走る（ $𝑛 = 0$ での零割を避けるため）．極限としては本文の形と同じだが，有限の $𝑛$ で式を突き合わせるときは添字が 1 つずれる．

InformationTheory — 形式化検証つき情報理論教科書（レビュー版）．数式は MathJax + AMS Euler で事前レンダリング．