2.2 典型集合

定理 2.1.4 は「実際に出る系列の確率は $2 - 𝑛 𝐻$ 近辺にある」と言っていた．この「近辺にある」を満たす系列だけを集めた集合を作り，それがどれくらい大きいかを数えるのが本節である．数え上げの結果（約 $2 𝑛 𝐻$ 個）が，次節のデータ圧縮の限界をそのまま与える．

以下，周辺分布は全アルファベット上で正，すなわち $𝑝 (𝑎) > 0$ （ $𝑎 \in X$ ）と仮定する．これは情報源への制約ではなく記法の整理である． $𝑝 (𝑎) = 0$ の文字は $𝑋 𝑖$ が決してとらないのだから， $X$ からあらかじめ除いておけばよい．

定義

定義 2.2.1（典型集合）. $𝜀 > 0$ と $𝑛 \geq 1$ に対し，長さ $𝑛$ の 典型集合 を

𝑇 (𝑛) 𝜀 : = {𝑥 \in X 𝑛 : ∣ - 1 𝑛 l o g 𝑝 (𝑥) - 𝐻 (𝑋) ∣ < 𝜀}

で定める． $𝑇 (𝑛) 𝜀$ の元を 典型系列 という．

定義は経験エントロピーの条件をそのまま集合に書き直したものである． $𝑥$ が典型であるとは，その確率が

2 - 𝑛 (𝐻 (𝑋) + 𝜀) < 𝑝 (𝑥) < 2 - 𝑛 (𝐻 (𝑋) - 𝜀)

の範囲にあることにほかならない（両辺の $l o g$ をとって $- 1 𝑛$ 倍すれば定義に戻る）．つまり典型集合とは「確率がこの幅に収まっている系列の集まり」であって，系列の見た目（どの文字がどこに並んでいるか）には一切触れていない．

形式化: typicalSet (ソース)

例 2.2.2（偏ったコインの典型集合）. 例 2.1.2 の情報源（ $𝑝 (1) = 0.9$ ， $𝑝 (0) = 0.1$ ， $𝐻 (𝑋) \approx 0.469$ ）で，長さ $𝑛$ のブロック $𝑥$ に $1$ が $𝑞 𝑛$ 個含まれるとする．すると

- 1 𝑛 l o g 𝑝 (𝑥) = - 𝑞 l o g 0.9 - (1 - 𝑞) l o g 0.1 \approx 0.152 𝑞 + 3.322 (1 - 𝑞)

であり，これが $𝐻 (𝑋) \approx 0.469$ に近いことと，割合 $𝑞$ が $0.9$ に近いことが同値になる（左辺は $𝑞$ の一次式で，傾きの絶対値は $3.322 - 0.152 = 3.17$ だから， $| 𝑞 - 0.9 | < 𝜀 / 3.17$ が典型性の条件である）．

見落としやすい点が一つある．単独でいちばん確率の高いブロックは $1$ ばかりが並んだ $(1, 1, \dots, 1)$ で，その確率は $0.9 𝑛$ である．しかしこの系列の割合は $𝑞 = 1$ なので， $𝜀$ が小さければ典型集合に入らない．

例 2.2.2 の最後の注意は，典型集合の性質を一つに凝縮している．典型集合は「起こりやすい系列の集まり」ではない．個々の系列としては， $1$ ばかりの系列のほうが典型系列より確率が高い．それでも次に見るように，ブロックが典型集合に落ちる確率は 1 に近づく．確率のやや低い系列が，数の多さで圧倒するからである．典型集合が捉えているのは「1 個あたりの確率」ではなく「確率 $\times$ 個数」の釣り合いのほうである．

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

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

証明. 定義 2.2.1 より，事象 ${𝑋 𝑛 \in 𝑇 (𝑛) 𝜀}$ は ${| ˆ 𝐻 𝑛 - 𝐻 (𝑋) | < 𝜀}$ そのものである．定理 2.1.4 の確率収束は，その余事象の確率 $P r [| ˆ 𝐻 𝑛 - 𝐻 (𝑋) | \geq 𝜀]$ が 0 に収束すると述べているから，もとの事象の確率は 1 に収束する． $◼$

