3.5 Shannon–McMillan–Breiman 定理

第2章の漸近等分配性（定理 2.1.4）は，i.i.d. 情報源で 1 文字あたりの驚きが $𝐻 (𝑋)$ に近づく，という主張だった．本節はそれをエルゴード的な定常情報源に広げる．近づく先は $𝐻 (𝑋)$ ではなくエントロピーレート $𝐻 (X)$ で，収束は概収束（確率 1 の事象の上で各点の収束）である．この一般化を Shannon–McMillan–Breiman 定理という．

まず量の名前を用意する．

定義 3.5.1（経験エントロピー）. 情報源 ${𝑋 𝑖}$ に対し，ブロックの確率を $𝑝 (𝑥 𝑛) : = P r [𝑋 𝑛 = 𝑥 𝑛]$ と書く． $𝑛 \geq 1$ に対し

ˆ 𝐻 𝑛 : = - 1 𝑛 l o g 𝑝 (𝑋 𝑛)

を長さ $𝑛$ の 経験エントロピー という．

式は定義 2.1.1 とまったく同じで，i.i.d. の仮定を外して同じ量を使う，という宣言である．違いは使える道具のほうにある．あちらでは独立性から $𝑝 (𝑋 𝑛)$ が周辺分布の積にほどけ（補題 2.1.3），大数の法則にかけられる形になった．記憶のある情報源ではこのほどきが使えない．ほどく代わりに何をするかが，本節の中身である．

確率 $0$ のブロックが実現する事象は，各 $𝑛$ で高々有限個の確率 $0$ の事象の和だから確率 $0$ である．したがって実現したブロックの確率は確率 1 で正で， $ˆ 𝐻 𝑛$ は確率 1 で定まる有限の値をとる．

形式化: 経験エントロピーにあたる定義 blockLogAvg (ソース)

定理 3.5.2（Shannon–McMillan–Breiman）. ${𝑋 𝑖}$ をエルゴード的な定常情報源とする．確率 1 で

ˆ 𝐻 𝑛 = - 1 𝑛 l o g 𝑝 (𝑋 𝑛) ⟶ 𝐻 (X) (𝑛 \to \infty) .

証明は上下からの挟み撃ちで行う．上からは記憶を有限の深さで打ち切った近似を，下からは無限の過去まで使った近似を当てる．どちらの側でも働くのは「確率分布どうしの比の期待値は1 を超えない」という一手だけなので，それを先に補題として切り出しておく．証明本体は補題 3.5.7 と補題 3.5.8 で，二つがそろったところで定理 3.5.2 の証明に戻る．

借りる道具

3.4 節の Birkhoff の個別エルゴード定理に加えて，下界（補題 3.5.8）の証明でだけ次の二つを借りる．上界（補題 3.5.7）はどちらも使わない．

両側への拡張. 定常情報源 ${𝑋 𝑖} 𝑖 \geq 0$ に対し，負の時刻まで延ばした列 ${𝑋 𝑖} 𝑖 \in ℤ$ で，定常であり，かつ非負の時刻の部分の同時分布が元の情報源と一致するものが存在する．元がエルゴード的なら，延ばした列もシフトについてエルゴード的である．これは第15章 15.7 節が借り直す．そちらが当てるのもアルファベットが株価比の有限集合になるだけの定常列なので，射程は広がらない．

無限の過去による条件付け. 両側に延ばした列について，有限の過去で条件付けた確率 $𝑝 (𝑋 0 ∣ 𝑋 - 1, \dots, 𝑋 - 𝑘)$ は $𝑘 \to \infty$ で確率 1 で収束する．その極限を $𝑝 (𝑋 0 ∣ 𝑋 - 1, 𝑋 - 2, \dots)$ と書く．さらに期待値も収束し，

𝔼 [- l o g 𝑝 (𝑋 0 ∣ 𝑋 - 1, 𝑋 - 2, \dots)] = l i m 𝑘 \to \infty 𝐻 (𝑋 0 ∣ 𝑋 - 1, \dots, 𝑋 - 𝑘)

が成り立つ．これは，増えていく情報で条件付けた確率が，その全体で条件付けた確率に確率 1 で収束するという Lévy のマルチンゲール収束定理と，期待値の側でその収束を許す優収束定理から得られる．

