出てくるもの (2)：情報源符号化定理

相対エントロピーから情報と物理を組み立てる　第1部 第5章 §1.5.5　★★★ 記号を $n$ 個まとめて符号にすると、1記号あたりの長さは $H/\ln2$ に $1/n$ の速さで近づく。固定長でも、典型集合を使えば率 $H$ で誤り確率を $0$ にできる

ブロック符号：可変長の場合

無記憶情報源の記号を $n$ 個まとめた $X^n=(X_1,\dots,X_n)$ を1つの記号とみなし、その上に符号を作る。$X^n$ の分布は $p^n(x^n)=p(x_1)\cdots p(x_n)$ で（右肩の $n$ は系列の長さで、冪ではない）、独立な確率変数のエントロピーは足し算になる（第1部第2章・第1部第3章）ので $H(X^n)=nH(X)$ である。

下界は、$D\ge0$ が $n$ によらず成り立つことによる。上界の幅が $1/n$ になるのは、整数に切り上げる損が符号語1つにつき1ビット未満で、それを $n$ 個の記号で分け合うからである。1.5.4節の最後の例（確率 $0.9$、$0.1$ の2値の情報源）で、ブロック長 $n$ の Huffman 符号の1記号あたりの平均符号長を数値で求めたものが図 1.5.3 である。$n=1$ の $1$ ビットから、$n=2$ で $0.645$、$n=4$ で $0.493$、$n=6$ で $0.470$ ビットと下がり、下界 $0.469$ ビットに近づく。ただし単調ではなく、$n=7$ では $0.474$ ビットと $n=6$ より長くなる。(1.5.9) が保証するのは $1/n$ の幅の帯に入ることだけで、帯の中のどこに落ちるかは $n$ ごとの $2$ の負べきへの合い方で決まる。

図 1.5.3　確率 $(0.9,0.1)$ の2値の無記憶情報源を $n$ 個ずつまとめて Huffman 符号にしたときの、1記号あたりの平均符号長（点線と点）。実線は定理 1.5.12 の下界と上界。値は $2^n$ 個の記号に Huffman の手続きを当てて数値で求めた（verify_ch1-05.py）。

固定長の符号と典型集合

可変長の符号は、記号列ごとに長さが変わる。これに対して、長さ $n$ の記号列をすべて同じ長さ $nR$ ビットの符号語で表す固定長の符号を考える（$R$ を符号化率と呼び、単位はビット毎記号）。$nR$ ビットで区別できる記号列は $2^{nR}$ 個までなので、$\lvert \mathcal X\rvert ^n$ 個のすべてに符号語を割り当てられない場合は、いくつかの列をあきらめ、それが出たら誤りとする。誤りの確率をいくらでも小さくできる率の下限が、ふたたび $H/\ln2$ になる。

ここで第1部第2章の漸近等分割性（AEP）を使う。$\epsilon>0$ に対して、

$$A_\epsilon^{(n)}=\Bigl\{x^n:\ \Bigl|-\frac1n\ln p^n(x^n)-H(X)\Bigr|\le\epsilon\Bigr\}\tag{1.5.10}$$

を典型集合と呼ぶ。第1部第2章で示したとおり、大数の法則から $\Pr(X^n\in A_\epsilon^{(n)})\to1$（$n\to\infty$）で、典型集合に入る列の確率はどれも $\mathrm{e}^{-n(H+\epsilon)}\le p^n(x^n)\le\mathrm{e}^{-n(H-\epsilon)}$ を満たし、その個数は $\lvert A_\epsilon^{(n)}\rvert \le\mathrm{e}^{n(H+\epsilon)}$ である。

(ii) の証明が示すのは、典型集合の1つ1つの列の確率がほぼ $\mathrm{e}^{-nH}$ にそろっているので、$\mathrm{e}^{nH}$ 個より少ない列をどう選んでも、確率の合計がほとんど集まらない、ということである。固定長でも可変長でも限界が同じ $H$ になるのは、確率の重みがほぼ $\mathrm{e}^{nH}$ 個の列に一様に広がっているからである。可変長の側では、同じ事実を分解 (1.5.5) と $D\ge0$ の形で使った。