2.4 強典型性

定義 2.2.1 の典型集合は，系列 $𝑥$ について確率 $𝑝 (𝑥)$ というただ一つの数しか見ていない．そのため，まったく違う見た目の系列どうしが同じ典型集合に入りうる． $- l o g 𝑝 (𝑥)$ は文字ごとの $- l o g 𝑝 (𝑥 𝑖)$ の和なので，ある文字が多すぎるぶんを別の文字が少なすぎるぶんが打ち消せば，経験的な出現頻度が真の分布からかなり離れていても，和としてはつじつまが合ってしまう．

本節では，この打ち消しを許さない，より細かい典型性を導入する．各文字の出現頻度が真の確率に一様に近いことを直接要求するもので，強典型性 と呼ばれる．定義 2.2.1 のほうは，区別するときには 弱典型性 と呼ぶ．強いほうを使うと，系列に含まれる文字の構成そのものが分かるので，確率の値だけでは追えない議論ができる．長さ $𝑛$ のブロックを一対で扱い，入力側と出力側が「そろって典型的」であることを要求する第6章の通信路符号化がその例である．

前節までと同じく，周辺分布は全アルファベット上で正とする（定理 2.4.4 で $l o g 𝑝 (𝑎)$ を各文字について足し上げるので，ここでは技術的にも必要になる）．

定義

定義 2.4.1（型と強典型集合）. 系列 $𝑥 \in X 𝑛$ に含まれる文字 $𝑎$ の個数を $𝑁 (𝑎 ∣ 𝑥)$ と書き， $𝑎 \mapsto 𝑁 (𝑎 ∣ 𝑥) / 𝑛$ を $𝑥$ の型（経験分布）と呼ぶ． $𝜀 > 0$ と $𝑛 \geq 1$ に対し，長さ $𝑛$ の 強典型集合 を

𝐴 * (𝑛) 𝜀 : = {𝑥 \in X 𝑛 : ∣ 𝑁 (𝑎 ∣ 𝑥) 𝑛 - 𝑝 (𝑎) ∣ \leq 𝜀 がすべての 𝑎 \in X で成り立つ}

で定める．

弱典型性が $X$ 上の和を 1 本とったあとの数を見るのに対し，強典型性は $X$ の各点で条件を課す．要求は文字数ぶんあり，しかもそれぞれが真の確率との差を直接押さえている．「型」という呼び名は， $𝑥$ をその経験分布で分類したときの分類名という含みである（形式化上の注記に出る「型」は Lean のデータ型のことで，別の語である）．

形式化: 強典型集合 stronglyTypicalSet (ソース)，文字の個数 $𝑁 (𝑎 ∣ 𝑥)$ にあたる typeCount (ソース)

例 2.4.2（弱典型だが強典型でない系列）. $X = {0, 1, 2}$ ， $𝑝 (0) = 1 / 2$ ， $𝑝 (1) = 𝑝 (2) = 1 / 4$ とする．驚きの値は $- l o g 𝑝 (0) = 1$ ， $- l o g 𝑝 (1) = - l o g 𝑝 (2) = 2$ で，エントロピーは

𝐻 (𝑋) = 12 \cdot 1 + 14 \cdot 2 + 14 \cdot 2 = 1.5

である． $𝑛$ を偶数とし， $0$ を $𝑛 / 2$ 個， $1$ を $𝑛 / 2$ 個含み， $2$ を一つも含まない系列 $𝑥$ をとる．その経験エントロピーは

- 1 𝑛 l o g 𝑝 (𝑥) = 12 \cdot (- l o g 12) + 12 \cdot (- l o g 14) = 12 \cdot 1 + 12 \cdot 2 = 1.5

となり，ちょうど $𝐻 (𝑋)$ に一致する．したがって $𝑥$ はどんな $𝜀 > 0$ に対しても弱典型である．一方その型 $(1 / 2, 1 / 2, 0)$ は真の分布 $(1 / 2, 1 / 4, 1 / 4)$ と第 2・第 3 座標で $1 / 4$ ずれているので， $𝜀 < 1 / 4$ なら強典型ではない．

