11.2 型類の確率

前節は型類について二つを得た．中の点はどれも同じ確率をもち， $𝑄$ が全点で正ならその確率は $e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄)))$ であること（命題 11.1.4），そして要素数が $𝑒 𝑛 𝐻 (𝑃)$ の前後にあること（定理 11.1.8）である．型類全体の確率は，一点の確率に要素数を掛けたものだから，この二つを掛け合わせれば出る．掛けるとエントロピーの項は打ち消し合い，相対エントロピーだけが指数に残る．これが本節の主張で，次節以降の議論はここから出発する．

挟み込み

定理 11.2.1（型類の確率）. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とする． $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）とすると

(𝑛 + 1) - | X | 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄) \leq 𝑄 𝑛 (T 𝑛 (𝑃)) \leq 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. 命題 11.1.4 より， $T 𝑛 (𝑃)$ のどの点についても $𝑄 𝑛$ による確率は $e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄)))$ であり，点のとり方に依らない．したがって

𝑄 𝑛 (T 𝑛 (𝑃)) = ∣ T 𝑛 (𝑃) ∣ e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄)))

である．この要素数に定理 11.1.8 の挟み込みを当てる．指数関数の値は正だから，不等式の向きは変わらない．

上界について， $| T 𝑛 (𝑃) | \leq 𝑒 𝑛 𝐻 (𝑃)$ より

𝑄 𝑛 (T 𝑛 (𝑃)) \leq 𝑒 𝑛 𝐻 (𝑃) e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄))) = 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)

である．下界も同じで， $| T 𝑛 (𝑃) | \geq (𝑛 + 1) - | X | 𝑒 𝑛 𝐻 (𝑃)$ の両辺に $e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄)))$ を掛ければ $𝑄 𝑛 (T 𝑛 (𝑃)) \geq (𝑛 + 1) - | X | 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)$ を得る． $◼$

形式化: 上界 typeClassByCount_Qn_le (ソース)，下界 typeClassByCount_Qn_ge (ソース)

指数に残るのは相対エントロピーだけである．エントロピーの項は，要素数の $𝑒 𝑛 𝐻 (𝑃)$ と一点の確率の $𝑒 - 𝑛 𝐻 (𝑃)$ で打ち消し合った．読み方は素直で， $𝑄$ に従う情報源から型が $𝑃$ の系列が出る確率は， $𝑃$ が $𝑄$ からどれだけ隔たっているかだけで決まり，その隔たりが確率の落ちる速さになる，ということである．上下の隔たりは $(𝑛 + 1) | X |$ 倍あるが，これが指数の速さに効かないことは系 11.2.3 で確かめる．

1.6 節は相対エントロピーを「 $𝑞$ だと思い込んで符号化したために余計に払う符号長」として読んだ．定理 11.2.1 はもう一つの読み方を与える． $𝑄$ から見たとき，型 $𝑃$ の系列がどれだけ出にくいかである． $𝐷 (𝑃 ‖ 𝑄)$ が小さければ指数は $0$ に近く，確率は $𝑛$ が増えてもゆっくりしか落ちない．大きければ速く落ちる．どちらの読み方でも， $𝐷 (𝑃 ‖ 𝑄)$ が $0$ になるのは $𝑃 = 𝑄$ のときに限る（定理 1.6.1）という性質が土台にある．

型の列に沿った極限

型の列を追う前に，本章で繰り返し使う一つの収束を切り出しておく．挟み込みの上下の隔たり $(𝑛 + 1) | X |$ は，対数をとって $𝑛$ で割ると $| X | l o g (𝑛 + 1) / 𝑛$ になる．これが $0$ に行くというのが次の補題であり，多項式倍の差が $1 𝑛 l o g$ の水準で消えるというのは，本章のどこでもこの形で効く．証明で使うのは 1.1 節の対数不等式ひとつである．

補題 11.2.2.

l i m 𝑛 \to \infty l o g (𝑛 + 1) 𝑛 = 0

である．

証明. 補題 1.1.7 の対数不等式 $l o g 𝑡 \leq (𝑡 - 1) l o g 𝑒$ を，本章の底のもとで（ $l o g 𝑒 = 1$ である） $𝑡 : = \sqrt 𝑛 + 1$ に当てると $12 l o g (𝑛 + 1) \leq \sqrt 𝑛 + 1 - 1 \leq \sqrt 𝑛 + 1$ であり， $𝑛 \geq 1$ では $\sqrt 𝑛 + 1 \leq \sqrt 2 𝑛$ だから

