← 情報理論 一覧

🎓 レベル：発展　|　重要度：A（必須）

📎 前提：自己情報量とエントロピー、結合・条件付きエントロピーと連鎖則　|　効く先：シャノンの情報源符号化定理

要点（BLUF）

• 漸近等分割性（AEP）：独立同分布（i.i.d.）な系列 $X_1,\dots,X_n$ について、$-\frac1n\log_2 p(X_1,\dots,X_n)$ は $n\to\infty$ でエントロピー $H$ に確率収束する。
• 結果として、長い系列の確率はどれもほぼ $2^{-nH}$ に等しく、典型集合 の要素数は約 $2^{nH}$ 個。全 $2^n$（または $|\mathcal X|^n$）通りのごく一部に確率が集中します。
• これが「$n$ 記号を平均 $nH$ bit で表せる（それ未満は不可）」＝シャノンの情報源符号化定理 の数理的な核心です。

1. 大数の法則の「情報版」

通常の大数の法則は「標本平均 → 期待値」。AEP はその対数尤度版です。i.i.d. なら $p(x_1,\dots,x_n)=\prod_i p(x_i)$ なので、

右辺は1記号あたりの自己情報量の期待値＝エントロピー。系列の「1記号あたりの驚き」は、長くすると必ず $H$ に近づく。言い換えると、長い系列の確率は

にほぼ等しくなります（指数の肩が $-nH$ に集中する）。

2. 典型集合（typical set）

$\varepsilon>0$ に対し、$\varepsilon$-典型集合 を「1記号あたりの驚きが $H$ に近い系列」の集合と定義します：

AEP から、$n$ が大きいとき次が成り立ちます。

• (a) 確率がほぼ1：$\Pr[A_\varepsilon^{(n)}] > 1-\varepsilon$。ほとんどの系列は典型的。
• (b) 各要素の確率：典型系列はどれも $2^{-n(H+\varepsilon)} \le p \le 2^{-n(H-\varepsilon)}$。ほぼ等確率。
• (c) 要素数：$|A_\varepsilon^{(n)}| \le 2^{n(H+\varepsilon)}$、かつ十分大きい $n$ で $\ge (1-\varepsilon)2^{n(H+\varepsilon)}$。だいたい $2^{nH}$ 個。

つまり「確率の塊は約 $2^{nH}$ 個のほぼ等確率な系列に集中し、残りの圧倒的多数の系列はほとんど起こらない」。$H<\log_2|\mathcal X|$ なら $2^{nH}\ll|\mathcal X|^n$ で、典型系列は全体のごく一部です。

3. コード：AEP と典型集合の集中（底2, bit）

ベルヌーイ情報源 $p(1)=0.2$（$H=0.7219$ bit）で、(1) $-\frac1n\log_2 p$ が $H$ に集中していく様子、(2) 典型集合に確率が集中することを確かめます。

import numpy as np

rng = np.random.default_rng(0)
# ベルヌーイ情報源 p(1)=0.2。各記号は独立同分布(i.i.d.)
p1 = 0.2
p = np.array([1-p1, p1])
H = -np.sum(p*np.log2(p))   # bit/記号
print(f"情報源エントロピー H = {H:.4f} bit/記号")
print(f"全系列数 2^n と 典型系列数 2^(nH) の比較:")
for n in [10, 50, 100, 200]:
    print(f"  n={n:>3}: 2^n = 2^{n}, 典型集合 ~ 2^(nH) = 2^{n*H:.1f}  (割合 ~ 2^(-n(1-H)) = {2**(-n*(1-H)):.2e})")
print("-"*56)

# --- AEP: (1/n)(-log2 p(系列)) -> H ---
print("AEP: 長い系列ほど (1/n)(-log2 p(x^n)) が H に集中")
for n in [10, 100, 1000, 10000]:
    X = (rng.random((2000, n)) < p1).astype(int)   # 2000本の系列
    logp = -(X*np.log2(p1) + (1-X)*np.log2(1-p1)).sum(axis=1)
    emp = logp / n
    print(f"  n={n:>5}: mean (1/n)(-log2 p) = {emp.mean():.4f}, std = {emp.std():.4f}  (H={H:.4f})")
print("-"*56)

# --- 典型集合のサイズと確率（n=100） ---
n = 100
eps = 0.1
N = 200000
X = (rng.random((N, n)) < p1).astype(int)
rate = -(X*np.log2(p1) + (1-X)*np.log2(1-p1)).sum(axis=1) / n
typical = np.abs(rate - H) < eps
print(f"n={n}, eps={eps}: 典型集合に入る系列の割合 = {typical.mean():.4f}")
print(f"  -> 確率のほとんど({typical.mean():.1%})が典型系列に集中（要素数は全{2**n:.0e}通りのごく一部）")

