MacKayの本で、5章の練習問題5.16にある話だが、答えを見ても良く意味が分からない。 Cover and Thomasを見ると、5.8にその節があって、証明は割とちゃんとしてるがノーテーションが分かりにくい。

という事でCover and Thomasの5.8を中心に証明をまとめてみる。 5.8そのままでは無いのと、MacKayのノートからリンクを貼りたいので別ポストとした。

示したい事、ハフマンコードは最適である

最適とは長さの期待値が最小な事。 前提としてはアルファベットの出現確率は知っている。

アルファベットはm種類とする。 1からmまでインデックスが振られてるとし、1番目のアルファベットが一番出やすく、m番目が一番出にくいように出やすさ順でインデックスを振るとして一般性を失わない。

補題、5.8.1 3つの性質を満たすinstantaneous codeの存在

この補題を前提に証明をするので、まずこの補題を理解するのが大切。

  1. 長さが確率の逆順に振られている （つまり \(p_i < p_j\) なら \(l_i \geq l_j\) ）
  2. 長さの上位2つのコードワードは同じ長さ
  3. 長さの上位2つは最後のビットだけ違って、それらは登場確率の下位2つに割り当てられてる

1は満たしてない所が一箇所あれば、それをi, jとしてコードワードを入れ替えて、元との長さの期待値の差を計算すると矛盾が示せる。

2はinstanteous codeなので、もし片方が長ければ同じ長さになるまで削っても良いはずだが、削ったらoptimalよりoptimal になってしまうから矛盾、ですぐ示せる。

3は満たしてなくてもoptimalな可能性はある。 ただ、2の理屈で、一番長いコードワードは2つ以上はあるはずで、満たしてないのは長いコードワードか複数あって、確率の下位2つが別々の分枝に入ってしまってるようなケース。

一番長いコードワードはprefixコードである事とoptimalityから、かならず兄弟がいるはずなので、この兄弟の枝に確率の下位2つを持ってくるのは、同じ長さの間での入れ替えのはずなので期待値は変わらない（性質1から下位の2番目は長さは二番目に長いはずだから同じ長さ）。

という事で性質3を満たすoptimalなコードは必ず作れる。

この3つの性質を満たすコードをカノニカルなコードと言う事にする。

証明

Cover and Thomasはノーテーションが分かりにくいので、決め直す。

今回用いるノーテーション

pが\(p_1\)から\(p_m\)まで順番に並んだ確率分布を表していて、それとm-2まで同じで、その次の項が\(p_{m-1}+p_m\)となってる、\(p^-\)という物を考える。

そして、pと\(p^-\)のそれぞれの最適なコードを別々に考える。

\(p^-\)の最適なコードを\(C^-_{m-1}\)とする。\(p^-\)起源のコードはマイナスをつける。

pの最適なコードでカノニカルな物の一つを、\(C_m\)と呼ぶ。

証明のあらすじ

証明のあらすじとしては、\(C^-_{m-1}\)から一つ伸ばして作った\(C^-_{m}\)が最適になってる、という事を示すことで、あとは再帰的に、要素2つからこの手続を繰り返せば、ハフマンコードが最適な事を言える。

\(C^-_{m}\)が最適になってる事を示す為には、\(C_m\)から一つ減らして作った\(C_{m-1}\)を作って、この2つのpと\(p^-\)の長さの期待値を比較する事で示す。

証明の中心の所

\(C^-_{m-1}\)で、m-1番目のコードにもう一桁足して、0をm-1、1をmのコードに割り当てた物を\(C^-_{m}\)とする。

\(C^-_{m-1}\)による長さの期待値を\(L^-_{m-1}\)と呼び、\(C^-_{m}\)による長さの期待値を\(L^-_{m}\)と呼ぶとする。

すると証明したいのは\(L^-_{m}\)が最小、という事。

\(L^-_{m}\)は、m-1とm以外は\(L^-_{m-1}\)と同じで、m-1とmは1だけ長い。

m-1が出る確率は\(p_{m-1}\)で、mは\(p_{m}\)だから、

\[L^-_{m} = L^-_{m-1} +p_{m-1} + p_{m}\]

定義により\(L^-_{m-1}\)は最小。 ただ\(L^-_{m}\)は最小かはこの時点では不明。

同様に\(C_m\)起源のコードの長さをそれぞれ\(L_m, L_{m-1}\)とすると、 \(L_{m-1}\)は\(L_m\)に最後二項をマージして一つ短いコードを割り当てることに相当する。

\(L_m\)をシグマで書き下してみると明らかなように、

\[L_{m-1} = L_m -p_m -p_{m-1}\]

となる。 \(L_m\)は定義により最小。だが\(L_{m-1}\)は最小かはこの時点では分からない。

この2つの式から

\(L_{m} \le L^-_{m} = L^-_{m-1} +p_{m-1} + p_{m}\) \(\le L_{m-1} +p_{m-1} + p_{m} \le L_{m}\)

なので

\[L_{m} = L^-_{m}\]

が言えた。