11.1 型と型類

公平なコインを $𝑛$ 回投げて，出た $1$ の割合がちょうど $0.9$ になる確率は， $𝑛$ が増えるとどれだけ速く落ちるだろうか．この落ちる速さを指数で書き下すことが本章の主題であり，その指数には相対エントロピーが現れる．手がかりは第2章にある．第2章は長さ $𝑛$ の系列を，確率という一つの数だけで分類した．定義 2.2.1 の典型集合がそれで，そこに入る確率が $1$ に近づくこと（定理 2.2.3）と，要素数がおよそ $2 𝑛 𝐻$ であること（定理 2.2.5）の二つから，圧縮の限界が出た．ところがこの分類は粗く，まったく違う構成の系列どうしが同じ集合に入りうる（例 2.4.2）．2.4 節はその粗さを埋めるために，各文字の出現回数を直接見る強典型性へ移り，そこで系列 $𝑥$ の型（経験分布）を定義 2.4.1 で置いた．本章はこの型による分類を最後まで押し進める．

型で分類すると，二つの勘定が立つ．一つは，長さ $𝑛$ の系列を型で類別したときの類の個数であり，これは $𝑛$ の多項式で抑えられる．もう一つは，一つの類に入る系列の個数であり，こちらは指数で増えて，その指数は類の型のエントロピーになる．本節はこの二つを示す．類の個数が多項式でしかないことは，あとで有限個の項の和を最大の項一つで置き換えるときに効く．というのも，多項式倍の差は $1 𝑛 l o g$ をとると消えるからである．この道具立てを型の方法と呼ぶ．めったに起きない事象の確率が $𝑛$ とともにどれだけ速く落ちるか（大偏差），二つの分布のどちらが真かを当てる問題（仮説検定）で誤りがどれだけ速く落ちるか，本章が問うのはこの二つである．

本章では $l o g$ の底を自然対数にとり，エントロピーと相対エントロピーの単位をナットで測る．型類の要素数や確率が $𝑒 𝑛 𝐻 (𝑃)$ ， $𝑒 - 𝑛 𝐷 (𝑃 ‖ 𝑄)$ の形で書けるところが本章の眼目なので，指数と対数の底がそろっていると式が読みやすい．第2章が底を $2$ にとって $2 𝑛 𝐻$ と書いたのに対し，単位の名前が変わるだけである．

以下，アルファベット $X$ 上の長さ $𝑛 \geq 1$ の系列を $𝑥 = (𝑥 0, \dots, 𝑥 𝑛 - 1) \in X 𝑛$ と書く． $X$ 上の分布 $𝑃$ に対し，各成分が独立に $𝑃$ に従う長さ $𝑛$ のブロックの分布を $𝑃 𝑛$ と書く．すなわち $𝑃 𝑛 ({𝑥}) : = \prod 𝑛 - 1 𝑖 = 0 𝑃 (𝑥 𝑖)$ とし，部分集合 $𝐴 \subseteq X 𝑛$ については $𝑃 𝑛 (𝐴) : = \sum 𝑥 \in 𝐴 𝑃 𝑛 ({𝑥})$ とする（第6章が通信路の $𝑛$ 回の使用を $𝑊 𝑛$ と書いたのと同じ，肩に長さを乗せる書き方である）．また本章では，最適化して選んだものに星印を付け，分布には $⋆$ を，値には $*$ を使い分ける．対数が狭義単調増加であること（補題 8.2.5）は，以下ことわりなく使う．

定義

定義 11.1.1（型と型類）. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とする．系列 $𝑥 \in X 𝑛$ に含まれる文字 $𝑎$ の個数を $𝑁 (𝑎 ∣ 𝑥)$ （定義 2.4.1）と書き， $𝑥$ の型を

ˆ 𝑃 𝑥 (𝑎) : = 𝑁 (𝑎 ∣ 𝑥) 𝑛 (𝑎 \in X)

