tecktom.com

典型集合の大きさ：enH\mathrm{e}^{nH} 個を数える

2026年10月15日8分で読めますAI生成教科書『虎の巻』第1部 第2章 驚きと Shannon エントロピー・典型系列
目次
  1. 典型集合の3つの性質
  2. 典型系列は最も確率の高い系列ではない
  3. 木下の層

AI 生成・木下が未勉強

相対エントロピーから情報と物理を組み立てる　第1部 第2章 §1.2.4　★★★ 典型集合はほぼ全確率を持ち、元の数は約 enH\mathrm{e}^{nH}。これより本質的に小さい集合では確率を集められない

典型集合の3つの性質

定理 1.2.6（典型集合の性質 ★★★）

任意の ϵ>0\epsilon>0 について次が成り立つ。

  1. (a) nn が十分大きければ Pr⁡(Xn∈Aϵ(n))≥1−ϵ\Pr(X^n\in A_\epsilon^{(n)})\ge1-\epsilon。
  2. (b) すべての nn で ∣Aϵ(n)∣≤en(H+ϵ)\lvert A_\epsilon^{(n)}\rvert \le\mathrm{e}^{n(H+\epsilon)}。
  3. (c) nn が十分大きければ ∣Aϵ(n)∣≥(1−ϵ) en(H−ϵ)\lvert A_\epsilon^{(n)}\rvert \ge(1-\epsilon)\,\mathrm{e}^{n(H-\epsilon)}。
証明

(a) は定理 1.2.4 で右辺を ϵ\epsilon 以下にすればよい（n≥σs2/ϵ3n\ge\sigma_s^2/\epsilon^3 で足りる）。

(b) 典型系列の確率は式 (1.2.13) から e−n(H+ϵ)\mathrm{e}^{-n(H+\epsilon)} 以上なので

1≥∑xn∈Aϵ(n)pn(xn)≥∣Aϵ(n)∣ e−n(H+ϵ).1\ge\sum_{x^n\in A_\epsilon^{(n)}}p^n(x^n)\ge\lvert A_\epsilon^{(n)}\rvert \,\mathrm{e}^{-n(H+\epsilon)} .

(c) 典型系列の確率は e−n(H−ϵ)\mathrm{e}^{-n(H-\epsilon)} 以下なので、(a) と合わせて1−ϵ≤∑xn∈Aϵ(n)pn(xn)≤∣Aϵ(n)∣ e−n(H−ϵ)1-\epsilon\le\sum_{x^n\in A_\epsilon^{(n)}}p^n(x^n)\le\lvert A_\epsilon^{(n)}\rvert \,\mathrm{e}^{-n(H-\epsilon)} となる。

(b) と (c) をまとめると、1nln⁡∣Aϵ(n)∣\frac1n\ln\lvert A_\epsilon^{(n)}\rvert は nn が大きいところで H−ϵH-\epsilon と H+ϵH+\epsilon の間にある。すべての系列の数は ∣X∣n=enln⁡∣X∣\lvert \mathcal X\rvert ^n=\mathrm{e}^{n\ln\lvert \mathcal X\rvert } なので、典型系列が全体に占める割合はおよそ e−n(ln⁡∣X∣−H)=e−nD(p ∥ u)\mathrm{e}^{-n(\ln\lvert \mathcal X\rvert -H)}=\mathrm{e}^{-nD(p\,\|\,u)}で、pp が一様分布でない限り nn について指数関数的に小さい。確率のほとんどすべてが、系列全体の中の指数関数的に小さな一部に集まっている。式 (1.2.6) の D(p ∥ u)D(p\,\|\,u) は、この割合の指数として意味を持つ。

エントロピーは何を数えているか

長さ nn の系列のうち「実際に出てくるもの」は約 enH\mathrm{e}^{nH} 個あり、どれもほぼ同じ確率 e−nH\mathrm{e}^{-nH} を持つ。したがってH=lim⁡1nln⁡(実際に出てくる系列の数)H=\lim\frac1n\ln(\text{実際に出てくる系列の数}) と読める。等確率の NN 通りから選ぶ場合の情報量 ln⁡N\ln N（Hartley）は、等確率でない情報源でも、長い系列にすれば「enH\mathrm{e}^{nH} 通りの等確率」に置き換えて使える。

典型系列は最も確率の高い系列ではない

典型系列という名前から、確率の高い系列を集めたものと思いやすいが、そうではない。p=0.1p=0.1 の2値の情報源では、最も確率の高い系列はすべて 00 の系列で、その確率 0.9n0.9^n は典型系列1つの確率 e−nH\mathrm{e}^{-nH} よりはるかに大きい。それでもすべて 00 の系列は、1文字あたりの驚きが−ln⁡0.9≈0.105-\ln0.9\approx0.105 nat で H≈0.325H\approx0.325 nat から遠いので典型集合に入らない。確率の高い系列は1つ1つの確率は大きいが数が少なく、典型系列は1つ1つの確率は小さいが数が多い。確率の総量で比べると、数の多い典型系列のほうが大きい。

この意味で典型集合は「確率をほぼ全部集めた集合のうち、元の数が最小のもの」と指数の精度で一致する。次の命題がそれを述べる。

命題 1.2.7（確率を集める集合の最小の大きさ ★★★）

0<δ<10<\delta<1 とする。Pr⁡(Xn∈B)≥1−δ\Pr(X^n\in B)\ge1-\delta を満たす任意の集合 B⊂XnB\subset\mathcal X^n について、nn が十分大きければ

∣B∣≥(1−δ−ϵ) en(H−ϵ).\lvert B\rvert \ge(1-\delta-\epsilon)\,\mathrm{e}^{n(H-\epsilon)} .

