3.1 定常情報源

第2章の情報源は i.i.d. だった．つまり次に何が来るかは，それまでに何が出たかと無関係で，1 文字あたりの不確かさは最初から最後まで $𝐻 (𝑋)$ のままである．しかし現実の情報源はそうではない．英文では q のあとにほとんど u しか来ないし，日本語で「情報」と読んだあとに「量」が続く確率は，文章全体での「量」の出現率よりずっと高い．前の文字を知っていると次の文字が当てやすくなる．その効き目を測る道具は第1章にすでにある．条件付けの単調性（定理 1.2.4）が $𝐻 (𝑋 1 ∣ 𝑋 0) \leq 𝐻 (𝑋 1)$ を与えていた．

記憶のある情報源なら「1 文字あたりの不確かさ」は $𝐻 (𝑋 0)$ より小さいはずで，第2章の圧縮限界も下がるはずである．だがその「1 文字あたり」を何と定義すればよいのか． $𝐻 (𝑋 𝑖)$ は $𝑖$ ごとに違うかもしれず， $𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖 - 1)$ も $𝐻 (𝑋 𝑖 ∣ 𝑋 𝑖 - 1, 𝑋 𝑖 - 2)$ も候補になる．候補を一つに絞るには，まず情報源の側に「時間が経っても性質が変わらない」という仮定を置かねばならない．それが本節の定常性である．本章は，記憶のある情報源について「1 文字あたりの不確かさ」を定め，第2章の結果がどこまでそのまま成り立つかを調べる．3.2 節でその量（エントロピーレート）を定義し，3.3 節でマルコフ情報源について計算し，3.4 節と 3.5 節で，長い列の確率がそのレートで決まるという第2章 2.1 節の結果を，記憶のある情報源のうち定常でエルゴード的なもの（3.4 節で定める）へ広げる．

以下，アルファベット $X$ は有限とし，長さ $𝑛$ のブロックを $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ と書く（第2章の記法をそのまま引き継ぐ）．本章では $l o g$ の底を 2 にとる．第2章と同じく $2 𝑛 𝐻$ の形の量を扱うので，指数と対数の底をそろえておくと式が読みやすい．

定義

定義 3.1.1（定常情報源）. $X$ に値をとる確率変数の列 $𝑋 0, 𝑋 1, 𝑋 2, \dots$ が定常であるとは，任意の $𝑛 \geq 1$ ，任意の $ℓ \geq 0$ ，任意の $𝑥 0, \dots, 𝑥 𝑛 - 1 \in X$ に対して

P r [𝑋 0 = 𝑥 0, \dots, 𝑋 𝑛 - 1 = 𝑥 𝑛 - 1] = P r [𝑋 ℓ = 𝑥 0, \dots, 𝑋 ℓ + 𝑛 - 1 = 𝑥 𝑛 - 1]

が成り立つことをいう．定常な列を 定常情報源 と呼ぶ．

定義が言っているのは，時計の針をどこに合わせても情報源が同じに見える，ということである．長さ $𝑛$ の窓を系列の上で滑らせても，窓から見える並びの分布は動かない．個々の文字が独立である必要はまったくなく， $𝑋 0$ と $𝑋 1$ がどれだけ強く絡んでいてもよい．禁じているのは絡み方が時刻によって変わることだけである．

この仮定がなければ「1 文字あたり」を語る意味がない．たとえば $𝑋 0$ だけが一様分布で $𝑋 1$ 以降がすべて定数，という列を考えると， $𝐻 (𝑋 𝑖)$ は $𝑖 = 0$ とそれ以外で違う値をとる．どの $𝑖$ の値を「1 文字あたりの不確かさ」と呼ぶべきかは決められない．定常性は，この問いを「どれでも同じ」にすることで消してしまう仮定である．

形式化: StationaryProcess，時刻 $𝑖$ の文字 obs，ブロック blockRV (ソース)

注記