で定める． $X$ 上の分布 $𝑃$ が 長さ $𝑛$ の型 であるとは， $ˆ 𝑃 𝑥 = 𝑃$ となる $𝑥 \in X 𝑛$ が存在することをいう．長さ $𝑛$ の型 $𝑃$ に対し，その型類を

T 𝑛 (𝑃) : = {𝑥 \in X 𝑛 : ˆ 𝑃 𝑥 = 𝑃}

で定める．

$ˆ 𝑃 𝑥$ は，系列 $𝑥$ を一度ばらばらにして，どの文字が何回出たかだけを残したものである．順序の情報は捨てられているので， $𝑥$ の並べ替えはすべて同じ型を与える．値は非負で， $\sum 𝑎 𝑁 (𝑎 ∣ 𝑥) = 𝑛$ だから総和は $1$ であり， $ˆ 𝑃 𝑥$ は確かに $X$ 上の分布である．定義 2.4.1 が名前だけ与えていたこの分布に，本章は記号を与えたことになる．長さ $𝑛$ の型がとる値は $0, 1 / 𝑛, 2 / 𝑛, \dots, 1$ に限られる．すなわち $𝑛$ を固定すると，分布のうちごく一部だけが型として現れる．

型類 $T 𝑛 (𝑃)$ は，型がちょうど $𝑃$ である長さ $𝑛$ の系列の全体である．どの $𝑥$ もただ一つの型をもつので，長さ $𝑛$ の型すべての型類は $X 𝑛$ を重なりなく覆う．また $ˆ 𝑃 𝑥 = 𝑃$ は「各文字 $𝑎$ について $𝑁 (𝑎 ∣ 𝑥) = 𝑛 𝑃 (𝑎)$ 」と同じことだから，型類は文字ごとの個数を指定して切り出した集合でもある．とくに $𝑃$ が長さ $𝑛$ の型なら $𝑛 𝑃 (𝑎)$ はどの文字でも非負整数である．

形式化: 文字の個数 typeCount (ソース)，型類 typeClassByCount (ソース)

例 11.1.2（長さ $3$ の二値系列）. $X = {0, 1}$ ， $𝑛 = 3$ とし， $ˆ 𝑃 𝑥$ と $T 3 (\cdot)$ を定義 11.1.1 のとおりとする．分布を $(𝑃 (0), 𝑃 (1))$ の形で書くと，長さ $3$ の型はちょうど

(1, 0), (23, 13), (13, 23), (0, 1)

の $4$ 個である．系列 $(𝑥 0, 𝑥 1, 𝑥 2)$ を $𝑥 0 𝑥 1 𝑥 2$ と並べて書くと，型類はこの順に

T 3 (1, 0) = {000}, T 3 (23, 13) = {001, 010, 100},

T 3 (13, 23) = {011, 101, 110}, T 3 (0, 1) = {111}

であり，要素数は $1, 3, 3, 1$ である．

証明. 長さ $3$ の系列 $𝑥$ について $𝑁 (1 ∣ 𝑥)$ は $0, 1, 2, 3$ のいずれかであり， $𝑁 (0 ∣ 𝑥) = 3 - 𝑁 (1 ∣ 𝑥)$ だから，型 $ˆ 𝑃 𝑥$ は $𝑁 (1 ∣ 𝑥)$ だけで決まる． $𝑁 (1 ∣ 𝑥) = 𝑗$ に対応する型は， $𝑗 = 0, 1, 2, 3$ の順に上の $4$ 個である．上の並びは $X 3$ の $8$ 本を $𝑁 (1 ∣ 𝑥)$ の値で分けたものであり，どの型類も空でないから， $4$ 個はすべて長さ $3$ の型であって，型はちょうど $4$ 個である．要素数は並びを数えて順に $1, 3, 3, 1$ である． $◼$

型が $4$ 個なのに対し，系列は $23 = 8$ 本ある．一般のアルファベットと一般の $𝑛$ で型がいくつあるかを，次に数える．