0 \leq l o g (𝑛 + 1) 𝑛 \leq 2 \sqrt 𝑛 + 1 𝑛 \leq 2 \sqrt 2 \sqrt 𝑛

である．右端は $0$ に収束するから，両端に挟まれた真ん中も $0$ に収束する． $◻$

形式化: log_succ_div_tendsto_zero (ソース)

系 11.2.3. $X$ を空でない有限アルファベット， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とする．各 $𝑛 \geq 1$ について $𝑃 𝑛$ を長さ $𝑛$ の型（定義 11.1.1）とし， $X$ 上の分布 $𝑃$ がどの文字 $𝑎$ でも $𝑃 𝑛 (𝑎) \to 𝑃 (𝑎)$ （ $𝑛 \to \infty$ ）を満たすならば

1 𝑛 l o g 𝑄 𝑛 (T 𝑛 (𝑃 𝑛)) ⟶ - 𝐷 (𝑃 ‖ 𝑄)

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. 定理 11.2.1 を型 $𝑃 𝑛$ に当てる．下界が正だから $𝑄 𝑛 (T 𝑛 (𝑃 𝑛))$ も正で対数がとれ， $l o g$ は単調だから，対数をとって $𝑛$ で割ると

- 𝐷 (𝑃 𝑛 ‖ 𝑄) - | X | l o g (𝑛 + 1) 𝑛 \leq 1 𝑛 l o g 𝑄 𝑛 (T 𝑛 (𝑃 𝑛)) \leq - 𝐷 (𝑃 𝑛 ‖ 𝑄)

である．両端が $- 𝐷 (𝑃 ‖ 𝑄)$ に収束することを見れば，主張が従う．

左端の第 $2$ 項は，補題 11.2.2 と， $| X |$ が $𝑛$ に依らない有限の数であることから $0$ に収束する．

次に $𝐷 (𝑃 𝑛 ‖ 𝑄) \to 𝐷 (𝑃 ‖ 𝑄)$ を見る． $X$ 上の分布 $˜ 𝑃$ に対し

𝐷 (˜ 𝑃 ‖ 𝑄) = \sum 𝑎 ˜ 𝑃 (𝑎) l o g ˜ 𝑃 (𝑎) - \sum 𝑎 ˜ 𝑃 (𝑎) l o g 𝑄 (𝑎) = - \sum 𝑎 𝜑 (˜ 𝑃 (𝑎)) - \sum 𝑎 ˜ 𝑃 (𝑎) l o g 𝑄 (𝑎)

と書ける（ $𝜑 (𝑡) = - 𝑡 l o g 𝑡$ は 1.1 節の記号であり， $˜ 𝑃 (𝑎) = 0$ の項が両辺で $0$ になることは $𝑄 (𝑎) > 0$ と $0 l o g 0 = 0$ の約束による）．1.1 節で認めた $𝜑$ の $[0, \infty)$ 上の連続性から，どの文字でも $𝜑 (𝑃 𝑛 (𝑎)) \to 𝜑 (𝑃 (𝑎))$ である．また $𝑄$ は全点で正だから $l o g 𝑄 (𝑎)$ は有限な数で， $𝑃 𝑛 (𝑎) l o g 𝑄 (𝑎) \to 𝑃 (𝑎) l o g 𝑄 (𝑎)$ である．収束する数列を有限個足したものはそれぞれの極限の和に収束するから， $X$ が有限であることと合わせて $𝐷 (𝑃 𝑛 ‖ 𝑄) \to 𝐷 (𝑃 ‖ 𝑄)$ を得る． $◼$

系 11.2.3 が言っているのは，指数が型について連続である，ということである．長さ $𝑛$ の型がとる値は $0, 1 / 𝑛, \dots, 1$ に限られる（定義 11.1.1）ので，あらかじめ与えられた分布 $𝑃$ が長さ $𝑛$ の型であるとは限らない．そのときは $𝑃$ に収束する型の列をとればよく，指数はそれでも $- 𝐷 (𝑃 ‖ 𝑄)$ に行く．次節はまさにこの形で使う．

自分の型類は多項式ぶんしか小さくならない