形式化は定義 3.1.1 の等式を直接書き下さず，測度保存力学系として与えている．確率空間 $(Ω, 𝜈)$ の上に， $𝜈$ を保つ写像 $𝑇$ （シフト）と， $X$ に値をとる単一の観測 $𝑋$ を置き，時刻 $𝑖$ の文字を $𝑋 𝑖 : = 𝑋 \circ 𝑇 𝑖$ と定める． $𝑇$ が $𝜈$ を保つことが，そのまま定義 3.1.1 の分布のシフト不変性にあたる．この $𝜈$ は $Ω$ 上の測度で，以下でマルコフ情報源の初期分布に使う $𝜇$ とは別のものである．

本文の ${𝑋 𝑖}$ が「別々の確率変数の列」に見えるのに対し，こちらでは確率変数はただ一つで，動くのは点のほうだという違いがある．この形をとると 3.4 節の Birkhoff の定理がそのまま使える．あちらは軌道 $𝜔, 𝑇 𝜔, 𝑇 2 𝜔, \dots$ に沿った平均を扱う定理だからである．3.4 節のエルゴード性も同じ流儀で，情報源そのものではなく力学系 $(Ω, 𝑇, 𝜈)$ に課される． $Ω$ を系列の空間， $𝑇$ をシフトにとる標準的な実現では，定義 3.4.1 と一致する．

定義 3.1.1 の等式そのものは，この形から導かれる定理として shiftedMarginal_eq_of_shift (InformationTheory/Probability/TwoSidedExtension/Core.lean) にある．

例 3.1.2（i.i.d. 情報源）. 第2章の i.i.d. 情報源は定常である．実際，独立性と同分布性より両辺とも $\prod 𝑛 - 1 𝑖 = 0 𝑝 (𝑥 𝑖)$ に等しい． $ℓ$ がどこであっても，掛け合わせる周辺分布は同じ $𝑝$ だからである．

記憶のある情報源——マルコフ情報源

定常性は時間による変化を禁じただけで，記憶の有無については何も言っていない．記憶のあるもっとも単純な情報源は，次の 1 文字が直前の 1 文字だけで決まるものである．

定義 3.1.3（マルコフ情報源）. 遷移確率とは， $X \times X$ 上の非負関数 $𝑃$ であって，各 $𝑎 \in X$ について $\sum 𝑏 𝑃 (𝑎, 𝑏) = 1$ を満たすもののことをいう． $X$ 上の分布 $𝜇$ と遷移確率 $𝑃$ に対し，任意の $𝑛 \geq 1$ と $𝑥 0, \dots, 𝑥 𝑛 - 1 \in X$ で

P r [𝑋 0 = 𝑥 0, \dots, 𝑋 𝑛 - 1 = 𝑥 𝑛 - 1] = 𝜇 (𝑥 0) 𝑛 - 1 \prod 𝑖 = 1 𝑃 (𝑥 𝑖 - 1, 𝑥 𝑖)

を満たす情報源を，初期分布 $𝜇$ ・遷移確率 $𝑃$ の マルコフ情報源 という． $𝜇$ が

\sum 𝑎 𝜇 (𝑎) 𝑃 (𝑎, 𝑏) = 𝜇 (𝑏) (𝑏 \in X)

を満たすとき， $𝜇$ を $𝑃$ の 定常分布 という．

第1章のマルコフ連鎖との関係. 定義 1.8.3 で「マルコフ連鎖」と呼んだのは三つの確率変数 $𝑋 \to 𝑍 \to 𝑌$ の条件付き独立のことで，遷移確率も時間も出てこなかった．ここで導入したのは時間発展する列のほうで，1.8 節で予告した意味である．二つは無関係ではない．定義 3.1.3の情報源では，任意の $𝑖 \geq 1$ について $𝑋 𝑖 - 1 \to 𝑋 𝑖 \to 𝑋 𝑖 + 1$ が定義 1.8.3 の意味でマルコフ連鎖をなす．直前の文字を知ってしまえば，それより前の文字は次の文字について何も語らないからである．同じ語が二つの意味をもつのは，この一致のためである．