型は多項式個しかない

命題 11.1.3. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とする．長さ $𝑛$ の型（定義 11.1.1）の個数は $(𝑛 + 1) | X |$ 以下である．

証明. $𝑃$ を長さ $𝑛$ の型とすると， $ˆ 𝑃 𝑥 = 𝑃$ となる $𝑥 \in X 𝑛$ があり，各文字 $𝑎$ について $𝑃 (𝑎) = 𝑁 (𝑎 ∣ 𝑥) / 𝑛$ である．したがって $𝑃$ は，個数の組 $(𝑁 (𝑎 ∣ 𝑥)) 𝑎 \in X$ を $𝑛$ で割ったものとして書ける．個数 $𝑁 (𝑎 ∣ 𝑥)$ は $0$ 以上 $𝑛$ 以下の整数だから，文字ごとに $𝑛 + 1$ 通りの値しかとれず，組は全部で $(𝑛 + 1) | X |$ 通り以下である．異なる型は異なる組を与えるので，型の個数もこれ以下である． $◼$

形式化: numTypes_le (ソース)

この数え方は粗い．個数の組の総和が $𝑛$ でなければならないという条件を使っておらず，型にならない組まで数えている．それでも以降の評価に入るのは $𝑛$ の多項式なので， $1 𝑛 l o g$ をとる水準では消える．系列のほうは $X 𝑛$ の要素数 $| X | 𝑛$ だけあり， $𝑛$ とともに指数で増える．本節の残りは，一つの型類がどれだけ大きいかを数える．

型類の中では確率が一定である

型が分かると，その系列の確率まで決まってしまう．長さ $𝑛$ のブロックの確率が文字ごとの確率の積であり，同じ文字については何回出たかだけが効くからである．次の命題はその値を書き下したものである．

命題 11.1.4. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑄$ を $X$ 上の全点で正の分布， $𝑄 𝑛$ をその $𝑛$ 重の積分布とする． $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）， $𝑥 \in T 𝑛 (𝑃)$ とすると

𝑄 𝑛 ({𝑥}) = e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄)))

である．ここで $𝐻$ は定義 1.1.1 のエントロピー， $𝐷$ は 1.6 節の相対エントロピーである．

証明. $𝑄 𝑛 ({𝑥}) = \prod 𝑛 - 1 𝑖 = 0 𝑄 (𝑥 𝑖)$ の積を，同じ文字ごとにまとめる．文字 $𝑎$ は $𝑥$ にちょうど $𝑁 (𝑎 ∣ 𝑥)$ 回現れ， $𝑥 \in T 𝑛 (𝑃)$ より $𝑁 (𝑎 ∣ 𝑥) = 𝑛 𝑃 (𝑎)$ だから

𝑄 𝑛 ({𝑥}) = \prod 𝑎 \in X 𝑄 (𝑎) 𝑁 (𝑎 ∣ 𝑥) = \prod 𝑎 \in X 𝑄 (𝑎) 𝑛 𝑃 (𝑎)

である． $𝑄$ は全点で正だからどの因子も正で，対数をとると

l o g 𝑄 𝑛 ({𝑥}) = 𝑛 \sum 𝑎 \in X 𝑃 (𝑎) l o g 𝑄 (𝑎)

になる（ $𝑃 (𝑎) = 0$ の文字では因子が $𝑄 (𝑎) 0 = 1$ であり，右辺の項も $0$ である）．

右辺の和を $𝑃$ 自身の対数を経由して書き直す． $𝑃 (𝑎) > 0$ の文字では

𝑃 (𝑎) l o g 𝑄 (𝑎) = 𝑃 (𝑎) l o g 𝑃 (𝑎) - 𝑃 (𝑎) l o g 𝑃 (𝑎) 𝑄 (𝑎)