この極限について，以下では有限個の条件付けと同じ二つの操作を認めて使う．第一に，各時刻 $𝑖$ の条件付き確率 $𝑝 (𝑋 𝑖 ∣ 𝑋 𝑖 - 1, 𝑋 𝑖 - 2, \dots)$ が同じように定まり，その積が「無限の過去 $P : = (𝑋 - 1, 𝑋 - 2, \dots)$ を与えたときの $𝑋 𝑛$ の条件付き確率」 $𝑝 (𝑋 𝑛 ∣ P)$ に等しいこと．これが条件付き確率のチェイン則である．第二に， $P$ の実現ごとに $𝑋 𝑛$ の分布 $𝑝 (\cdot ∣ P)$ が定まり，期待値が「 $P$ を固定してとる期待値」と「 $P$ についてとる期待値」の二段に分かれること．有限個の条件付けなら第1章の道具から出るが，無限の過去についてはここで認める．これは第15章 15.7 節も引く．そちらが節の終わりで借りる二つは，無限の過去のもとでの $𝑋 0$ の条件付き分布をこの極限として読み，その筋書きは，各期の条件付き評価を $𝑛$ 期ぶんの積へ渡す段が上の二つの操作の外に出ることを，足りないものとして名指す．当てる対象は同じく株価比の有限集合に値をとる定常列なので，射程は広がらない．

以上はどれも本書では証明しないが，3.4 節の Birkhoff の定理と同じく，無条件の機械検証済みの定理として形式化されている．

形式化: 両側への拡張 μZ，非負の時刻での一致 μZ_nat_proj_eq，シフトの測度保存性measurePreserving_shiftZ，エルゴード性 ergodic_shiftZ (ソース)，Lévy の収束condProbPast_tendsto_condProbInfty とその極限 condProbInfty (ソース)，無限の過去で条件付けた負対数の期待値 integral_pmfLogCondInfty_eq_entropyRate (ソース)

形式化上の注記. 期待値の等式は，形式化では右辺を条件付きエントロピーの極限ではなくエントロピーレートそのものとして述べている．本文が補題 3.5.8 の冒頭で定常性と定理 3.2.6 を経由して書き換える 2 段が，あちらでは 1 本の宣言に畳み込まれている．

比は指数の尺度では見えない

補題 3.5.3. 非負の確率変数の列 $(Λ 𝑛) 𝑛 \geq 1$ が任意の $𝑛$ で $𝔼 [Λ 𝑛] \leq 1$ を満たすなら，確率 1 で

l i m s u p 𝑛 \to \infty 1 𝑛 l o g Λ 𝑛 \leq 0

である（ $Λ 𝑛 = 0$ のときは $l o g Λ 𝑛 = - \infty$ と読む）．

証明. $𝐴 𝑛 : = {Λ 𝑛 \geq 𝑛 2}$ とおく． $Λ 𝑛 \geq 0$ だから Markov の不等式が使えて $P r [𝐴 𝑛] \leq 𝔼 [Λ 𝑛] / 𝑛 2 \leq 1 / 𝑛 2$ である．したがって任意の $𝑁 \geq 1$ に対し

P r [⋃ 𝑛 \geq 𝑁 𝐴 𝑛] \leq \sum 𝑛 \geq 𝑁 1 𝑛 2

であり， $\sum 𝑛 𝑛 - 2$ が収束するので右辺は $𝑁 \to \infty$ で $0$ に向かう．左辺は $𝑁$ について非増加だから，「 $𝐴 𝑛$ が無限回起こる」事象 $⋂ 𝑁 ⋃ 𝑛 \geq 𝑁 𝐴 𝑛$ の確率は $0$ である．

すなわち確率 1 で，十分大きなすべての $𝑛$ について $Λ 𝑛 < 𝑛 2$ ，したがって

1 𝑛 l o g Λ 𝑛 < 2 l o g 𝑛 𝑛

である．右辺は $0$ に収束するので，上極限は $0$ 以下である． $◻$

補題 3.5.3 が言っているのは，期待値が 1 で抑えられた比は $𝑛 2$ より速くは大きくならず， $1 𝑛 l o g$ という尺度ではそれが $0$ に潰れる，ということである．第2章の議論が指数の肩を $1 / 𝑛$ の精度でしか見ていなかったのと同じ粗さで，この粗さのおかげで「多項式ぶんのずれ」は最初から見えない．