命題 3.1.4. 定義 3.1.3 のマルコフ情報源が定常であるための必要十分条件は，初期分布 $𝜇$ が遷移確率 $𝑃$ の定常分布であることである．

証明. まず $𝑋 ℓ$ の分布がすべての $ℓ$ で $𝜇$ に等しいことを， $ℓ$ についての帰納法で示す． $ℓ = 0$ は仮定である． $𝑋 ℓ$ の分布が $𝜇$ なら，定義 3.1.3 の分解を $𝑛 = ℓ + 2$ に使って $𝑥 0, \dots, 𝑥 ℓ - 1$ を和で消すと

P r [𝑋 ℓ + 1 = 𝑏] = \sum 𝑎 P r [𝑋 ℓ = 𝑎] 𝑃 (𝑎, 𝑏) = \sum 𝑎 𝜇 (𝑎) 𝑃 (𝑎, 𝑏) = 𝜇 (𝑏)

であり，最後の等号が定常分布の条件である．

次に定義 3.1.1 の等式を見る．先頭の $ℓ$ 文字は，衝突を避けるため $𝑦 0, \dots, 𝑦 ℓ - 1$ と書く．定義 3.1.3 の分解でこれらを和で消すと，残るのは $𝑋 ℓ$ の分布と $ℓ$ 以降の遷移確率だけである：

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

前段より $P r [𝑋 ℓ = 𝑥 0] = 𝜇 (𝑥 0)$ だから，右辺は $ℓ$ に依らない． $ℓ = 0$ の場合と比べれば定義 3.1.1 の等式を得る．

逆に情報源が定常だとする．定義 3.1.1 を $𝑛 = 1$ ， $ℓ = 1$ に使うと $𝑋 1$ の分布は $𝑋 0$ のそれ，すなわち $𝜇$ に等しい．いっぽう定義 3.1.3 の分解を $𝑛 = 2$ に使って $𝑥 0$ を和で消すと $P r [𝑋 1 = 𝑏] = \sum 𝑎 𝜇 (𝑎) 𝑃 (𝑎, 𝑏)$ である．二つを比べれば $\sum 𝑎 𝜇 (𝑎) 𝑃 (𝑎, 𝑏) = 𝜇 (𝑏)$ ，すなわち $𝜇$ は $𝑃$ の定常分布である． $◼$

命題 3.1.4 は，マルコフ情報源を定常にする初期分布の選び方は，定常分布であるというただ一つの条件に尽きる，と言っている．定常分布が存在するかどうかは別の問題で，本書では扱わない．以下でマルコフ情報源を持ち出すときは，定常分布が与えられているものとする．

例 3.1.5（二状態マルコフ情報源）. $X = {0, 1}$ ， $𝛼, 𝛽 \in (0, 1)$ とし，遷移確率を

𝑃 (0, 1) = 𝛼, 𝑃 (0, 0) = 1 - 𝛼, 𝑃 (1, 0) = 𝛽, 𝑃 (1, 1) = 1 - 𝛽

で定める．状態 $0$ からは確率 $𝛼$ で移り，状態 $1$ からは確率 $𝛽$ で戻る，という情報源である（図 3.1.1）．定常分布は

𝜇 (0) = 𝛽 𝛼 + 𝛽, 𝜇 (1) = 𝛼 𝛼 + 𝛽

である．実際

𝜇 (0) (1 - 𝛼) + 𝜇 (1) 𝛽 = 𝛽 (1 - 𝛼) + 𝛼 𝛽 𝛼 + 𝛽 = 𝛽 𝛼 + 𝛽 = 𝜇 (0)

であり，もう一方の等式は全体が 1 であることから従う．

滞在時間で読む. 定常分布の比 $𝜇 (0) : 𝜇 (1) = 𝛽 : 𝛼$ は，状態を出ていく確率の逆比である．出ていきにくい状態ほど長く滞在するので，その分だけ確率が集まる．

図 3.1.1. 例 3.1.5 の二状態マルコフ情報源の遷移．矢印に添えた数が，その向きに移る確率である．

情報理論入門（Lean による形式証明つき）・GitHub