であり， $𝑃 (𝑎) = 0$ の文字では， $𝑄 (𝑎) > 0$ と $0 l o g 0 = 0$ の約束（定義 1.1.1）により三つの項がすべて $0$ である． $𝑎$ について足すと，第 $1$ 項の和は $- 𝐻 (𝑃)$ ，第 $2$ 項の和は $𝐷 (𝑃 ‖ 𝑄)$ だから

l o g 𝑄 𝑛 ({𝑥}) = - 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑄))

となる．両辺の指数をとれば主張を得る． $◼$

右辺に $𝑥$ が現れないことが，この命題の言っていることのすべてである．型類の中の点はどれも同じ確率をもち，しかもその確率は，型のエントロピーと，型が $𝑄$ からどれだけ隔たっているかの二つだけで決まる．第2章の経験エントロピーは $- 1 𝑛 l o g 𝑝 (𝑥)$ という一つの数だったが，命題 11.1.4 の指数は $𝐻 (𝑃)$ と $𝐷 (𝑃 ‖ 𝑄)$ の二つに分かれている．この分かれ方を定義 2.1.1 の言葉に戻したものが系 11.1.9 である．

形式化上の注記. 命題 11.1.4 に対応する単独の宣言は無い．typeClassByCount_prod_eq (InformationTheory/Shannon/Sanov/LDP.lean) が同じ等式を与えているが，第 $1$ 因子が $\prod 𝑎 𝑃 (𝑎) 𝑛 𝑃 (𝑎)$ の形で残っている．これを $𝑒 - 𝑛 𝐻 (𝑃)$ に書き換えるのが prod_div_pow_eq_prod_pow_div_npow_of_sum (InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean) と pow_div_prod_pow_eq_exp_n_entropyByCount (InformationTheory/Shannon/TypeClassLowerBound.lean) であり，命題 11.1.4 はこの三つの合成として得られる．

系 11.1.5. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）， $𝑃 𝑛$ をその $𝑛$ 重の積分布とする． $𝑥 \in T 𝑛 (𝑃)$ とすると $𝑃 𝑛 ({𝑥}) = 𝑒 - 𝑛 𝐻 (𝑃)$ である（ $𝐻$ は定義 1.1.1 のエントロピー）．とくに $T 𝑛 (𝑃)$ の点はどれも同じ確率をもつ．

証明. $𝑃 𝑛 ({𝑥}) = \prod 𝑛 - 1 𝑖 = 0 𝑃 (𝑥 𝑖)$ を同じ文字ごとにまとめると， $𝑥 \in T 𝑛 (𝑃)$ より $𝑁 (𝑎 ∣ 𝑥) = 𝑛 𝑃 (𝑎)$ だから $\prod 𝑎 𝑃 (𝑎) 𝑛 𝑃 (𝑎)$ である． $𝑃 (𝑎) = 0$ の文字では $𝑛 𝑃 (𝑎) = 0$ なので因子は $1$ であり，積は $𝑃 (𝑎) > 0$ の文字だけをわたる．その対数は $𝑛 \sum 𝑎 : 𝑃 (𝑎) > 0 𝑃 (𝑎) l o g 𝑃 (𝑎)$ であり， $0 l o g 0 = 0$ の約束（定義 1.1.1）のもとでこれは $- 𝑛 𝐻 (𝑃)$ に等しい．両辺の指数をとれば等式を得る．右辺は $𝑥$ に依らないから，後半も従う． $◼$

形式化上の注記. 系 11.1.5 に対応する単独の宣言も無い． $𝑃$ が全点で正であれば，命題 11.1.4 と同じ三つの宣言に $𝑄$ として $𝑃$ 自身をとった合成で得られる（相対エントロピーの項が消える）．

型類の要素数は多項係数である

型類は文字ごとの個数を指定して切り出した集合だった（定義 11.1.1）．したがってその要素数は，位置を文字ごとに割り振る割り振り方の数であり，組合せの数として書き下せる．