記憶を $𝑘$ 文字で打ち切る

記憶の深さを $𝑘$ 文字に制限した近似分布を作る．

定義 3.5.4（ $𝑘$ 次打ち切り近似）. 定常情報源 ${𝑋 𝑖}$ ， $𝑘 \geq 0$ ， $𝑛 > 𝑘$ に対し

𝑞 𝑘 (𝑥 𝑛) : = 𝑝 (𝑥 𝑘) 𝑛 - 1 \prod 𝑖 = 𝑘 𝑝 (𝑥 𝑖 ∣ 𝑥 𝑖 - 𝑘, \dots, 𝑥 𝑖 - 1)

と定める．ここで $𝑝 (𝑥 𝑖 ∣ 𝑥 𝑖 - 𝑘, \dots, 𝑥 𝑖 - 1)$ は，定常性により時刻に依らない量 $P r [𝑋 𝑘 = 𝑥 𝑖 ∣ 𝑋 𝑘 = (𝑥 𝑖 - 𝑘, \dots, 𝑥 𝑖 - 1)]$ を表す（ $𝑝 (𝑥 0) : = 1$ ．条件にあたる長さ $𝑘$ の並びの確率が $0$ のときは $𝑞 𝑘 (𝑥 𝑛) : = 0$ と約束する）．

これは「直前の $𝑘$ 文字しか覚えていない情報源」が同じブロックに与える確率である． $𝑘 = 0$ なら 1 文字ずつ独立に出す情報源， $𝑘 = 1$ ならマルコフ情報源（3.3 節）にあたる．真の分布と違って総和はちょうど 1 にならないが，超えることはない．

補題 3.5.5. 定義 3.5.4 の $𝑞 𝑘$ は，任意の $𝑘 \geq 0$ と $𝑛 > 𝑘$ に対し $\sum 𝑥 𝑛 \in X 𝑛 𝑞 𝑘 (𝑥 𝑛) \leq 1$ を満たす．

証明. 後ろの文字から順に和をとる．最後の文字 $𝑥 𝑛 - 1$ について和をとると，条件にあたる $(𝑥 𝑛 - 1 - 𝑘, \dots, 𝑥 𝑛 - 2)$ の確率が正なら条件付き確率の和はちょうど 1 で，確率が $0$ なら約束により和は $0$ である．いずれにせよ 1 以下だから，全体は $𝑞 𝑘$ の $𝑥 𝑛 - 1$ までの部分で抑えられる．同じことを $𝑥 𝑘$ まで繰り返すと $\sum 𝑥 𝑘 𝑝 (𝑥 𝑘) = 1$ が残る． $◻$

補題 3.5.6. ${𝑋 𝑖}$ をエルゴード的な定常情報源とする．各 $𝑘 \geq 0$ に対し，確率 1 で

- 1 𝑛 l o g 𝑞 𝑘 (𝑋 𝑛) ⟶ 𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘) (𝑛 \to \infty) .

証明. 実現した並びの確率は確率 1 で正だから， $𝑝 (𝑋 𝑘) > 0$ であり，また $𝑘 \leq 𝑖 \leq 𝑛 - 1$ の各 $𝑖$ について長さ $𝑘 + 1$ の並び $(𝑋 𝑖 - 𝑘, \dots, 𝑋 𝑖)$ の確率も正である．後者から各段の条件付き確率 $𝑝 (𝑋 𝑖 ∣ 𝑋 𝑖 - 𝑘, \dots, 𝑋 𝑖 - 1)$ が正なので，確率 1 で $𝑞 𝑘 (𝑋 𝑛) > 0$ である．対数をとって

- 1 𝑛 l o g 𝑞 𝑘 (𝑋 𝑛) = - 1 𝑛 l o g 𝑝 (𝑋 𝑘) + 1 𝑛 𝑛 - 1 \sum 𝑖 = 𝑘 (- l o g 𝑝 (𝑋 𝑖 ∣ 𝑋 𝑖 - 𝑘, \dots, 𝑋 𝑖 - 1))

と分かれる．第 1 項は $𝑛$ に依らない確率変数を $𝑛$ で割ったものだから $0$ に収束する．

