情報理論・符号理論の問題

確率をすべて分母 $24$ でそろえると、$a_1,\dots ,a_6$ の重みは $8,6,4,3,2,1$（単位 $\frac{1}{24}$）である。

瞬時符号の平均符号長の最小値は、ハフマン符号によって達成される（ハフマン符号の最適性）。そこで 3 元ハフマン符号を作る。

ダミー記号の追加　3 元ハフマン符号では、毎回 3 個の節点を 1 個にまとめるので、まとめるたびに節点の数は $2$ 減る。最後に節点がちょうど 1 個になるには、最初の記号数 $n$ が $n\equiv 1(\mathrm{mod}2)$ を満たす必要がある。$n=6$ は偶数なので、確率 $0$ のダミー記号 $d$ を 1 個加えて 7 個にする。重みは $8,6,4,3,2,1,0$ となる。

併合の手順
- 小さい 3 つ $0,1,2$（$d,a_6,a_5$）をまとめて $3$ にする。残り: $8,6,4,3,3$
- 小さい 3 つ $3,3,4$（$a_4$、先の併合節点、$a_3$）をまとめて $10$ にする。残り: $8,6,10$
- 残り 3 つをまとめて $24$（根）にする。

符号長　根からの深さが符号長なので
$$\ell (a_1)=1,\ell (a_2)=1,\ell (a_3)=2,\ell (a_4)=2,\ell (a_5)=3,\ell (a_6)=3$$
（ダミー $d$ も長さ $3$ だが確率 $0$ なので平均には寄与しない）。

これらの長さはクラフトの不等式
$$2\cdot 3^{-1}+2\cdot 3^{-2}+2\cdot 3^{-3}=\frac{18+6+2}{27}=\frac{26}{27}\le 1$$
を満たしており、確かにこの長さの 3 元瞬時符号が存在する（ダミーを含めると和はちょうど $1$）。

平均符号長
$$L=\frac{8\cdot 1+6\cdot 1+4\cdot 2+3\cdot 2+2\cdot 3+1\cdot 3}{24}=\frac{8+6+8+6+6+3}{24}=\frac{37}{24}.$$

（検算: 平均符号長は併合でできた節点の重みの和に等しく、$\frac{3+10+24}{24}=\frac{37}{24}$ となり一致する。）

よって求める最小値は $\frac{37}{24}$ である。

3 元ハフマン符号が最適なので、これで平均符号長の最小値を求める。記号数 6 は 3 元木が完全になる個数（奇数）ではないので、確率 0 のダミー記号を 1 つ加えて 7 個にする。

1. 確率の小さい 3 つ $0,\frac{1}{24},\frac{1}{12}$ を併合して $\frac{1}{8}$ を得る。
2. 残りは $\frac{1}{3},\frac{1}{4},\frac{1}{6},\frac{1}{8},\frac{1}{8}$。小さい 3 つ $\frac{1}{6},\frac{1}{8},\frac{1}{8}$ を併合して $\frac{5}{12}$ を得る。
3. 残りは $\frac{1}{3},\frac{1}{4},\frac{5}{12}$。この 3 つを併合して $1$ になる。

平均符号長は、併合で作られた内部節点の確率の和に等しい。
$$\frac{1}{8}+\frac{5}{12}+1=\frac{3+10+24}{24}=\frac{37}{24}.$$

検算として符号長から直接計算する。符号長は $a_1,a_2$ が 1、$a_3,a_4$ が 2、$a_5,a_6$ が 3 となる。
$$\frac{1}{3}+\frac{1}{4}+2\left(\frac{1}{6}+\frac{1}{8}\right)+3\left(\frac{1}{12}+\frac{1}{24}\right)=\frac{14}{24}+\frac{14}{24}+\frac{9}{24}=\frac{37}{24}.$$

したがって最小値は $\frac{37}{24}$ である。