命題 11.1.6. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）とすると

∣ T 𝑛 (𝑃) ∣ = 𝑛! \prod 𝑎 \in X (𝑛 𝑃 (𝑎))!

である．

証明. $𝑃$ は長さ $𝑛$ の型だから，どの文字でも $𝑛 𝑃 (𝑎)$ は非負整数であり，その総和は $𝑛$ である． $T 𝑛 (𝑃)$ の系列は，位置の全体 ${0, 1, \dots, 𝑛 - 1}$ を，各文字 $𝑎$ に大きさ $𝑛 𝑃 (𝑎)$ の集合を割り当てて重なりなく分ける分け方と $1$ 対 $1$ に対応する（割り当てた位置にその文字を書けばよい）． $X$ の文字に順番を付け，先頭の文字から順に，まだ使っていない位置の中から必要な個数を選んでいくと，選び方の総数は二項係数の積になり，約分すると主張の右辺になる． $◼$

形式化上の注記. 命題 11.1.6 に対応する単独の宣言は無い．形式化は InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean の中でこの等式を両向きの不等式として証明しているが，どちらもファイルの外に公開されていない補助補題なので名前で指すことができない．

右辺の分母は，同じ文字どうしの並べ替えを打ち消す因子である．例 11.1.2 で数えた $1, 3, 3, 1$ は，この式の $X = {0, 1}$ ， $𝑛 = 3$ の場合であり，たとえば型 $(23, 13)$ では $3! / (2! 1!) = 3$ になる．要素数がこの形で書けると，二つの型類の重さを比べるのは階乗の比を比べることになる．

いちばん重いのは自分の型類

命題 11.1.4 は一点の確率を与えた．型類全体の確率は，これに要素数を掛けたものである．要素数の指数評価に移る前に， $𝑃 𝑛$ で測ったときどの型類がいちばん重いかを見ておく．型類は $X 𝑛$ を重なりなく覆い，その個数は多項式で抑えられる（命題 11.1.3）から，全体の確率 $1$ のうち多項式の逆数ぶんは，いちばん重い型類が担っている．どれがいちばん重いかをここで決めておけば，系 11.1.5 で確率を要素数に読み替えて定理 11.1.8 の下界が出る．

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

𝑃 𝑛 (T 𝑛 (𝑃')) \leq 𝑃 𝑛 (T 𝑛 (𝑃))

である．

証明. まず型類全体の確率を書き下す．長さ $𝑛$ の型 $˜ 𝑃$ をとると， $𝑥 \in T 𝑛 (˜ 𝑃)$ なら $𝑃 𝑛 ({𝑥}) = \prod 𝑖 < 𝑛 𝑃 (𝑥 𝑖) = \prod 𝑎 𝑃 (𝑎) 𝑛 ˜ 𝑃 (𝑎)$ であり，これは $𝑥$ に依らない．よって型類全体の確率は要素数にこの値を掛けたものであり，命題 11.1.6 より

𝑃 𝑛 (T 𝑛 (˜ 𝑃)) = 𝑛! \prod 𝑎 (𝑛 ˜ 𝑃 (𝑎))! \prod 𝑎 𝑃 (𝑎) 𝑛 ˜ 𝑃 (𝑎)

である．この式を $˜ 𝑃 : = 𝑃'$ と $˜ 𝑃 : = 𝑃$ について比べる．

ある文字 $𝑎$ で $𝑃 (𝑎) = 0$ かつ $𝑃' (𝑎) > 0$ である場合を先に片づける．このとき $𝑃 𝑛 (T 𝑛 (𝑃'))$ の式は因子 $𝑃 (𝑎) 𝑛 𝑃' (𝑎) = 0$ をもつので値は $0$ であり， $𝑃 𝑛 (T 𝑛 (𝑃))$ は確率だから非負で，主張が成り立つ．