第 2 項に 3.4 節の Birkhoff の定理を当てる．先頭 $𝑘 + 1$ 文字だけで決まる関数

𝑓 𝑘 (𝑥) : = - l o g 𝑝 (𝑥 𝑘 ∣ 𝑥 0, \dots, 𝑥 𝑘 - 1)

をとると， $- l o g 𝑝 (𝑋 𝑖 ∣ 𝑋 𝑖 - 𝑘, \dots, 𝑋 𝑖 - 1) = 𝑓 𝑘 (𝜎 𝑖 - 𝑘 𝑋)$ である（条件付き確率を時刻に依らない量にとったのは定義 3.5.4 の側なので，ここは定義の書き換えにすぎない）． $𝑗 : = 𝑖 - 𝑘$ と置き換えると第 2 項は

1 𝑛 𝑛 - 𝑘 - 1 \sum 𝑗 = 0 𝑓 𝑘 (𝜎 𝑗 𝑋) = 𝑛 - 𝑘 𝑛 \cdot 1 𝑛 - 𝑘 𝑛 - 𝑘 - 1 \sum 𝑗 = 0 𝑓 𝑘 (𝜎 𝑗 𝑋)

になる． $𝑓 𝑘 \geq 0$ であり，その期待値は定義 1.2.2 より $𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘)$ で，これは定理 1.2.4 と定理 1.1.5 より $l o g | X |$ 以下である．期待値が有限だから $𝑓 𝑘$ は確率 1 で有限な値をとり（確率 $0$ の並びの上で $+ \infty$ になりうるが，そこは期待値に効かない），3.4 節で借りた定理が要求する形を満たす．Birkhoff の定理より第 2 因子は確率 1 で $𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘)$ に収束し， $𝑛 - 𝑘 𝑛 \to 1$ と合わせて主張を得る． $◻$

形式化: negLogQk_div_tendsto_condEntropyTail (ソース)

上界

補題 3.5.7. ${𝑋 𝑖}$ をエルゴード的な定常情報源とする．確率 1 で $l i m s u p 𝑛 ˆ 𝐻 𝑛 \leq 𝐻 (X)$ ．

証明. $𝑘 \geq 0$ を固定する．確率 1 で $𝑝 (𝑋 𝑛) > 0$ だから

Λ 𝑛 : = 𝑞 𝑘 (𝑋 𝑛) 𝑝 (𝑋 𝑛) (𝑛 > 𝑘)

は確率 1 で定まる非負の確率変数である．補題 3.5.5 より，その期待値は

𝔼 [Λ 𝑛] = \sum 𝑥 𝑛 : 𝑝 (𝑥 𝑛) > 0 𝑝 (𝑥 𝑛) 𝑞 𝑘 (𝑥 𝑛) 𝑝 (𝑥 𝑛) = \sum 𝑥 𝑛 : 𝑝 (𝑥 𝑛) > 0 𝑞 𝑘 (𝑥 𝑛) \leq 1

である．補題 3.5.3 より確率 1 で $l i m s u p 𝑛 1 𝑛 l o g Λ 𝑛 \leq 0$ ，すなわち

1 𝑛 l o g Λ 𝑛 = ˆ 𝐻 𝑛 - (- 1 𝑛 l o g 𝑞 𝑘 (𝑋 𝑛))

と書き直して $l i m s u p 𝑛 (ˆ 𝐻 𝑛 - (- 1 𝑛 l o g 𝑞 𝑘 (𝑋 𝑛))) \leq 0$ である．補題 3.5.6 より引かれている側は $𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘)$ に収束するから

l i m s u p 𝑛 ˆ 𝐻 𝑛 \leq 𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘) .

これが各 $𝑘$ について確率 1 で成り立つ．可算個の確率 1 の事象の共通部分もまた確率 1 だから，確率 1 ですべての $𝑘$ について同時に成り立つ．そこで $𝑘 \to \infty$ とすれば，定理 3.2.6より右辺は $𝐻 (X)$ に収束する． $◻$

形式化: algoet_cover_limsup_bound (ソース)

下界

補題 3.5.8. ${𝑋 𝑖}$ をエルゴード的な定常情報源とする．確率 1 で $l i m i n f 𝑛 ˆ 𝐻 𝑛 \geq 𝐻 (X)$ ．

