エントロピーとシャノン・ファノ符号: 情報理論入門 4

$f$ を瞬時符号とする。$l_x = |f(x)|$ とすると、クラフトの不等式より $$\sum_{x \in \mathcal{X}} 2^{-l_x} \le 1 \tag{1}$$ が成り立つ。式 (1) が成り立つ範囲で $\sum_{x \in \mathcal{X}} p(x) l_x$ が最小となる $l \in \mathbb{R}^{\mathcal{X}}$ を考える。ラグランジュ乗数を $\lambda \ge 0$ とすると、ラグランジアンは $$L = \sum_{x \in \mathcal{X}} p(x) l_x + \lambda \left(\left(\sum_{x \in \mathcal{X}} 2^{-l_x}\right) – 1\right)$$ となる。これを $l_x$ について微分すると、 $$\frac{\partial L}{\partial l_x} = p(x) – \lambda (\log_e 2) 2^{-l_x}$$ となる。これをゼロとおくと、$l_x = – \log_2 \frac{p(x)}{\lambda log_e 2}$ となり、これを制約に代入すると、$\lambda = \frac{1}{\log_e 2}$ のとき、すなわち、$l_x = – \log_2 p(x)$ のとき最小となる。よって、 $$\begin{align*}\mathbb{E}_{x \sim p}[|f(x)|] &= \sum_{x \in \mathcal{X}} p(x) |f(x)| \\ &=\sum_{x \in \mathcal{X}} p(x) l_x \\ &\ge – \sum_{x \in \mathcal{X}} p(x) \log_2 p(x) \\ &= H(\mathcal{X}, p)\end{align*}$$ が成り立つ。

$l_x = \text{ceil}\left(\log_2 \frac{1}{p(x)}\right)$ とすると、$l_x$ は正整数であり、 $$\begin{align*} \sum_{x \in \mathcal{X}} 2^{-l_x} &= \sum_{x \in \mathcal{X}} 2^{-\text{ceil}\left(\log_2 \frac{1}{p(x)}\right)} \\ &\le \sum_{x \in \mathcal{X}} 2^{-\log_2 \frac{1}{p(x)}} \\ &= \sum_{x \in \mathcal{X}} p(x) \\ &= 1\end{align*}$$ より、$l_x$ はクラフトの不等式の条件を満たす。よって、このような瞬時符号を構成できる。

$l_x = \text{ceil}\left(\log_2 \frac{1}{p(x)}\right)$ とすると、 $$\begin{align*} \mathbb{E}_{x \sim p}[|f(x)|] &= \sum_{x \in \mathcal{X}} p(x) l_x \\ &= \sum_{x \in \mathcal{X}} p_x \text{ceil}\left(\log_2 \frac{1}{p(x)}\right) \\ &< \sum_{x \in \mathcal{X}} p_x \left(\left(\log_2 \frac{1}{p(x)}\right) + 1\right) \\ &= \left(-\sum_{x \in \mathcal{X}} p_x \log_2 p(x)\right) + \sum_{x \in \mathcal{X}} p(x) \\ &= H_1(\mathcal{X}, p) + 1\end{align*}$$