以下，どの文字でも $𝑃' (𝑎) > 0$ ならば $𝑃 (𝑎) > 0$ である場合を見る．このとき $𝑃 (𝑎) = 0$ の文字では $𝑃' (𝑎) = 0$ でもあるから，二つの式の対応する因子はどちらも $0! = 1$ と $𝑃 (𝑎) 0 = 1$ で一致する．また系 11.1.5 より $𝑃 𝑛 (T 𝑛 (𝑃)) = | T 𝑛 (𝑃) | 𝑒 - 𝑛 𝐻 (𝑃)$ で， $𝑃$ は長さ $𝑛$ の型だから $T 𝑛 (𝑃)$ は空でなく，この値は正である．よって割ることができ， $𝑛!$ も約分されて

𝑃 𝑛 (T 𝑛 (𝑃')) 𝑃 𝑛 (T 𝑛 (𝑃)) = \prod 𝑎 : 𝑃 (𝑎) > 0 (𝑛 𝑃 (𝑎))! (𝑛 𝑃' (𝑎))! 𝑃 (𝑎) 𝑛 𝑃' (𝑎) - 𝑛 𝑃 (𝑎)

である．

各因子を階乗の比で抑える．非負整数 $𝑢$ ， $𝑣$ が $𝑢 \geq 1$ を満たすとき $𝑢! / 𝑣! \leq 𝑢 𝑢 - 𝑣$ である．実際， $𝑣 \leq 𝑢$ なら $𝑢! / 𝑣!$ は $𝑣 + 1$ から $𝑢$ までの $𝑢 - 𝑣$ 個の整数の積で，どの因子も $𝑢$ 以下だから $𝑢 𝑢 - 𝑣$ 以下である． $𝑣 > 𝑢$ なら $𝑣! / 𝑢!$ が $𝑢 + 1$ から $𝑣$ までの $𝑣 - 𝑢$ 個の整数の積で，どの因子も $𝑢$ より大きいから $𝑢 𝑣 - 𝑢$ 以上であり，逆数をとると同じ不等式になる．

$𝑃 (𝑎) > 0$ の文字ごとに $𝑢 : = 𝑛 𝑃 (𝑎)$ ， $𝑣 : = 𝑛 𝑃' (𝑎)$ ととる． $𝑃$ と $𝑃'$ は長さ $𝑛$ の型だからこれらは非負整数で， $𝑃 (𝑎) > 0$ より $𝑢 \geq 1$ である． $𝑃 (𝑎) = 𝑢 / 𝑛$ に注意して，正の数 $𝑃 (𝑎) 𝑣 - 𝑢$ を両辺に掛けると

(𝑛 𝑃 (𝑎))! (𝑛 𝑃' (𝑎))! 𝑃 (𝑎) 𝑛 𝑃' (𝑎) - 𝑛 𝑃 (𝑎) \leq 𝑢 𝑢 - 𝑣 (𝑢 𝑛) 𝑣 - 𝑢 = 𝑛 𝑢 - 𝑣

を得る．これを $𝑃 (𝑎) > 0$ の文字について掛け合わせると， $𝑛$ の肩に乗るのは

\sum 𝑎 : 𝑃 (𝑎) > 0 (𝑛 𝑃 (𝑎) - 𝑛 𝑃' (𝑎)) = 𝑛 - 𝑛 = 0

である（第 $1$ の和は全文字にわたる和 $\sum 𝑎 𝑛 𝑃 (𝑎) = 𝑛$ に等しく，第 $2$ の和も，いま見ている場合には $𝑃 (𝑎) = 0$ の文字で $𝑃' (𝑎) = 0$ だから $\sum 𝑎 𝑛 𝑃' (𝑎) = 𝑛$ に等しい）．よって比は $𝑛 0 = 1$ 以下であり，主張を得る． $◻$

この不等式は，大数の法則を型類の言葉で言い直したものである． $𝑃$ に従う情報源から見ると，型が $𝑃$ の系列は各文字の出現回数が期待どおりの系列であり，型がずれた系列はそのぶん確率を失う．いちばん重い型類が自分の型類になるのはそのためである．

形式化上の注記. 補題 11.1.7 の不等式は multinomial_mul_prod_ratio_pow_le (InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean) が与えるが，型類の要素数を多項係数で書いた形になっている．要素数と多項係数が一致すること（命題 11.1.6）のほうはファイルの外に公開されていないので，本文の形そのままの単独の宣言は無い．

要素数は $𝑒 𝑛 𝐻 (𝑃)$ の前後にある

定理 11.1.8（型類の要素数）. $X$ を空でない有限アルファベット， $𝑛 \geq 1$ とし， $𝑃$ を長さ $𝑛$ の型（定義 11.1.1）とすると

(𝑛 + 1) - | X | 𝑒 𝑛 𝐻 (𝑃) \leq ∣ T 𝑛 (𝑃) ∣ \leq 𝑒 𝑛 𝐻 (𝑃)

である（ $𝐻$ は定義 1.1.1 のエントロピー）．

証明. 上界を示す． $𝑃 𝑛$ を $𝑃$ の $𝑛$ 重の積分布とすると，系 11.1.5 より $T 𝑛 (𝑃)$ の各点の確率は $𝑒 - 𝑛 𝐻 (𝑃)$ だから

𝑃 𝑛 (T 𝑛 (𝑃)) = ∣ T 𝑛 (𝑃) ∣ 𝑒 - 𝑛 𝐻 (𝑃)

である．左辺は確率だから $1$ 以下であり，両辺に $𝑒 𝑛 𝐻 (𝑃)$ を掛ければ上界を得る．

下界に移る．どの $𝑥 \in X 𝑛$ もただ一つの型 $ˆ 𝑃 𝑥$ をもつ（定義 11.1.1）から，長さ $𝑛$ の型の型類は $X 𝑛$ を重なりなく覆う．よって $𝑃'$ が長さ $𝑛$ の型の全体をわたる和として

1 = \sum 𝑃' 𝑃 𝑛 (T 𝑛 (𝑃'))

が成り立つ．右辺の各項は補題 11.1.7 より $𝑃 𝑛 (T 𝑛 (𝑃))$ 以下であり，項の個数は命題 11.1.3 より $(𝑛 + 1) | X |$ 以下だから

1 \leq (𝑛 + 1) | X | 𝑃 𝑛 (T 𝑛 (𝑃)) = (𝑛 + 1) | X | ∣ T 𝑛 (𝑃) ∣ 𝑒 - 𝑛 𝐻 (𝑃)

である．両辺に $(𝑛 + 1) - | X | 𝑒 𝑛 𝐻 (𝑃)$ を掛ければ下界を得る． $◼$

型類の要素数は $𝑒 𝑛 𝐻 (𝑃)$ の前後にあり，上下の隔たりは $(𝑛 + 1) | X |$ 倍である． $1 𝑛 l o g$ をとるとこの隔たりは $| X | l o g (𝑛 + 1) 𝑛$ になる．第2章定理 2.2.5 も典型集合の要素数を $2 𝑛 𝐻 (𝑋)$ のまわりで評価したが，そこには典型集合を切り出すときに選んだ幅 $𝜀$ が指数に残っていた．典型集合が「経験エントロピーが $𝐻 (𝑋)$ に近い」という幅のある条件で切り出した集合であるのに対し，型類は一つの型で切り出した集合なので，指数に幅が残らない．

形式化上の注記. 定理 11.1.8 の上界にも下界にも，対応する単独の宣言は無い．typeClassByCount_card_le と typeClassByCount_card_ge (InformationTheory/Shannon/Sanov/MultinomialLowerBound.lean) が同じ挟み込みを $𝑛 𝑛 / \prod 𝑎 (𝑛 𝑃 (𝑎)) 𝑛 𝑃 (𝑎)$ の形で与え，pow_div_prod_pow_eq_exp_n_entropyByCount (InformationTheory/Shannon/TypeClassLowerBound.lean) がこの量を $𝑒 𝑛 𝐻 (𝑃)$ に書き換える．二つの合成である．

経験エントロピーを型で読む

系 11.1.9. $X$ を空でない有限アルファベットとし，定義 2.1.1 の設定（i.i.d. 情報源 $𝑋 0, 𝑋 1, \dots$ ，各 $𝑋 𝑖$ は $X$ に値をとり，その分布は $𝑝$ ）で， $𝑝$ は $X$ 上の全点で正の分布とし， $𝑛 \geq 1$ とする．ブロック $𝑋 𝑛 = (𝑋 0, \dots, 𝑋 𝑛 - 1)$ の型を $ˆ 𝑃 𝑋 𝑛$ （定義 11.1.1）と書くと，定義 2.1.1 の経験エントロピー $ˆ 𝐻 𝑛 = - 1 𝑛 l o g 𝑝 (𝑋 0, \dots, 𝑋 𝑛 - 1)$ は

ˆ 𝐻 𝑛 = 𝐻 (ˆ 𝑃 𝑋 𝑛) + 𝐷 (ˆ 𝑃 𝑋 𝑛 ∥ 𝑝)

を満たす（ $𝐻$ は定義 1.1.1 のエントロピー， $𝐷$ は 1.6 節の相対エントロピー）．

証明. 補題 2.1.3 より $ˆ 𝐻 𝑛 = 1 𝑛 \sum 𝑖 < 𝑛 (- l o g 𝑝 (𝑋 𝑖))$ である．対数は積を和に変えるので，和を対数の中へ戻すと， $𝑝 𝑛$ を $𝑝$ の $𝑛$ 重の積分布として $ˆ 𝐻 𝑛 = - 1 𝑛 l o g \prod 𝑖 < 𝑛 𝑝 (𝑋 𝑖) = - 1 𝑛 l o g 𝑝 𝑛 ({𝑋 𝑛})$ である．

$𝑃 : = ˆ 𝑃 𝑋 𝑛$ と置く． $𝑃$ は長さ $𝑛$ の型であり， $𝑋 𝑛 \in T 𝑛 (𝑃)$ である． $𝑝$ は全点で正だから，命題 11.1.4 を $𝑄 : = 𝑝$ に当てて

𝑝 𝑛 ({𝑋 𝑛}) = e x p (- 𝑛 (𝐻 (𝑃) + 𝐷 (𝑃 ‖ 𝑝)))

を得る．両辺の対数をとって $- 1 / 𝑛$ を掛ければ主張になる． $◼$

系 11.1.9 は，第2章が一つの数として扱っていた経験エントロピーを二つに割る．第 $1$ 項 $𝐻 (ˆ 𝑃 𝑋 𝑛)$ は，実際に出た系列の型そのもののエントロピーであり，第 $2$ 項 $𝐷 (ˆ 𝑃 𝑋 𝑛 ‖ 𝑝)$ は，その型が真の分布からどれだけ隔たっているかである． $ˆ 𝐻 𝑛$ が $𝐻 (𝑋)$ からずれる原因が，型のエントロピーのずれと，型と真の分布の隔たりの二つに分かれる，ということでもある．

形式化上の注記. 第2章 2.1 節の形式化は経験エントロピーを $1$ 文字ごとの対数尤度の相加平均として定義しており，型を経由した系 11.1.9 の形に対応する単独の宣言は無い．

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

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

11.1 型と型類

定義

型は多項式個しかない

型類の中では確率が一定である

型類の要素数は多項係数である

いちばん重いのは自分の型類

要素数は𝑒𝑛𝐻(𝑃)の前後にある

経験エントロピーを型で読む

要素数は $𝑒 𝑛 𝐻 (𝑃)$ の前後にある