証明. 借りた両側への拡張により，以下では ${𝑋 𝑖}$ を $𝑖 \in ℤ$ に延ばしたエルゴード的な定常列とみなす．

𝑔 (𝑥) : = - l o g 𝑝 (𝑥 0 ∣ 𝑥 - 1, 𝑥 - 2, \dots)

とおくと

𝔼 [𝑔 (𝑋)] = l i m 𝑘 \to \infty 𝐻 (𝑋 0 ∣ 𝑋 - 1, \dots, 𝑋 - 𝑘) = l i m 𝑘 \to \infty 𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘) = 𝐻 (X)

である．最初の等号は借りた期待値の収束，真ん中の等号は両側列の定常性で時計を $𝑘$ ずらしただけ，最後の等号は定理 3.2.6 である． $𝑔 \geq 0$ の期待値が有限なのだから，とくに $𝑔$ は確率 1 で有限な値をとり，3.4 節で借りた定理を当てられる．

比の期待値を抑える. 無限の過去を $P : = (𝑋 - 1, 𝑋 - 2, \dots)$ と書き，

𝑞 \infty (𝑋 𝑛) : = 𝑛 - 1 \prod 𝑖 = 0 𝑝 (𝑋 𝑖 ∣ 𝑋 𝑖 - 1, 𝑋 𝑖 - 2, \dots)

とおく．借りた条件付き確率のチェイン則より，これは $P$ を与えたときの $𝑋 𝑛$ の条件付き確率 $𝑝 (𝑋 𝑛 ∣ P)$ にほかならない． $Λ 𝑛 : = 𝑝 (𝑋 𝑛) / 𝑞 \infty (𝑋 𝑛)$ とおくと， $P$ を固定した条件付き期待値は

𝔼 [Λ 𝑛 ∣ P] = \sum 𝑥 𝑛 𝑝 (𝑥 𝑛 ∣ P) 𝑝 (𝑥 𝑛) 𝑝 (𝑥 𝑛 ∣ P) = \sum 𝑥 𝑛 : 𝑝 (𝑥 𝑛 ∣ P) > 0 𝑝 (𝑥 𝑛) \leq 1

である．両辺の期待値をとって $𝔼 [Λ 𝑛] \leq 1$ を得る．

補題 3.5.3 を当てる. $1 𝑛 l o g Λ 𝑛 = (- 1 𝑛 l o g 𝑞 \infty (𝑋 𝑛)) - ˆ 𝐻 𝑛$ だから，確率 1 で

l i m s u p 𝑛 ((- 1 𝑛 l o g 𝑞 \infty (𝑋 𝑛)) - ˆ 𝐻 𝑛) \leq 0 .

一方 $- 1 𝑛 l o g 𝑞 \infty (𝑋 𝑛) = 1 𝑛 \sum 𝑛 - 1 𝑖 = 0 𝑔 (𝜎 𝑖 𝑋)$ であり，両側に延ばした列もエルゴード的な定常列だから，Birkhoff の定理よりこれは確率 1 で $𝔼 [𝑔 (𝑋)] = 𝐻 (X)$ に収束する． $𝑎 𝑛 : = ˆ 𝐻 𝑛$ ， $𝑏 𝑛 : = - 1 𝑛 l o g 𝑞 \infty (𝑋 𝑛)$ と書くと $𝑎 𝑛 = 𝑏 𝑛 - (𝑏 𝑛 - 𝑎 𝑛)$ だから

l i m i n f 𝑛 𝑎 𝑛 \geq l i m 𝑛 𝑏 𝑛 - l i m s u p 𝑛 (𝑏 𝑛 - 𝑎 𝑛) \geq 𝐻 (X)

である．

最後に，主張は $𝑋 𝑛$ だけで決まる量についてのものであり，両側に延ばした列の非負時刻の部分の分布は元の情報源と一致するから，元の情報源についても成り立つ． $◻$

形式化: algoet_cover_liminf_bound (ソース)

証明（定理 3.5.2）. 補題 3.5.7 と補題 3.5.8 より，確率 1 で

𝐻 (X) \leq l i m i n f 𝑛 ˆ 𝐻 𝑛 \leq l i m s u p 𝑛 ˆ 𝐻 𝑛 \leq 𝐻 (X)