例 2.4.2 で $1$ と $2$ の取り換えが効いたのは $- l o g 𝑝 (1) = - l o g 𝑝 (2)$ だったからで， $1$ を 1 個増やして $2$ を 1 個減らしても $- l o g 𝑝 (𝑥)$ はまったく変わらない．ただしこれは現象がいちばん見やすく出た場合であって，一般の理由はもう少し素っ気ない．定理 2.4.4 の証明で見るように，弱典型性が型に課すのは $\sum 𝑎 (𝑁 (𝑎 ∣ 𝑥) / 𝑛) (- l o g 𝑝 (𝑎))$ が $𝐻 (𝑋)$ に近いという 1 本の線形条件だけである．一方，型は $| X |$ 個の座標をもち（総和が 1 なので）自由度は $| X | - 1$ ある．条件 1 本で自由度 $| X | - 1$ を縛りきれるのは $| X | = 2$ のときだけで，しかもその 1 本が退化していないこと，すなわち係数 $- l o g 𝑝 (𝑎)$ が文字によって違うことが要る．

この読み方で両端を確かめられる．偏った二値（例 2.2.2）なら自由度 1 に対し条件 1 本，係数の差 $| l o g 𝑝 (0) - l o g 𝑝 (1) |$ は 0 でないので型が決まり，弱典型性の条件は頻度の条件そのものになる．ところが公平なコインでは $- l o g 𝑝 (0) = - l o g 𝑝 (1)$ で条件が退化し，どの系列も経験エントロピーがちょうど $𝐻 (𝑋)$ になるので全系列が弱典型になる一方，強典型集合は表の割合が $1 / 2$ 近辺のものだけの真部分集合である．二値でも二つの概念は分かれるのであって，分かれないのは偏った二値の場合だけである． $| X | \geq 3$ なら，係数がすべて相異なっていても条件 1 本では足りず，つねに分かれる．

性質1：強典型集合に入る確率も 1 に近づく

定理 2.4.3. 任意の $𝜀 > 0$ に対し $P r [𝑋 𝑛 \in 𝐴 * (𝑛) 𝜀] \to 1$ （ $𝑛 \to \infty$ ）．

証明. 文字 $𝑎$ を一つ固定し，指示変数 $𝑍 (𝑎) 𝑖 : = 𝟏 [𝑋 𝑖 = 𝑎]$ を考える． $𝑍 (𝑎) 𝑖$ は $𝑋 𝑖$ だけの関数だから i.i.d. であり， $𝔼 [𝑍 (𝑎) 𝑖] = P r [𝑋 𝑖 = 𝑎] = 𝑝 (𝑎)$ ，値は ${0, 1}$ に収まるので有界である．個数はこの指示変数の和 $𝑁 (𝑎 ∣ 𝑋 𝑛) = \sum 𝑖 < 𝑛 𝑍 (𝑎) 𝑖$ だから，大数の法則より

P r [∣ 𝑁 (𝑎 ∣ 𝑋 𝑛) 𝑛 - 𝑝 (𝑎) ∣ > 𝜀] ⟶ 0 .

$X$ は有限なので，この事象を $𝑎$ にわたって合併しても，確率の劣加法性（合併の確率は和以下）より

P r [𝑋 𝑛 \notin 𝐴 * (𝑛) 𝜀] \leq \sum 𝑎 \in X P r [∣ 𝑁 (𝑎 ∣ 𝑋 𝑛) 𝑛 - 𝑝 (𝑎) ∣ > 𝜀] ⟶ 0

であり，有限個の 0 に収束する列の和はやはり 0 に収束する． $◼$

証明の形は定理 2.1.4 と同じで，i.i.d. な有界確率変数の相加平均に大数の法則を当てる．ただし当てる対象が違う．定理 2.1.4 では対数尤度 $- l o g 𝑝 (𝑋 𝑖)$ という1 本の実数値量に当てたのに対し，ここでは文字ごとの指示変数に文字数ぶん当てて，最後に合併している．アルファベットが有限であることが，この「文字数ぶん」を有限個に留めるために効いている．

