2.1 漸近等分配性

第1章はエントロピー $𝐻 (𝑋)$ を「平均驚き量」として導入した．平均である以上，それは1 回の観測について何かを言う量ではない．しかし情報源は 1 文字だけ出して終わるのではなく，次々と文字を送り出す． $𝑛$ 文字を受け取ったとき，実際に受け取った驚きを 1 文字あたりに均した値（分布から計算した平均ではなく，その回に実現した値）はどう振る舞うだろうか．

本節の答えは「 $𝑛$ を大きくすると実現値は $𝐻 (𝑋)$ に張り付く」である．これだけ聞くと大数の法則の言い換えにすぎないが，驚きの平均が張り付くということは，実際に現れる系列の確率がどれもほぼ同じ値になるということでもある．1 文字あたりの驚きが $𝐻 (𝑋)$ に近いというのは，対数を外せば系列の確率が $2 - 𝑛 𝐻 (𝑋)$ の近くにあるということだからで，両者は同じ事実の言い換えにすぎない．長さ $𝑛$ の系列は全部で $| X | 𝑛$ 個あるのに，分布が偏っていれば実際に現れるのはそのごく一部で，しかもその一部の中ではどれも同じくらい起こりやすい．「漸近的に等しく分配される」という本章の題はここから来ている．次節以降で見るように，この「ごく一部」を数え上げると約 $2 𝑛 𝐻$ 個であり， $𝑛 𝐻$ ビットあれば番号を振れる．データ圧縮の限界がエントロピーで決まるのは，この数え上げが理由である．

以下，情報源は 独立同分布（i.i.d.）とする．すなわち $𝑋 0, 𝑋 1, 𝑋 2, \dots$ は互いに独立で，どれも同じ分布 $𝑝$ に従うものとし，アルファベット $X$ は有限とする．長さ $𝑛$ のブロックを $𝑋 𝑛 : = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ と書き， $𝑛 \geq 1$ とする．ブロックの確率も同じ記号で $𝑝 (𝑥 0, \dots, 𝑥 𝑛 - 1)$ と書く．引数が 1 文字なら周辺分布， $𝑛$ 文字の並びならブロックの同時分布である．

本章では $l o g$ の底を 2 にとる． $2 𝑛 𝐻$ のように指数と対数の底をそろえておくと式が読みやすく，エントロピーの単位もビットで揃うためである．他の底をとりたければ， $𝐻$ の値と指数の底を同じ底で読み替えればよい（式の形は変わらない）．

道具を二つ借りる．一つめは大数の強法則で，形は「i.i.d. で期待値をもつ確率変数列の相加平均は，期待値に概収束する」，すなわち確率 1 の事象の上で各点収束するという事実である．当てる相手は，有限アルファベット上の i.i.d. な列から作った有界な確率変数の相加平均である．二つめは概収束は確率収束を含むという関係で，形は「概収束する確率変数の列は，同じ極限に確率収束もする」，すなわち任意の $𝜀 > 0$ について，極限から $𝜀$ 以上離れる確率が 0 に近づくということである．当てる相手は経験エントロピーの列である．直接借りるのは，一つめが本節の定理 2.1.4・2.4 節の定理 2.4.3・第3章の例 3.4.2・第5章の定理 5.5.1・第15章の定理 15.5.1 と系 15.5.5 の六つの証明，二つめが本節の定理 2.1.4 と 3.5 節の系 3.5.10 の二つの証明だけで，ほかの主張はすべてこれらを経由してのみ二つの道具に依存する．これらを認めれば，残りは第1章の道具だけで読める．

定義

定義 2.1.1（経験エントロピー）. i.i.d. 情報源 $𝑋 0, 𝑋 1, \dots$ （各 $𝑋 𝑖$ の分布は $𝑝$ ）と $𝑛 \geq 1$ に対し，長さ $𝑛$ の経験エントロピー を

ˆ 𝐻 𝑛 : = - 1 𝑛 l o g 𝑝 (𝑋 0, 𝑋 1, \dots, 𝑋 𝑛 - 1)

で定める．ここで $𝑝 (𝑥 0, \dots, 𝑥 𝑛 - 1)$ はブロック $𝑋 𝑛$ の確率である．

$ˆ 𝐻 𝑛$ は分布から決まる定数ではなく，観測のたびに値が変わる確率変数である．定義 1.1.1 のエントロピー $𝐻 (𝑋)$ が分布 $𝑝$ だけで決まる数であるのと対照的で， $ˆ 𝐻 𝑛$ は「今回たまたま出た系列がどれだけ珍しかったか」を 1 文字あたりに直した量になっている．

