Kraft–McMillan の不等式：$q_C$ が確率分布になる理由

符号語 $c_1c_2\cdots c_\ell$ に、区間 $I(x)=[\,0.c_1c_2\cdots c_\ell,\ 0.c_1c_2\cdots c_\ell+2^{-\ell}\,)$ を対応させる（$0.c_1\cdots c_\ell$ は2進小数）。この区間は、2進小数展開が $c_1\cdots c_\ell$ で始まる $[0,1)$ の数全体である。2つの符号語のどちらも他方の語頭でなければ、最初に食い違う桁で2進小数展開が分かれるので、対応する区間は重ならない（図 1.5.1 の右）。重ならない区間の長さの和は $[0,1)$ の長さ $1$ を超えないので (1.5.4) が出る。

逆に、(1.5.4) を満たす長さを小さい順に $\ell_1\le\ell_2\le\cdots\le\ell_m$ と並べ、$s_i=\sum_{j<i}2^{-\ell_j}$（$s_1=0$）とおく。$s_i$ は分母が $2^{\ell_{i-1}}$ の分数で $\ell_{i-1}\le\ell_i$ なので、$2^{\ell_i}s_i$ は整数になり、$s_i$ の2進小数展開は $\ell_i$ 桁で終わる。その $\ell_i$ 桁を $i$ 番目の符号語にする。$i$ 番目の符号語の区間は $[s_i,s_i+2^{-\ell_i})=[s_i,s_{i+1})$ で、$s_{m+1}=K\le1$ なので、区間は $[0,1)$ の中に重ならずに並ぶ。もし $i<j$ の符号語 $i$ が符号語 $j$ の語頭なら、$s_j$ は区間 $[s_i,s_i+2^{-\ell_i})$ に入るはずだが、$s_j\ge s_{i+1}=s_i+2^{-\ell_i}$ なので入らない。よって語頭符号になる。

符号語の長さの最大値を $\ell_{\max}$ とする。正の整数 $n$ について $K(C)^n$ を展開すると

$$K(C)^n=\sum_{x_1,\dots,x_n}2^{-(\ell(x_1)+\cdots+\ell(x_n))}=\sum_{k=1}^{n\ell_{\max}}A_k\,2^{-k}$$

となる。ここで $A_k$ は、つないだ長さがちょうど $k$ になる記号列 $x_1\cdots x_n$ の個数である。一意に復号できるので、異なる記号列は異なる $0$・$1$ の列に移る。長さ $k$ の $0$・$1$ の列は $2^k$ 通りしかないので $A_k\le2^k$ で、したがって $K(C)^n\le n\ell_{\max}$ である。もし $K(C)>1$ なら左辺は $n$ について指数関数的に増え、右辺は $n$ の1次でしか増えないので、大きな $n$ で矛盾する。よって $K(C)\le1$。