形式化: stronglyTypicalSet_prob_tendsto_one (ソース)

性質2：強典型なら弱典型

定理 2.4.4. $𝐿 : = \sum 𝑎 \in X ∣ l o g 𝑝 (𝑎) ∣$ とおく． $𝜀 𝐿 < 𝜀'$ ならば

𝐴 * (𝑛) 𝜀 \subseteq 𝑇 (𝑛) 𝜀' .

証明. 経験エントロピーを型で書き直す．補題 2.1.3 の和分解 $- l o g 𝑝 (𝑥) = \sum 𝑖 < 𝑛 (- l o g 𝑝 (𝑥 𝑖))$ を，同じ文字ごとにまとめると

- 1 𝑛 l o g 𝑝 (𝑥) = \sum 𝑎 \in X 𝑁 (𝑎 ∣ 𝑥) 𝑛 (- l o g 𝑝 (𝑎))

である．一方 $𝐻 (𝑋) = \sum 𝑎 𝑝 (𝑎) (- l o g 𝑝 (𝑎))$ だから，差は

- 1 𝑛 l o g 𝑝 (𝑥) - 𝐻 (𝑋) = \sum 𝑎 \in X (𝑁 (𝑎 ∣ 𝑥) 𝑛 - 𝑝 (𝑎)) (- l o g 𝑝 (𝑎))

と，型の各座標のずれの一次結合になる． $𝑥 \in 𝐴 * (𝑛) 𝜀$ なら各座標のずれは絶対値 $𝜀$ 以下だから，三角不等式で

∣ - 1 𝑛 l o g 𝑝 (𝑥) - 𝐻 (𝑋) ∣ \leq 𝜀 \sum 𝑎 \in X ∣ l o g 𝑝 (𝑎) ∣ = 𝜀 𝐿 < 𝜀',

すなわち $𝑥 \in 𝑇 (𝑛) 𝜀'$ である． $◼$

この計算は，弱典型性と強典型性の関係をそのまま式にしている．経験エントロピーと $𝐻 (𝑋)$ のずれは，型のずれを係数 $- l o g 𝑝 (𝑎)$ で重みづけて足したものにすぎない．だから型のずれを全座標で小さくすれば，経験エントロピーのずれも小さくなる．これが包含の内容である．逆向きが成り立たないのは，この一次結合が符号の違う項どうしで打ち消しあえるからで，例 2.4.2 はその打ち消しをちょうど起こしてみせた例である．定数 $𝐿$ は打ち消しを最悪の場合で見積もったときの増幅率にあたり，真の確率にきわめて小さい値があると大きくなる．

形式化: 包含 stronglyTypicalSet_subset_typicalSet，増幅率 $𝐿$ にあたる logSumAbs (ソース)

性質3：強典型集合の大きさ

定理 2.4.4 の包含は $𝜀 𝐿$ より真に大きい幅を要求するので，そのまま使うには余裕をいくらか足さねばならない．次の主張の $𝛿$ はその余裕で，いくらでも小さくとってよい． $𝜂$ は定理 2.2.5 と同じく，確率が 1 に届かないぶんの取りこぼしである．

系 2.4.5. $𝐿$ を定理 2.4.4 のものとし， $𝜀 > 0$ ， $𝛿 > 0$ ， $𝜂 \in (0, 1)$ とする． $𝑛$ が十分大きければ

(1 - 𝜂) 2 𝑛 (𝐻 (𝑋) - 𝜀 𝐿 - 𝛿) \leq ∣ 𝐴 * (𝑛) 𝜀 ∣ \leq 2 𝑛 (𝐻 (𝑋) + 𝜀 𝐿 + 𝛿) .

証明. $𝜀' : = 𝜀 𝐿 + 𝛿$ とおくと $𝜀 𝐿 < 𝜀'$ だから，定理 2.4.4 より $𝐴 * (𝑛) 𝜀 \subseteq 𝑇 (𝑛) 𝜀'$ である．

上界を示す．包含と定理 2.2.5 の上界から