$ˆ 𝐻 𝑛$ はブロック全体の確率で定義されているが，i.i.d. なら独立性が積を作り，対数がその積を和に変えるので，1 文字ごとの驚きの相加平均にほどける．ブロックという扱いにくい対象が 1 文字ずつの和になるのが i.i.d. の効きどころで，大数の法則が使えるようになるのもそのためである．次の補題 2.1.3 でこのほどきを確かめる．

例 2.1.2（偏ったコイン）. $X = {0, 1}$ ， $𝑝 (1) = 0.9$ ， $𝑝 (0) = 0.1$ の情報源を考える．エントロピーは例 1.1.2 の二値エントロピーで $𝐻 (𝑋) = 𝐻 𝑏 (0.1) \approx 0.469$ ビットである．

$𝑛 = 10$ 回投げて $1$ が 9 回， $0$ が 1 回出たとすると

ˆ 𝐻 10 = - 110 l o g (0.9 9 \cdot 0.1) = - (0.9 l o g 0.9 + 0.1 l o g 0.1) = 𝐻 𝑏 (0.1),

ちょうど $𝐻 (𝑋)$ に一致する．一方 10 回とも $1$ が出たなら $ˆ 𝐻 10 = - l o g 0.9 \approx 0.152$ ビットで， $𝐻 (𝑋)$ の 3 分の 1 ほどしかない． $ˆ 𝐻 𝑛$ が観測ごとに揺れる量であることが，この二つの値の差に出ている．

例 2.1.2 で $ˆ 𝐻 10$ が $𝐻 (𝑋)$ に一致したのは偶然ではない．出た $1$ の割合がちょうど $0.9$ だったからで，一般に $1$ の割合が $𝑞$ なら $ˆ 𝐻 𝑛 = - 𝑞 l o g 0.9 - (1 - 𝑞) l o g 0.1$ になる．割合 $𝑞$ が真の確率 $0.9$ に近づけば $ˆ 𝐻 𝑛$ は $𝐻 (𝑋)$ に近づく．これが本節の定理の，この情報源における姿である．10 回とも $1$ が出るという事象は確率 $0.9 10 \approx 0.35$ でまだ珍しくないが， $𝑛 = 100$ なら $0.9 100 \approx 2.7 \times 10 - 5$ で，めったに起きない． $𝑛$ を大きくすると揺れが消えるとはそういうことである．

大数の法則にかけられる形にする

補題 2.1.3. i.i.d. 情報源に対し，経験エントロピーは 1 文字ごとの驚きの相加平均に等しい:

ˆ 𝐻 𝑛 = 1 𝑛 𝑛 - 1 \sum 𝑖 = 0 (- l o g 𝑝 (𝑋 𝑖)) .

またその各項の期待値は $𝔼 [- l o g 𝑝 (𝑋 𝑖)] = 𝐻 (𝑋)$ である．

証明. 独立性より，ブロックの確率は周辺分布の積 $𝑝 (𝑥 0, \dots, 𝑥 𝑛 - 1) = \prod 𝑖 < 𝑛 𝑝 (𝑥 𝑖)$ に等しい．対数は積を和に変えるので

ˆ 𝐻 𝑛 = - 1 𝑛 l o g \prod 𝑖 < 𝑛 𝑝 (𝑋 𝑖) = 1 𝑛 \sum 𝑖 < 𝑛 (- l o g 𝑝 (𝑋 𝑖)) .

どの $𝑋 𝑖$ も分布 $𝑝$ に従うので，期待値を定義どおり書き下すと

𝔼 [- l o g 𝑝 (𝑋 𝑖)] = \sum 𝑥 \in X 𝑝 (𝑥) (- l o g 𝑝 (𝑥)) = - \sum 𝑥 𝑝 (𝑥) l o g 𝑝 (𝑥) = 𝐻 (𝑋)

であり，これは定義 1.1.1 そのものである． $𝑝 (𝑥) = 0$ の項は両辺とも $0 l o g 0 = 0$ の約束により寄与しない． $◻$

補題 2.1.3 の後半は式の上ではエントロピーの定義を読み替えただけだが，本節の見取り図はこれで決まる． $ˆ 𝐻 𝑛$ は i.i.d. な量 $- l o g 𝑝 (𝑋 𝑖)$ の相加平均であり，その各項の期待値が $𝐻 (𝑋)$ である．相加平均が期待値に近づくというのが大数の法則だから， $ˆ 𝐻 𝑛$ は $𝐻 (𝑋)$ に近づく．第1章で $𝐻 (𝑋)$ を「驚きの平均」と呼んだのは定義に沿った説明だったが，ここではその平均が，実際に観測される驚きの平均として現れる．

主張と証明

定理 2.1.4（漸近等分配性）. i.i.d. 情報源に対し， $𝑛 \to \infty$ で

ˆ 𝐻 𝑛 = - 1 𝑛 l o g 𝑝 (𝑋 0, \dots, 𝑋 𝑛 - 1) ⟶ 𝐻 (𝑋)