である．したがって極限が存在し，その値は $𝐻 (X)$ である． $◼$

形式化: shannon_mcmillan_breiman (ソース)

二つの近似で挟む. 上からは記憶を $𝑘$ 文字で打ち切った $𝑞 𝑘$ を，下からは無限の過去まで使った $𝑞 \infty$ を当てた． $𝑞 𝑘$ は真の情報源より予測が下手で（記憶が浅い）， $𝑞 \infty$ は上手である（ $𝑋 𝑛$ の外にある情報まで使う）．上からの評価は $𝐻 (𝑋 𝑘 ∣ 𝑋 𝑘)$ で止まり， $𝑘 \to \infty$ で $𝐻 (X)$ まで下りてくる．下からの評価のほうは，Lévy の収束のおかげで最初から $𝐻 (X)$ ちょうどに着く．

同じ一手が両側で効く. 上界では $𝑞 𝑘 / 𝑝$ を，下界では $𝑝 / 𝑞 \infty$ を補題 3.5.3 に入れた．使ったのはどちらも「確率分布どうしの比の期待値は 1 を超えない」だけである．比が多項式ぶんしか増えないことが分かれば， $1 𝑛 l o g$ の尺度ではそれが消える．証明の仕事は，比の期待値が 1 以下になるように分母と分子を選ぶところに集中している．

なぜ無限の過去に出ていくのか. $𝑞 𝑘$ は $𝑋 𝑛$ だけの関数なので，分母に置いて下界にも使えそうに見える．しかし $𝑝 / 𝑞 𝑘$ の期待値は 1 で抑えられない． $𝑞 𝑘$ が極端に小さい並びで比が爆発しうるからである． $𝑞 \infty$ は $P$ を与えたときの $𝑋 𝑛$ の条件付き確率そのものなので， $P$ を固定して $𝑥 𝑛$ について和をとると，分母がそこで割り戻されて残るのは真の確率の総和になり，1 を超えない．効いているのは大小関係ではなく，分母がそれ自身の確率で重みづけされているという正規化である．負の時刻に出ていく理由はここにあり，両側への拡張はそのためだけに借りている．

期待値のレベルでは何が起きているか

命題 3.5.9. 任意の情報源と $𝑛 \geq 1$ に対し $𝔼 [ˆ 𝐻 𝑛] = 𝐻 𝑛 / 𝑛$ である．

証明. 定義 1.1.1 より $𝐻 𝑛 = 𝐻 (𝑋 𝑛) = - \sum 𝑥 𝑛 𝑝 (𝑥 𝑛) l o g 𝑝 (𝑥 𝑛) = 𝔼 [- l o g 𝑝 (𝑋 𝑛)]$ である．両辺を $𝑛$ で割れば，右辺は定義 3.5.1 の $ˆ 𝐻 𝑛$ の期待値である． $◼$

形式化: expected_blockLogAvg_eq (ソース)

命題 3.5.9 は定義を書き直しただけである．それでも役に立つのは，定理 3.2.6 と合わせると $𝔼 [ˆ 𝐻 𝑛] \to 𝐻 (X)$ が直ちに出るからである．つまり「平均すれば $𝐻 (X)$ に近づく」ところまでは，本節の道具を一つも使わずに言える．定理 3.5.2 が言い足しているのは「1 本 1 本の実現でもそうなる」という一点であり，Birkhoff の定理も両側への拡張も，その一点のためだけに要る．

第2章の符号化定理はどこまで生き延びるか

系 3.5.10. $| X | \geq 2$ とし，定常情報源に対して定義 2.3.1 のブロック情報源符号を考える．

情報源がさらにエルゴード的で $𝑅 > 𝐻 (X)$ ならば， $𝑅 𝑛 \to 𝑅$ かつ $𝑃 (𝑛) 𝑒 \to 0$ を満たす符号の族が存在する．
逆に，符号の族が $𝑃 (𝑛) 𝑒 \to 0$ を満たし，レートの列 $(𝑅 𝑛)$ が上に有界ならば $𝐻 (X) \leq l i m i n f 𝑛 𝑅 𝑛$ である．