形式化: typicalSet_prob_tendsto_one (ソース)

性質2：典型系列の確率はどれもほぼ等しい

定理 2.2.4. $𝜀 > 0$ とする． $𝑥 \in 𝑇 (𝑛) 𝜀$ ならば

2 - 𝑛 (𝐻 (𝑋) + 𝜀) \leq 𝑝 (𝑥) \leq 2 - 𝑛 (𝐻 (𝑋) - 𝜀) .

証明. $𝑥 \in 𝑇 (𝑛) 𝜀$ は定義より $∣ - 1 𝑛 l o g 𝑝 (𝑥) - 𝐻 (𝑋) ∣ < 𝜀$ ，すなわち

𝑛 (𝐻 (𝑋) - 𝜀) < - l o g 𝑝 (𝑥) < 𝑛 (𝐻 (𝑋) + 𝜀)

と同値である．各辺に $- 1$ を掛けて不等号の向きを反転させ， $2$ を底とする指数をとれば主張を得る（実際には狭義の不等号で成り立つが，以降は等号込みの形で足りる）． $◼$

定理 2.2.4 が「漸近等分配性」という名前の由来である．典型系列はどれも確率が $2 - 𝑛 𝐻$ の同じ幅の中に収まっている．すなわち全確率のほぼ全部が，たがいにほぼ等確率な系列のあいだで分け合われ，系列ごとの差は指数の肩の $𝜀$ のぶんしか残らない． $𝑛$ が大きいとき $2 \pm 𝑛 𝜀$ という因子は決して小さくないが， $𝜀$ はいくらでも小さくとれるので， $1 𝑛 l o g 𝑝 (𝑥)$ という尺度で見るかぎり典型系列は互いに区別がつかない．

形式化: 上界 typicalSet_prob_le，下界 typicalSet_prob_ge (ソース)

性質3：典型集合の大きさは約 $2 𝑛 𝐻$

次の評価は上下で形が揃っていない．上界は確率の総和が 1 だという勘定だけで出るのでどの $𝑛$ でも成り立つが，下界は「ブロックがほぼ確実に典型集合に入る」という漸近的な事実（定理 2.2.3）を使うので， $𝑛$ が大きいときにしか言えない．しかもその確率は 1 に近づくだけで 1 には届かないから，取りこぼしのぶんの因子 $1 - 𝜂$ が残る．

定理 2.2.5. $𝜀 > 0$ とする．任意の $𝑛$ に対し

∣ 𝑇 (𝑛) 𝜀 ∣ \leq 2 𝑛 (𝐻 (𝑋) + 𝜀) .

また任意の $𝜂 \in (0, 1)$ に対し， $𝑛$ が十分大きければ

∣ 𝑇 (𝑛) 𝜀 ∣ \geq (1 - 𝜂) 2 𝑛 (𝐻 (𝑋) - 𝜀) .

証明. 上界を示す．全系列にわたる確率の総和は 1 だから，典型系列だけの和はそれ以下である．定理 2.2.4 の下界を各項に当てると

1 = \sum 𝑥 \in X 𝑛 𝑝 (𝑥) \geq \sum 𝑥 \in 𝑇 (𝑛) 𝜀 𝑝 (𝑥) \geq ∣ 𝑇 (𝑛) 𝜀 ∣ \cdot 2 - 𝑛 (𝐻 (𝑋) + 𝜀) .

両辺に $2 𝑛 (𝐻 (𝑋) + 𝜀)$ を掛ければ上界を得る．

下界に移る．定理 2.2.3 より， $𝑛$ を十分大きくとれば $P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀] \geq 1 - 𝜂$ にできる．この確率は典型系列の確率の和であり，定理 2.2.4 の上界を各項に当てると

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

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

形式化: 上界 typicalSet_card_le (ソース)