が確率収束の意味で成り立つ．すなわち任意の $𝜀 > 0$ に対し $P r [∣ ˆ 𝐻 𝑛 - 𝐻 (𝑋) ∣ \geq 𝜀] \to 0$ ．さらに収束は概収束の意味でも成り立つ．すなわち確率 1 の事象の上で各点収束する．

証明. $𝑌 𝑖 : = - l o g 𝑝 (𝑋 𝑖)$ とおく． $𝑌 𝑖$ は $𝑋 𝑖$ だけの関数だから， $𝑋 0, 𝑋 1, \dots$ がi.i.d. であれば $𝑌 0, 𝑌 1, \dots$ も i.i.d. である．

$𝑌 𝑖$ が期待値をもつことを確かめる． $𝑋 𝑖$ が値 $𝑎$ をとる確率は $𝑝 (𝑎)$ なので， $𝑝 (𝑎) = 0$ の値を $𝑋 𝑖$ がとる確率は 0 である．よって $𝑌 𝑖$ は確率 1 で有限集合 ${- l o g 𝑝 (𝑎) : 𝑝 (𝑎) > 0}$ に値をとり，確率 1 で有界である．有界な確率変数は期待値をもち，補題 2.1.3 よりその値は $𝐻 (𝑋)$ である．

補題 2.1.3 より $ˆ 𝐻 𝑛 = 1 𝑛 \sum 𝑖 < 𝑛 𝑌 𝑖$ だから，i.i.d. で期待値をもつ列に大数の強法則を適用して，概収束 $ˆ 𝐻 𝑛 \to 𝐻 (𝑋)$ を得る．借りた二つめ，すなわち概収束は確率収束を含むという関係から，主張の前半もここから従う． $◼$

両端で確かめる. 極端な情報源では定理 2.1.4 は何も言っていないに等しい． $𝑋$ がある一点に確率 1 で集中していれば $𝐻 (𝑋) = 0$ （命題 1.1.4）で，出る系列はただ一つ，その確率は 1 だから $ˆ 𝐻 𝑛 = 0$ が常に成り立ち，揺れる余地がない． $X$ 上の一様分布なら，どの系列も確率 $| X | - 𝑛$ なので $ˆ 𝐻 𝑛 = l o g | X | = 𝐻 (𝑋)$ が，やはり常に成り立つ（例 1.1.3）．揺れが生じるのは分布が偏っていて，しかも一点に集中していない中間の場合だけであり，そこで初めて「 $𝑛$ を大きくすると揺れが消える」という主張に中身が出る．

どの系列が出るかは言わない. 定理 2.1.4 が述べているのは，実際に出た系列の確率が $2 - 𝑛 𝐻 (𝑋)$ の近くにあるということだけで，どの系列が出るかについては何も言わない．確率が近いというだけなら，たがいにまったく違う系列どうしでも成り立ちうる．次節では，この「確率が $2 - 𝑛 𝐻$ 近辺の系列」をひとまとめの集合として取り出し，その集合がどれくらい大きいかを数える．定理 2.1.4 は，その集合にブロックが入る確率が 1 に近づくことを保証する部分を担う．

形式化上の注記（本章共通）. 形式化は本章を通じて $l o g$ を自然対数にとり，指数評価を exp，レートをナットで述べている．本文が底を 2 に固定しているのと表層が違うだけで，底をそろえれば同じ主張である．i.i.d. 仮定は Mathlib に IsIID 述語が無いため，独立性（どの 2 つをとっても独立，という意味での 対独立）と同分布性 IdentDistrib の 2 本に分けて受ける．

形式化上の注記. 本文は経験エントロピーをブロックの確率 $- 1 𝑛 l o g 𝑝 (𝑋 𝑛)$ で定義し，補題 2.1.3 で1 文字ずつの和にほどいた．形式化はこの順序を逆にとり，1 文字ごとの logLikelihood の相加平均を定義に据えている．証明が使うのは相加平均の形だけなので，独立性の仮定を後段の必要な定理にだけ課せるという利点がある（次節の要素数上界がその恩恵を受ける）．裏返すと，形式化の定義を本文のブロック確率の形に戻すには補題 2.1.3 が要り，そこには相互独立が効いている．その積分解は形式化では次節の点ごとの確率評価の証明に埋め込まれていて，単独の宣言にはなっていない．概収束は Mathlib の大数の強法則strong_law_ae_real，確率収束はそこから tendstoInMeasure_of_tendsto_ae で導く．

形式化: 1 文字あたりの対数尤度 logLikelihood，その期待値integral_logLikelihood_zero（補題 2.1.3 の後半），概収束 aep_ae，確率収束 aep_inProbability (ソース)

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