証明. 主張 1 の達成可能性を示す．定義 2.2.1 の典型集合を， $𝐻 (𝑋)$ を $𝐻 (X)$ に， $𝑝$ をブロックの確率に読み替えて同じ式で定める．定理 3.5.2 は概収束を述べているので，2.1 節で借りた「概収束は確率収束を含む」より確率収束も従い，定理 2.2.3 の証明は定理 2.1.4 の確率収束しか使っていないから，そのまま通る．定理 2.2.4 は典型集合の定義の書き直しにすぎず，定理 2.2.5 は定理 2.2.3・定理 2.2.4 と「確率の総和が 1」しか使わない．したがって定理 2.3.2 の符号の構成がそのまま働く．

主張 2 の逆に移る．定理 2.3.4 の証明が i.i.d. を使っているのは，補題 2.3.3 で $𝐻 (𝑋 𝑛) = 𝑛 𝐻 (𝑋)$ と書き換える 1 箇所だけである．そこを $𝐻 (𝑋 𝑛) = 𝐻 𝑛$ と読み替えると残りはそのまま通って，各 $𝑛$ で

𝐻 𝑛 𝑛 \leq 𝑅 𝑛 + 𝛿 𝑛, 𝛿 𝑛 \to 0

を得る．あとは $𝐻 𝑛 / 𝑛 \geq 𝐻 (X)$ を言えばよい．補題 3.2.4 より数列 $(𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖)) 𝑖$ は非増加であり，定理 3.2.6 よりその極限が $𝐻 (X)$ だから，各項は $𝐻 (X)$ 以上である．補題 3.2.3 より $𝐻 𝑛 / 𝑛$ はその相加平均だから，やはり $𝐻 (X)$ 以上である．よって $𝐻 (X) \leq 𝑅 𝑛 + 𝛿 𝑛$ となり，下極限をとれば主張を得る． $◼$

系 3.5.10 は，情報源符号化定理（定理 2.3.6）が i.i.d. の仮定なしに成り立つ，と言っている．置き換わったのは 1 文字のエントロピー $𝐻 (𝑋)$ がエントロピーレート $𝐻 (X)$ になったところだけで，圧縮の限界を決めているのが「1 文字あたりの不確かさ」であることは変わらない．

エルゴード性がどこで効くか. 逆定理 (2) の証明はエルゴード性を使っていない．定常でありさえすれば $𝐻 𝑛 / 𝑛 \geq 𝐻 (X)$ が言えるからである．エルゴード性が要るのは達成可能性 (1) のほう，つまり定理 3.5.2 を経由して典型集合を作るところである．例 3.4.2 がそこを壊す．最初のコインを固定すればその先は i.i.d. で，混合の確率のうち自分の側の項が支配するから，経験エントロピーは定理 2.1.4 のとおり分岐ごとの値に落ち着く．すなわち表なら $1$ ビット，裏なら $𝐻 𝑏 (0.1) \approx 0.47$ ビットである．ただ一つの値に収束するという定理 3.5.2 の結論が，ここでは成り立っていない．いっぽうエントロピーレートは，命題 3.5.9 の $𝔼 [ˆ 𝐻 𝑛] = 𝐻 𝑛 / 𝑛$ から二つの値の平均 $\approx 0.73$ ビットになる．したがって $0.73 < 𝑅 < 1$ にとった符号は，表の側の実現を覆いきれない．長さ $𝑛$ のブロックが $2 𝑛$ 通りあるのに，用意した符号語は $2 𝑅 𝑛$ 個しかないためである．誤り確率は $0$ に落ちず， $1 / 2$ 近くに残る．

形式化上の注記. 系 3.5.10 に対応する単独の宣言は形式化されていない．エルゴード的な定常情報源に対する典型集合とブロック情報源符号は，第2章の i.i.d. 版とは別に立てる必要があり，そこまでは形式化されていないためである．本文の証明が第2章の主張を「そのまま通る」と書いているのは紙の上での議論で，機械検証されているのは定理 3.5.2 までである．

第2章はエントロピーを，分布から計算する量・長い系列が見せる振る舞い・圧縮率の下限，という三つの顔で捉えた．本章はその三つがそのままエントロピーレートに引き継がれることを見たことになる．第6章では情報源ではなく通信路（信号を受け取って別の信号を返すもの）に目を移し，そこを通せる情報の量にも同じように限界があることを見る．

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