系 11.2.4. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）， $𝑃 𝑛$ をその $𝑛$ 重の積分布とすると

𝑃 𝑛 (T 𝑛 (𝑃)) \geq (𝑛 + 1) - | X |

である．

証明. 系 11.1.5 より $𝑃 𝑛 (T 𝑛 (𝑃)) = | T 𝑛 (𝑃) | 𝑒 - 𝑛 𝐻 (𝑃)$ であり，定理 11.1.8 の下界より $| T 𝑛 (𝑃) | \geq (𝑛 + 1) - | X | 𝑒 𝑛 𝐻 (𝑃)$ である．二つを合わせると $𝑃 𝑛 (T 𝑛 (𝑃)) \geq (𝑛 + 1) - | X |$ を得る． $◼$

自分の型類に落ちる確率は， $𝑛$ の多項式の逆数までしか小さくならない．指数では落ちないということである．補題 11.1.7 によればこの型類が $𝑃 𝑛$ で測っていちばん重いのだから，いちばん重い型類の重さについての評価でもある． $𝑃$ が全点で正であれば，定理 11.2.1 で $𝑄$ に $𝑃$ 自身をとっても同じ下界が出る（相対エントロピーが $0$ になることは定理 1.6.1 の等号条件による）．系 11.2.4 はそれを，全点で正とは限らない型にまで広げた形である．

一様分布からの隔たり

本節から先の節では，公平なコインを基準の分布にとった例を繰り返し扱う．そこで現れる相対エントロピーは，二値エントロピー関数ひとつで書ける．引くたびに導き直さずに済むよう，先に補題として切り出しておく．

補題 11.2.5（二値分布の一様分布からの隔たり）. $X = {0, 1}$ とし， $𝑄$ を $𝑄 (0) = 𝑄 (1) = 1 / 2$ で定まる分布， $𝐻 𝑏$ を例 1.1.2 の二値エントロピー関数とする． $X$ 上のどの分布 $𝑃$ についても

𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (𝑃 (1)) = l o g 2 - 𝐻 𝑏 (𝑃 (0))

である（ $𝐷$ は 1.6 節の相対エントロピー）．

証明. $𝑄$ は $X$ 上の一様分布で $| X | = 2$ だから，命題 10.1.2 より $𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 (𝑃)$ である（ $𝐻$ は定義 1.1.1 のエントロピー）．例 1.1.2 の定め方から $𝐻 (𝑃) = 𝐻 𝑏 (𝑃 (1))$ であり，補題 9.3.1 の第 $1$ の主張より $𝐻 𝑏 (𝑃 (1)) = 𝐻 𝑏 (1 - 𝑃 (1)) = 𝐻 𝑏 (𝑃 (0))$ である． $◻$

形式化上の注記. 補題 11.2.5 に対応する単独の宣言は無い．一般のアルファベットについて $𝐷 (𝑃 ‖ 𝑈) = l o g | X | - 𝐻 (𝑃)$ を述べる klDiv_uniformOn_univ_toReal_eq (InformationTheory/Shannon/MaxEntropy/Basic.lean) が第 $1$ の等号の骨格を与えるが，エントロピーを二値エントロピー関数の形に書き直すところと，第 $2$ の等号にあたる対称性は，本書の形式化には無い．対称性のほうは Mathlib の Real.binEntropy_one_sub が無条件の機械検証済みの補題として与えている．

この形は，公平なコインからの隔たりが，エントロピーの目減りぶんとして測れることを言っている． $𝑃$ が公平なコインに近いほど $𝐻 𝑏$ は $l o g 2$ に近く，隔たりは $0$ に近い． $𝑃$ が一方の文字に寄るほど $𝐻 𝑏$ は小さくなり，そのぶん隔たりが大きくなる． $𝑃 (0)$ と $𝑃 (1)$ のどちらで書いてもよいのは，二値エントロピー関数が $1 / 2$ を軸に左右対称だからである．

数値で見る

例 11.2.6（偏ったコインを公平なコインで測る）. $X = {0, 1}$ とし， $𝑄$ を $𝑄 (0) = 𝑄 (1) = 1 / 2$ で定まる分布， $𝑃$ を $𝑃 (0) = 0.1$ ， $𝑃 (1) = 0.9$ で定まる分布とする． $𝑄 𝑛$ を $𝑄$ の $𝑛$ 重の積分布， $T 𝑛 (\cdot)$ を定義 11.1.1 のとおり， $𝐻 𝑏$ を例 1.1.2 の二値エントロピー関数とすると，次の三つが成り立つ．

$𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (0.1)$ であり，その値は約 $0.368$ ナットである．
$𝑛$ が $10$ の倍数ならば $𝑃$ は長さ $𝑛$ の型であり， $(𝑛 + 1) - 2 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄) \leq 𝑄 𝑛 (T 𝑛 (𝑃)) \leq 𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)$ が成り立つ．
$𝑛 = 100$ のとき $𝑄 100 (T 100 (𝑃)) = (10010) 2 - 100$ であり，その値は約 $1.37 \times 10 - 17$ である．このとき第 $2$ の挟み込みの上界は約 $1.04 \times 10 - 16$ ，下界は約 $1.02 \times 10 - 20$ である．

証明.

補題 11.2.5 を $𝑃$ に当てると $𝐷 (𝑃 ‖ 𝑄) = l o g 2 - 𝐻 𝑏 (𝑃 (0)) = l o g 2 - 𝐻 𝑏 (0.1)$ である．値は $𝐻 𝑏 (0.1) = - 0.1 l o g 0.1 - 0.9 l o g 0.9 = 0.3250 \dots$ ， $l o g 2 = 0.6931 \dots$ だから，差は $0.3680 \dots$ である．
$𝑛 𝑃 (0) = 𝑛 / 10$ ， $𝑛 𝑃 (1) = 9 𝑛 / 10$ は， $𝑛$ が $10$ の倍数なら非負整数であり，和は $𝑛$ である． $0$ を $𝑛 / 10$ 個並べたあと $1$ を $9 𝑛 / 10$ 個並べた系列の型は $𝑃$ だから， $𝑃$ は長さ $𝑛$ の型である． $𝑄$ は全点で正で $| X | = 2$ だから，定理 11.2.1 がそのまま第 $2$ の主張を与える．
$T 100 (𝑃)$ は $0$ をちょうど $10$ 個含む長さ $100$ の系列の全体だから，その要素数は， $100$ 個の位置から $0$ を置く $10$ 個を選ぶ選び方の数 $(10010)$ である． $𝑄$ は一様なので各点の確率は $2 - 100$ であり，掛け合わせて $𝑄 100 (T 100 (𝑃)) = (10010) 2 - 100$ を得る． $(10010) = 17310309456440$ と $2 - 100 = 7.888 \dots \times 10 - 31$ から，値は $1.365 \dots \times 10 - 17$ である．上界は $𝑒 - 100 𝐷 (𝑃 ‖ 𝑄) = 𝑒 - 36.806 \dots = 1.035 \dots \times 10 - 16$ ，下界はこれを $(100 + 1) 2 = 10201$ で割った $1.015 \dots \times 10 - 20$ である．

$◼$

この $𝑃$ は例 2.1.2 の偏ったコインと同じ分布である（あちらは $l o g$ の底を $2$ にとったので， $𝐻 𝑏 (0.1)$ の値が約 $0.469$ ビットと書かれている）．例 11.2.6 の第 $3$ の主張は，定理 11.2.1 の挟み込みが実際どれくらいの粗さかを見せている．真の値は上界より $1$ 桁ほど小さく，下界より $3$ 桁ほど大きい．上下の隔たりは $4$ 桁あるが， $1 𝑛 l o g$ をとれば $l o g 10201 100 = 0.092 \dots$ の差でしかない．指数の速さだけを見るなら，公平なコインを $100$ 回投げて $1$ がちょうど $90$ 回出る確率は $𝑒 - 100 𝐷 (𝑃 ‖ 𝑄)$ のあたりにある．

形式化上の注記. 例 11.2.6 の数値に対応する宣言は無い．形式化には，具体的な分布を入れて相対エントロピーや型類の確率を計算した実例が置かれていない．

定理 11.2.1 が扱ったのは一つの型類である．次節は型の集合を指定し，経験分布がその集合に落ちる確率を問う．型の個数が多項式でしかないこと（命題 11.1.3）と本節の挟み込みが，そこで効く．集合全体の確率の指数を，その集合の中の一つの分布だけで書けるか，というのが次節の問いであり，答えを与えるのが Sanov の定理である．

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