形式化上の注記. 下界に対応する単独の宣言は形式化されていない．typicalSet_card_ge (InformationTheory/Shannon/AEP/Basic/Achievability.lean) は「 $𝑛$ が十分大きければ」を含まず，確率評価 $1 - 𝜂 \leq P r [𝑋 𝑛 \in 𝑇 (𝑛) 𝜀]$ のほうを仮定として受け取る形をしている．本文の主張を作るには，その仮定を $𝑛$ について落とすtypicalSet_prob_ge_of_rate (InformationTheory/Shannon/AEP/Rate.lean) との合成が要る．本文の証明が定理 2.2.3 を経由するのと同じ 2 段である．

証明の要点は一つだけである．確率の和を「個数 $\times$ 1 個あたりの確率」で挟むと，確率の側は定理 2.2.4 が押さえてくれるので，残った個数の側が決まる．上界と下界で使う向きが逆になっているのに注意したい．個数を上から抑えるには 1 個あたりの確率を下から，下から抑えるには上から評価する必要があり，定理 2.2.4 が両側評価であることが両方に効いている．

規模感. 全系列は $| X | 𝑛 = 2 𝑛 l o g | X |$ 個ある．定理 1.1.5 により $𝐻 (𝑋) \leq l o g | X |$ であり，等号は一様分布のときに限る．分布が一様でなければ肩の差は正なので， $𝜀$ をそれより小さくとれば，典型集合の割合はおよそ $2 - 𝑛 (l o g | X | - 𝐻 (𝑋) - 𝜀)$ で指数的に 0 へ向かう（ $𝜀 \to 0$ の極限が $2 - 𝑛 (l o g | X | - 𝐻 (𝑋))$ である）．例 2.2.2 の偏ったコインなら，全系列 $2 𝑛$ 個に対し典型集合は約 $2 0.469 𝑛$ 個で，割合は $2 - 0.531 𝑛$ となる． $𝑛 = 100$ なら $10 - 16$ 程度である．それでもブロックはほぼ確実にその中に落ちる．定理 2.2.3 と定理 2.2.5 は，この一見矛盾する二つの事実を同時に述べている．

要素数を符号長に読み替える. 典型集合の要素数が約 $2 𝑛 𝐻$ なら，その各元に高々 $2 𝑛 (𝐻 + 𝜀)$ 通りの通し番号を振れる．番号を書き下すのに必要なのは $𝑛 (𝐻 + 𝜀)$ ビット，1 文字あたり $𝐻 + 𝜀$ ビットである．典型集合に入らない系列は捨ててよい．定理 2.2.3 がその確率を 0 に押し込むからである．これが次節の圧縮方式そのものであり，定理 2.2.5 の上界がそのままレートの上界になる．

形式化上の注記. 本文が $𝑝 (𝑎) > 0$ を「記法の整理」として置いたのに対し，形式化ではこれが実質的な仮定hpos になる．Real.log 0 = 0 という Mathlib の規約の下では，確率 0 の文字を含むブロックの経験エントロピーが $+ \infty$ ではなく有限値になってしまい，定理 2.2.4 の下界が壊れるためである．同じ理由で，形式化は典型集合が可測であることを別に示している（measurableSet_typicalSet）．本文は有限集合の部分集合として扱うので，この一手は要らない．

要素数の上界（定理 2.2.5 の前半）は，形式化でも本文でも独立性を使わない．ただし理由が違う．本文は典型集合をブロックの確率で定義しているので，その総和が 1 なのは確率分布であることから直ちに従う．形式化は典型集合を 1 文字ごとの対数尤度の和で定義しているので，周辺分布の積 $\prod 𝑖 𝑝 (𝑥 𝑖)$ が総和 1 になるという別の事実で同じ挟み込みが閉じ，ブロック確率と積を同一視する手間そのものが要らなくなっている．

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

2.2 典型集合

定義

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

性質2：典型系列の確率はどれもほぼ等しい

性質3：典型集合の大きさは約2𝑛𝐻

性質3：典型集合の大きさは約 $2 𝑛 𝐻$