∣ 𝐴 * (𝑛) 𝜀 ∣ \leq ∣ 𝑇 (𝑛) 𝜀' ∣ \leq 2 𝑛 (𝐻 (𝑋) + 𝜀')

であり，これは任意の $𝑛$ で成り立つ．

下界に移る．定理 2.4.3 より， $𝑛$ を十分大きくとれば $P r [𝑋 𝑛 \in 𝐴 * (𝑛) 𝜀] \geq 1 - 𝜂$ にできる．包含より $𝐴 * (𝑛) 𝜀$ の元はすべて $𝑇 (𝑛) 𝜀'$ の元だから，定理 2.2.4 の上界が各元に使えて

1 - 𝜂 \leq \sum 𝑥 \in 𝐴 * (𝑛) 𝜀 𝑝 (𝑥) \leq ∣ 𝐴 * (𝑛) 𝜀 ∣ \cdot 2 - 𝑛 (𝐻 (𝑋) - 𝜀') .

両辺に $2 𝑛 (𝐻 (𝑋) - 𝜀')$ を掛ければ下界を得る． $◼$

系 2.4.5 は定理 2.2.5 とほとんど同じ形をしている．強典型集合も，弱典型集合と同じく約 $2 𝑛 𝐻$ 個の元をもつということである． $𝜀$ を小さくすれば $𝜀 𝐿$ も小さくなるので，指数の肩の幅はいくらでも狭くできる．強典型性は条件としては弱典型性より真に強いのに，数え上げの粗さでは同じ答えに行き着く．指数の肩を $1 / 𝑛$ の精度でしか見ていないので，両者の差はこの尺度には現れない．差が見えるのは，個数を数えるときではなく，系列に含まれる文字の構成を直接問うときである．

弱典型側からの借りもの. 上界と下界のどちらも，強典型集合そのものを数えたのではなく，弱典型集合の評価を包含を通じて借りてきている．系 2.4.5 は強典型性そのものの性質というより，包含（定理 2.4.4）を通して弱典型集合の勘定が伝わったものである．

形式化: 下界 stronglyTypicalSet_card_ge_eventually (ソース)

系 2.4.5 には，本章の中で回収できる帰結が一つある．定理 2.4.3 と系 2.4.5 の上界を合わせると，強典型集合もまた「確率が 1 に近づき，要素数が約 $2 𝑛 𝐻$ 」という 2.3 節の符号化がまさに必要とした 2 条件を満たす．したがって前節の圧縮方式は，弱典型集合のかわりに強典型集合に番号を振っても同じレートで動く． $𝜀 𝐿$ のぶんだけ幅が広がるが， $𝜀$ を小さくとれば消える差である．強典型性を使うと符号が良くなるわけではない，というのがここでの結論であり，それでよい．強典型性の値打ちは圧縮率ではなく，系列に含まれる文字の構成を押さえられることのほうにある．

本章はエントロピーを二度定義し直したことになる．第1章では分布から計算する量として，本章では長い系列が実際に見せる振る舞いとしてとらえた．そして定理 2.3.6 で，その二つが圧縮率の下限という第三の顔でも一致した．第3章では独立性の仮定を外し，文字どうしに記憶のある情報源で同じ問いを立て直す．そこでも中心にいるのは，本章で作った「1 文字あたりの量が長さとともに落ち着く」という見方である．

形式化上の注記. 系 2.4.5 の上界に対応する単独の宣言は形式化されていない．本文の証明と同じく，包含stronglyTypicalSet_subset_typicalSet と弱典型側の上界 typicalSet_card_le（2.2 節）の合成として得られる形になっている．下界のほうは $𝑛$ の存在を含んだ形で単独で形式化されており，2.2 節の下界とはこの点で扱いが違う．

形式化は強典型集合が可測であることを別に示している（measurableSet_stronglyTypicalSet）．本文は有限集合の部分集合として扱うので，この一手は要らない．定理 2.4.3 の経路は対独立で足りるが，系 2.4.5 の下界は典型系列の点ごとの確率評価（定理 2.2.4）を経由するため相互独立を要求する．

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