出力：

情報源エントロピー H = 0.7219 bit/記号
全系列数 2^n と 典型系列数 2^(nH) の比較:
  n= 10: 2^n = 2^10, 典型集合 ~ 2^(nH) = 2^7.2  (割合 ~ 2^(-n(1-H)) = 1.46e-01)
  n= 50: 2^n = 2^50, 典型集合 ~ 2^(nH) = 2^36.1  (割合 ~ 2^(-n(1-H)) = 6.53e-05)
  n=100: 2^n = 2^100, 典型集合 ~ 2^(nH) = 2^72.2  (割合 ~ 2^(-n(1-H)) = 4.26e-09)
  n=200: 2^n = 2^200, 典型集合 ~ 2^(nH) = 2^144.4  (割合 ~ 2^(-n(1-H)) = 1.81e-17)
--------------------------------------------------------
AEP: 長い系列ほど (1/n)(-log2 p(x^n)) が H に集中
  n=   10: mean (1/n)(-log2 p) = 0.7179, std = 0.2420  (H=0.7219)
  n=  100: mean (1/n)(-log2 p) = 0.7229, std = 0.0801  (H=0.7219)
  n= 1000: mean (1/n)(-log2 p) = 0.7218, std = 0.0248  (H=0.7219)
  n=10000: mean (1/n)(-log2 p) = 0.7221, std = 0.0079  (H=0.7219)
--------------------------------------------------------
n=100, eps=0.1: 典型集合に入る系列の割合 = 0.7777
  -> 確率のほとんど(77.8%)が典型系列に集中（要素数は全1e+30通りのごく一部）

出力の意味：(1) 1記号あたりの驚きの標準偏差は $n=10$ で $0.24$ → $n=10000$ で $0.008$ とどんどん縮み、平均は常に $H=0.7219$ 付近——長くするほど系列は「ほぼ等確率」に揃う（これが AEP）。(2) 典型集合の要素数は $2^{nH}$ 個で、$n=100$ なら $2^{72.2}$ 個。全 $2^{100}\approx10^{30}$ 通りに対し割合は $2^{-n(1-H)}\approx 4\times10^{-9}$——ごく一部に過ぎないのに、その一部に確率の 78%（さらに $n$ を増やせば1へ）が集まる。「ほとんど起こる系列」は全体のごくわずか。だから残りを捨てて典型系列だけに $nH$ bit の番号を振れば、ほぼ誤りなく圧縮できます。

4. 数式の直観的意味（符号化定理への橋）

AEP は圧縮の限界をそのまま与えます。典型系列が約 $2^{nH}$ 個なら、それらに通し番号を振るのに必要なビット数は $\log_2 2^{nH}=nH$ bit、つまり 1記号あたり平均 $H$ bit。非典型系列はほとんど現れないので無視してよい（誤り確率 → 0）。逆に $H$ bit 未満では番号が足りず、必ず復元に失敗する系列が残ります。これが シャノンの情報源符号化定理 の「達成可能性」と「逆」の両方の核心です。記憶のある定常情報源では $H$ をエントロピーレート（結合・条件付きエントロピーと連鎖則）に置き換えれば同じ話が成り立ちます。

⚠️ よくある誤解

• 「典型系列＝最も確率の高い系列」ではない：ベルヌーイ $p(1)=0.2$ で最も確率が高いのは「全部0」の系列ですが、それは典型的ではありません（1記号あたりの驚きが $H$ からずれる）。典型系列は「1の割合が約 20%」の系列です。
• 「AEP は各系列が等確率という意味」ではない：正確には典型集合の中でほぼ等確率。全系列が等確率なのではありません。
• 「AEP は有限 $n$ で厳密に成り立つ」ではない：あくまで $n\to\infty$ の極限（漸近）。有限 $n$ では幅 $\varepsilon$ のゆらぎが残ります（コードの std がそれ）。
• 「i.i.d. でなくても同じ式」ではない：独立同分布が基本。記憶があるときは $H$ をエントロピーレートに置き換える必要があります。

対応シミュレーション

• 本文のコードで AEP の集中（std が $\to 0$）と典型集合への確率集中を実証済み。

関連ノート

• 自己情報量とエントロピー（前提・1記号の驚き）
• 結合・条件付きエントロピーと連鎖則（記憶あり版＝エントロピーレート）
• 無歪み符号化とKraft不等式（典型系列に番号を振る符号）
• シャノンの情報源符号化定理（AEP が圧縮の限界を与える）
• 第1章 情報量とエントロピー 目次
• 情報理論 全体目次