証明

nn が十分大きければ Pr⁡(Aϵ(n))≥1−ϵ\Pr(A_\epsilon^{(n)})\ge1-\epsilon なので、Pr⁡(B∩Aϵ(n))≥1−δ−ϵ\Pr(B\cap A_\epsilon^{(n)})\ge1-\delta-\epsilon である（2つの集合の外にある確率の和は δ+ϵ\delta+\epsilon 以下）。B∩Aϵ(n)B\cap A_\epsilon^{(n)} の元はどれも確率が e−n(H−ϵ)\mathrm{e}^{-n(H-\epsilon)} 以下なので1−δ−ϵ≤∣B∩Aϵ(n)∣ e−n(H−ϵ)≤∣B∣ e−n(H−ϵ)1-\delta-\epsilon\le\lvert B\cap A_\epsilon^{(n)}\rvert \,\mathrm{e}^{-n(H-\epsilon)}\le\lvert B\rvert \,\mathrm{e}^{-n(H-\epsilon)} となる。

命題と定理 1.2.6 (b) を合わせると、確率 1−δ1-\delta 以上を集める集合の大きさは、どう選んでも指数の精度で enH\mathrm{e}^{nH} である。この事実は第1部第5章のデータ圧縮の両側の評価になる。典型系列に 11 から番号を振れば、番号は n(H+ϵ)/ln⁡2+1n(H+\epsilon)/\ln2+1 ビットで書け、1文字あたり約 H/ln⁡2H/\ln2 ビットで系列を送れる（達成できる側）。命題 1.2.7 は、それより本質的に短い番号では確率 1−δ1-\delta 以上の系列に番号を付けきれないことを言う（越えられない側）。

例題 1.2.4　長さ 100 の系列で典型集合を数える ★★

オリジナルp(1)=0.1p(1)=0.1 の2値の情報源で n=100n=100、ϵ=0.05\epsilon=0.05 nat とする。

  1. (1) 典型集合に入る 11 の個数 kk の範囲を求め、典型集合の元の数 ∣Aϵ(100)∣\lvert A_\epsilon^{(100)}\rvert と、その確率を求めよ。
  2. (2) 定理 1.2.6 (b) の上限 en(H+ϵ)\mathrm{e}^{n(H+\epsilon)} と比べよ。また 1nln⁡∣Aϵ(100)∣\frac1n\ln\lvert A_\epsilon^{(100)}\rvert を H±ϵH\pm\epsilon と比べよ。
  3. (3) すべて 00 の系列の確率と、k=10k=10 の系列1つの確率の比を求めよ。
解答

(1) 式 (1.2.14) から条件は ∣k/100−0.1∣≤0.05/ln⁡9=0.02276\lvert k/100-0.1\rvert \le0.05/\ln9=0.02276、つまり 7.72≤k≤12.287.72\le k\le12.28 で、k=8,9,10,11,12k=8,9,10,11,12 の5通りである。

∣Aϵ(100)∣=∑k=812(100k)≈1.211×1015,Pr⁡(Aϵ(100))=∑k=812(100k)0.1k 0.9100−k≈0.596.\lvert A_\epsilon^{(100)}\rvert =\sum_{k=8}^{12}\binom{100}{k}\approx1.211\times10^{15},\qquad \Pr(A_\epsilon^{(100)})=\sum_{k=8}^{12}\binom{100}{k}0.1^k\,0.9^{100-k}\approx0.596 .

n=100n=100 ではまだ (a) の 1−ϵ1-\epsilon には達しない（図 1.2.3）。

(2) e100×0.3751≈1.95×1016\mathrm{e}^{100\times0.3751}\approx1.95\times10^{16} で、上限を満たしている。1100ln⁡(1.211×1015)≈0.347\frac1{100}\ln(1.211\times10^{15})\approx0.347 nat はH−ϵ=0.275H-\epsilon=0.275 と H+ϵ=0.375H+\epsilon=0.375 の間にある。全系列の数 2100≈1.27×10302^{100}\approx1.27\times10^{30} に対する割合は約 9.6×10−169.6\times10^{-16} にすぎない。

(3) k=10k=10 の系列の確率は 0.110 0.9900.1^{10}\,0.9^{90} で、k/n=pk/n=p ちょうどなので e−nH≈7.6×10−15\mathrm{e}^{-nH}\approx7.6\times10^{-15} に等しい。すべて 00 の系列の確率は0.9100≈2.66×10−50.9^{100}\approx2.66\times10^{-5} で、比は 0.910/0.110=910≈3.5×1090.9^{10}/0.1^{10}=9^{10}\approx3.5\times10^9 である。すべて 00 の系列は1つで 3.5×1093.5\times10^9 倍の確率を持つが、k=10k=10 の系列は (10010)≈1.73×1013\binom{100}{10}\approx1.73\times10^{13} 個あるので、確率の総量では k=10k=10 の組（0.1320.132）がすべて 00 の系列（2.7×10−52.7\times10^{-5}）を大きく上回る。

ほかの巻では

木下の勉強ステータス

木下はまだこの記事を勉強していません。

AI（Claude）が書いた教材を、木下が勉強しながら公開しています。式と数値は検算していますが、誤りが残っているかもしれません。誤りのご指摘・削除のご依頼をいただければ直します。 連絡先：support@tecktom.com

目次

この記事が含まれている連載

連載AI生成教科書『虎の巻』授業とは別に、分野をまたいで気になったことを AI（Claude）が教材にし、木下が勉強しながら公開しています。上の段は AI が書いた本文、下の段は木下が勉強したあとに書いた文です。1787本の記事・木下 智貴
← AI生成教科書『虎の巻』の記事一覧へ