ベルヌイモデルのエントロピーやKLダイバージェンスを考える

$P_{Ber}$の$H_n(x)$や$D_n(x\parallel y)$を考える

$n$回の試行結果である$x^n$の1の発生回数を$m$とすると$P_{Ber}$の$\theta$の最尤推定値$\hat{\theta }$は$\frac{m}{n}$となる． $$\begin{array}{rcl}{\displaystyle \hat{\theta }}& =& {\displaystyle \frac{m}{n}}\\ H_n(P)& \stackrel{\mathrm{def}}{=}& E_P^n[-{\log }_{2}P(X^n)]\\ {\displaystyle H(\theta )}& \stackrel{\mathrm{def}}{=}& {\displaystyle -\theta {\log }_2\left(\theta \right)-(1-\theta ){\log }_2(1-\theta )\dots P=P_{Ber}\mathrm{で}\theta \mathrm{を}\mathrm{引}\mathrm{数}\mathrm{と}\mathrm{し}\mathrm{て}\mathrm{括}\mathrm{弧}\mathrm{の}\mathrm{内}\mathrm{側}\mathrm{に}\mathrm{記}\mathrm{載}\mathrm{す}\mathrm{る}．}\\ {\displaystyle H(\hat{\theta })}& =& {\displaystyle -\hat{\theta }{\log }_2\left(\hat{\theta }\right)-(1-\hat{\theta }){\log }_2(1-\hat{\theta })}\\ & =& {\displaystyle -\frac{m}{n}{\log }_2\left(\frac{m}{n}\right)-(1-\frac{m}{n}){\log }_2(1-\frac{m}{n})}\\ & =& {\displaystyle \frac{1}{n}\{-m{\log }_2\left(\frac{m}{n}\right)-(n-m){\log }_2\left(\frac{n-m}{n}\right)\}}\\ & =& {\displaystyle \frac{1}{n}\left\{{\displaystyle -m{\log }_2\left(m\right){\displaystyle +m{\log }_2\left(n\right){\displaystyle -(n-m){\log }_2(n-m){\displaystyle +(n-m){\log }_2\left(n\right){\displaystyle }}}}}\right\}}\\ {\displaystyle D(\hat{\theta }\parallel \theta )}& =& {\displaystyle \hat{\theta }{\log }_2\left(\frac{\hat{\theta }}{\theta }\right)+(1-\hat{\theta }){\log }_2\left(\frac{1-\hat{\theta }}{1-\theta }\right)}\\ & =& {\displaystyle \frac{m}{n}{\log }_2\left(\frac{\frac{m}{n}}{\theta }\right)+(1-\frac{m}{n}){\log }_2\left(\frac{1-\frac{m}{n}}{1-\theta }\right)}\\ & =& {\displaystyle \frac{1}{n}\left\{{\displaystyle m{\log }_2\left(\frac{\frac{m}{n}}{\theta }\right){\displaystyle +(n-m){\log }_2\left(\frac{1-\frac{m}{n}}{1-\theta }\right){\displaystyle }}}\right\}}\\ & =& {\displaystyle \frac{1}{n}\left\{{\displaystyle m{\log }_2\left(\frac{m}{n}\right){\displaystyle -m{\log }_2\left(\theta \right){\displaystyle +(n-m){\log }_2(1-\frac{m}{n}){\displaystyle {\displaystyle -(n-m){\log }_2(1-\theta ){\displaystyle }}}}}}\right\}}\\ & =& {\displaystyle \frac{1}{n}\left\{{\displaystyle m{\log }_2\left(m\right){\displaystyle -m{\log }_2\left(n\right){\displaystyle -m{\log }_2\left(\theta \right){\displaystyle +(n-m){\log }_2(n-m){\displaystyle -(n-m){\log }_2\left(n\right){\displaystyle -(n-m){\log }_2(1-\theta ){\displaystyle }}}}}}}\right\}}\\ {\displaystyle H(\hat{\theta })+D(\hat{\theta }\parallel \theta )}& =& {\displaystyle \frac{1}{n}\left\{{\displaystyle -m{\log }_2\left(\theta \right)-(n-m){\log }_2(1-\theta ){\displaystyle }}\right\}}\\ {\displaystyle n\{H(\hat{\theta })+D(\hat{\theta }\parallel \theta )\}}& =& {\displaystyle -m{\log }_2\left(\theta \right)-(n-m){\log }_2(1-\theta )}\end{array}$$ $$\begin{array}{rcl}-{\log }_2(L(\theta |x^n))& =& -m{\log }_2\left(\theta \right)-(n-m){\log }_2(1-\theta )\\ n\{H\left(\hat{\theta }\right)+D(\hat{\theta }\parallel \theta )\}& =& -m{\log }_2\left(\theta \right)-(n-m){\log }_2(1-\theta )\\ -{\log }_2\left(L(\theta |x^n)\right)& =& n\{H\left(\hat{\theta }\right)+D(\hat{\theta }\parallel \theta )\}\\ & =& nH\left(\hat{\theta }\right)+nD(\hat{\theta }\parallel \theta )\\ -{\log }_2\left(L(\hat{\theta }|x^n)\right)& =& nH\left(\hat{\theta }\right)+nD(\hat{\theta }\parallel \hat{\theta })\dots \theta =\hat{\theta }\\ & =& nH\left(\hat{\theta }\right)+n0\dots D(\hat{\theta }\parallel \hat{\theta })=0\\ & =& nH\left(\frac{m}{n}\right)\dots \hat{\theta }=\frac{m}{n}\end{array}$$

ベルヌイモデルとベルヌイモデルの尤度に対する情報量

ベルヌイモデル $P_{Ber}$

$$\begin{array}{r}P(X|\theta )=\{\begin{array}{ll}{\displaystyle \theta }& :(X=1)\\ {\displaystyle 1-\theta }& :(X=0)\end{array}\\ {\displaystyle P_{Ber}=\{P(X|\theta ):(0\le \theta \le 1)\}}\end{array}$$

$x^n$を$P_{Ber}$で最短長の符号化をすることを考える

データ列$x^n$が与えられた時の生成確率$P(x^n|\theta )$を$\theta$の凾数とみなすと $$\begin{array}{rcl}{\displaystyle L(\theta |x^n)}& =& P(x^n|\theta )\end{array}$$ としてこれを尤度(likelihood)と呼ぶ．

ベルヌイモデルの尤度に対する情報量

$x^n$の1の発生回数を$m$とすると0の発生回数は$n-m$となるので最尤推定値(maximum likelihood estimator)は $$\begin{array}{rcl}{\displaystyle L(\theta |x^n)}& =& {\theta }^m(1-\theta {)}^{(n-m)}\end{array}$$ 情報量(=符号長)を考えると $$\begin{array}{rcl}{\displaystyle -{\log }_2(L(\theta |x^n))}& =& -{\log }_2({\theta }^m(1-\theta {)}^{(n-m)})\\ & =& {\displaystyle -{\log }_2\left({\theta }^m\right)-{\log }_2((1-\theta {)}^{(n-m)})}\\ & =& {\displaystyle -m{\log }_2\left(\theta \right)-(n-m){\log }_2(1-\theta )}\end{array}$$

確率Pで発生しているデータ系列を確率Qに基づく符号化した際のKullback-Leiblerダイバージェンス

例:確率Pで発生しているデータ系列を確率Qに基づく符号化した際のKullback-Leiblerダイバージェンス$D_n$

$y_1$	$y_2$	$x^2$ $=y_1{y}_2$	$P(x^2)$	$Q(x^2)$	$Q^{\prime }(x^2)$	$Q^{″}(x^2)$
0	0	00	$\frac{1}{8}$	$\frac{1}{8}$	$\frac{1}{2}$	$\frac{1}{4}$
0	1	01	$\frac{1}{8}$	$\frac{1}{8}$	$\frac{1}{4}$	$\frac{1}{4}$
1	0	10	$\frac{1}{4}$	$\frac{1}{4}$	$\frac{1}{8}$	$\frac{1}{4}$
1	1	11	$\frac{1}{2}$	$\frac{1}{2}$	$\frac{1}{8}$	$\frac{1}{4}$

$Q(x^2)$でのダイバージェンス

$$\begin{array}{rcl}{D}_n(P\parallel Q)& =& E_P^n[{\log }_2\frac{P(X^n)}{Q(X^n)}]\\ & =& {\displaystyle \sum _{x^2\in {\chi }^2}P(x^2){\log }_2\frac{P(x^2)}{Q(x^2)}}\\ & =& \frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{8}}+\frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{8}}+\frac{1}{4}\times {\log }_2\frac{\frac{1}{4}}{\frac{1}{4}}+\frac{1}{2}\times {\log }_2\frac{\frac{1}{2}}{\frac{1}{2}}\\ & =& \frac{1}{8}\times {\log }_{2}1+\frac{1}{8}\times {\log }_{2}1+\frac{1}{4}\times {\log }_{2}1+\frac{1}{2}\times {\log }_{2}1\\ & =& \frac{1}{8}\times 0+\frac{1}{8}\times 0+\frac{1}{4}\times 0+\frac{1}{2}\times 0\\ & =& 0+0+0+0\\ & =& 0\end{array}$$

$Q^{\prime }(x^2)$でのダイバージェンス

$$\begin{array}{rcl}{D}_n(P\parallel Q^{\prime })& =& E_P^n[{\log }_2\frac{P(X^n)}{Q^{\prime }(X^n)}]\\ & =& {\displaystyle \sum _{x^2\in {\chi }^2}P(x^2){\log }_2\frac{P(x^2)}{Q^{\prime }(x^2)}}\\ & =& \frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{2}}+\frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{4}}+\frac{1}{4}\times {\log }_2\frac{\frac{1}{4}}{\frac{1}{8}}+\frac{1}{2}\times {\log }_2\frac{\frac{1}{2}}{\frac{1}{8}}\\ & =& \frac{1}{8}\times {\log }_2\frac{1}{4}+\frac{1}{8}\times {\log }_2\frac{1}{2}+\frac{1}{4}\times {\log }_{2}2+\frac{1}{2}\times {\log }_{2}4\\ & =& \frac{1}{8}\times -2+\frac{1}{8}\times -1+\frac{1}{4}\times 1+\frac{1}{2}\times 2\\ & =& -\frac{1}{4}-\frac{1}{8}+\frac{1}{4}+1\\ & =& \frac{7}{8}=0.875\end{array}$$

$Q^{″}(x^2)$でのダイバージェンス

$$\begin{array}{rcl}{D}_n(P\parallel Q^{″})& =& E_P^n[{\log }_2\frac{P(X^n)}{Q^{″}(X^n)}]\\ & =& {\displaystyle \sum _{x^2\in {\chi }^2}P(x^2){\log }_2\frac{P(x^2)}{Q^{″}(x^2)}}\\ & =& \frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{4}}+\frac{1}{8}\times {\log }_2\frac{\frac{1}{8}}{\frac{1}{4}}+\frac{1}{4}\times {\log }_2\frac{\frac{1}{4}}{\frac{1}{4}}+\frac{1}{2}\times {\log }_2\frac{\frac{1}{2}}{\frac{1}{4}}\\ & =& \frac{1}{8}\times {\log }_2\frac{1}{2}+\frac{1}{8}\times {\log }_2\frac{1}{2}+\frac{1}{4}\times {\log }_{2}1+\frac{1}{2}\times {\log }_{2}2\\ & =& \frac{1}{8}\times -1+\frac{1}{8}\times -1+\frac{1}{4}\times 0+\frac{1}{2}\times 1\\ & =& -\frac{1}{8}-\frac{1}{8}+0+\frac{1}{2}\\ & =& \frac{1}{4}=0.25\end{array}$$

KLダイバージェンスの下限

${\log }_{\mathrm{e}}x\le (x-1)$の証明

$$\begin{array}{rcl}f(x)& =& x-1-{\log }_{\mathrm{e}}x\\ f^{\prime }(x)& =& \frac{x-1}{x}\\ f^{″}(x)& =& \frac{1}{x^2}\\ f^{\prime }=0& \mathrm{は}& x=1\end{array}$$ よって$f^{″}(1)>0$より$f$は$x=1$で極小であり，また $x<1$ で常に$f^{\prime }<0$ 及び $x>1$ で常に$f^{\prime }>0$ なので最小でもある．
$f(1)=0$なので$f\ge 0$である． $$\begin{array}{rcl}x-1-{\log }_{\mathrm{e}}x& \ge & 0\\ -{\log }_{\mathrm{e}}x& \ge & -x+1=-(x-1)\\ {\log }_{\mathrm{e}}x& \le & (x-1)\end{array}$$

${\log }_{\mathrm{e}}x\le (x-1)$の底の変換等の式変形

$$\begin{array}{rcl}{\log }_{\mathrm{e}}x& \le & (x-1)\\ & \le & -(1-x)\\ -{\log }_{\mathrm{e}}x& \ge & (1-x)\\ {\log }_{\mathrm{e}}\frac{1}{x}& \ge & (1-x)\\ \frac{{\log }_2\frac{1}{x}}{{\log }_2\mathrm{e}}& \ge & (1-x)\\ {\log }_2\frac{1}{x}& \ge & ({\log }_2\mathrm{e})(1-x)\end{array}$$

$D_n(P\parallel Q)$の下限

$$\begin{array}{rcl}{\log }_2\frac{1}{x}& \ge & ({\log }_2\mathrm{e})(1-x)\\ {\log }_2\frac{1}{\frac{Q(x^n)}{P(x^n)}}& \ge & ({\log }_2\mathrm{e})\{1-\frac{Q(x^n)}{P(x^n)}\}& x=\frac{Q(x^n)}{P(x^n)}\mathrm{と}\mathrm{し}\mathrm{て}\mathrm{代}\mathrm{入}\\ {\log }_2\frac{P(x^n)}{Q(x^n)}& \ge & ({\log }_2\mathrm{e})\{1-\frac{Q(x^n)}{P(x^n)}\}\\ E_P^n[{\log }_2\frac{P(X^n)}{Q(X^n)}]& \ge & E_P^n[({\log }_2\mathrm{e})\{1-\frac{Q(X^n)}{P(X^n)}\}]& \mathrm{両}\mathrm{辺}\mathrm{期}\mathrm{待}\mathrm{値}\mathrm{を}\mathrm{取}\mathrm{る}\\ D_n(P\parallel Q)& \ge & E_P^n[({\log }_2\mathrm{e})\{1-\frac{Q(X^n)}{P(X^n)}\}]\\ & \ge & ({\log }_2\mathrm{e})E_P^n[1-\frac{Q(X^n)}{P(X^n)}]& E[cX]=cE[X]\\ & \ge & {\displaystyle ({\log }_2\mathrm{e})[\{1-\frac{Q(x^m)}{P(x^m)}\}P(x^m)+\{1-\frac{Q(x_2^n)}{P(x_2^n)}\}P(x_2^n)+\cdots ]}\\ & \ge & {\displaystyle ({\log }_2\mathrm{e})[\{P(x^m)-Q(x^m)\}+\{P(x_2^n)-Q(x_2^n)\}+\cdots ]}\\ & \ge & {\displaystyle ({\log }_2\mathrm{e})[\{P(x^m)+P(x_2^n)+\cdots \}-\{Q(x^m)+Q(x_2^n)+\cdots \}]}\\ & \ge & {\displaystyle ({\log }_2\mathrm{e})\{\sum _{X^n}P(x^n)-\sum _{X^n}Q(x^n)\}}\\ & \ge & {\displaystyle ({\log }_2\mathrm{e})\{1-\sum _{X^n}Q(x^n)\}}& {\displaystyle \sum _{X^n}P(x^n)=1}\\ & \ge & 0& {\displaystyle \sum _{X^n}Q(x^n)=1\mathrm{の}\mathrm{と}\mathrm{き}\mathrm{は}0}\end{array}$$

平均符号長の下限(エントロピー, Kullback-Leiblerダイバージェンス)

符号長($l(x^n)$)がShannon情報量($-{\log }_{2}P(x^n)$)と等しい場合(確率$P(x^n)$に基づく符号化(P-based coding))

$$\begin{array}{rcl}\mathcal{l}(x^n)& =& -{\log }_{2}P(x^n)\\ -\mathcal{l}(x^n)& =& {\log }_{2}P(x^n)\\ 2^{-\mathcal{l}(x^n)}& =& 2^{{\log }_{2}P(x^n)}\\ & =& P(x^n)\\ P(x^n)& =& 2^{-\mathcal{l}(x^n)}\\ {\displaystyle \sum _{x^n\in {\chi }^n}P(x^n)}& \le & 1& \dots P(x^n)\mathrm{は}\mathrm{確}\mathrm{率}\mathrm{質}\mathrm{量}\mathrm{凾}\mathrm{数}\mathrm{な}\mathrm{の}\mathrm{で}\mathrm{総}\mathrm{和}\mathrm{は}1,P(x^n)\mathrm{を}\mathrm{劣}\mathrm{確}\mathrm{率}\mathrm{凾}\mathrm{数}\mathrm{と}\mathrm{す}\mathrm{る}\mathrm{ケ}\mathrm{ー}\mathrm{ス}\mathrm{を}\mathrm{考}\mathrm{え}\mathrm{る}\mathrm{場}\mathrm{合}\mathrm{は}\mathrm{総}\mathrm{和}\mathrm{は}1\mathrm{以}\mathrm{下}\\ {\displaystyle \sum _{x^n\in {\chi }^n}{2}^{-\mathcal{l}(x^n)}}& \le & 1& \dots 2^{-\mathcal{l}(x^n)}=P(x^n)\mathrm{な}\mathrm{の}\mathrm{で}\mathrm{や}\mathrm{は}\mathrm{り}\mathrm{総}\mathrm{和}\mathrm{は}1,P(x^n)\mathrm{を}\mathrm{劣}\mathrm{確}\mathrm{率}\mathrm{凾}\mathrm{数}\mathrm{と}\mathrm{す}\mathrm{る}\mathrm{ケ}\mathrm{ー}\mathrm{ス}\mathrm{を}\mathrm{考}\mathrm{え}\mathrm{る}\mathrm{場}\mathrm{合}\mathrm{は}\mathrm{総}\mathrm{和}\mathrm{は}1\mathrm{以}\mathrm{下}\end{array}$$ 劣確率凾数は $P(x)\ge 0$ の条件は確率(質量)凾数と同じで，$\sum P(x)\le 1$となる凾数．

符号長の期待値とその下限

$$\begin{array}{rcll}{E}_P^n[\mathcal{l}(X^n)]& \ge & H_n(P)& \dots \mathrm{符}\mathrm{号}\mathrm{長}\mathrm{の}\mathrm{期}\mathrm{待}\mathrm{値}\mathrm{・}\mathrm{平}\mathrm{均}\mathrm{符}\mathrm{号}\mathrm{長}\mathrm{の}\mathrm{下}\mathrm{限}\\ H_n(P)& \stackrel{\mathrm{def}}{=}& E_P^n[-{\log }_{2}P(X^n)]& \dots \mathrm{確}\mathrm{率}P(x^n)\mathrm{に}\mathrm{基}\mathrm{づ}\mathrm{く}\mathrm{符}\mathrm{号}\mathrm{化}\mathrm{の}\mathrm{長}\mathrm{さ}\mathrm{で}\mathrm{あ}\mathrm{る}\mathrm{こ}\mathrm{と}\mathrm{が}\mathrm{条}\mathrm{件}\mathcal{l}(X^n)=-{\log }_{2}P(X^n)\end{array}$$ $H_n(P)$をエントロピー(entropy)と呼ぶ．

確率Pで発生しているデータ系列を確率Qに基づく符号化した場合の平均符号長

$$\begin{array}{rcl}{\displaystyle {\log }_{2}P(x^n)-{\log }_{2}P(x^n)}& =& {\displaystyle {\log }_{2}Q(x^n)-{\log }_{2}Q(x^n)}\\ {\displaystyle -{\log }_{2}Q(x^n)}& =& -{\log }_{2}P(x^n)+{\log }_{2}P(x^n)-{\log }_{2}Q(x^n)\\ & =& {\displaystyle -{\log }_{2}P(x^n)+{\log }_2\frac{P(x^n)}{Q(x^n)}}\\ {\displaystyle E_P^n[-{\log }_{2}Q(X^n)]}& =& {\displaystyle E_P^n[-{\log }_{2}P(X^n)]+E_P^n[{\log }_2\frac{P(X^n)}{Q(X^n)}]}\\ & =& {\displaystyle H_n(P)+D_n(P\parallel Q)}\\ D_n(P\parallel Q)& \stackrel{\mathrm{def}}{=}& E_P^n[{\log }_2\frac{P(X^n)}{Q(X^n)}]\end{array}$$ $D_n(P\parallel Q)$をKullback-Leiblerダイバージェンス(Kullback-Leibler divergence)と呼ぶ．

χ^n上の確率質量凾数P(x^n)から求める符号長(符号長の期待値, 平均符号長)

${\chi }^n$上の確率質量凾数$P(x^n)$から求める符号長

$$\begin{array}{rl}I(x^n)=\lceil -{\log }_{2}P(x^n)\rceil & \dots {\chi }^n\mathrm{上}\mathrm{の}\mathrm{確}\mathrm{率}\mathrm{質}\mathrm{量}\mathrm{凾}\mathrm{数}P(x^n)\mathrm{か}\mathrm{ら}\mathrm{求}\mathrm{め}\mathrm{る}\mathrm{符}\mathrm{号}\mathrm{長}(I:{\chi }^n\to {\mathbb{R}}^{+})\end{array}$$

符号長の期待値

$$\begin{array}{rl}E[\mathcal{l}(x^n)]={\displaystyle \sum _{x^n\in {\chi }^n}\mathcal{l}(x^n)P(x^n)}& \dots \mathrm{符}\mathrm{号}\mathrm{長}\mathrm{の}\mathrm{期}\mathrm{待}\mathrm{値},\mathrm{平}\mathrm{均}\mathrm{符}\mathrm{号}\mathrm{長}(averagecodewordlength)\end{array}$$

例:$\chi =\{0,1\},n=2$

$y_1$	$y_2$	$x^2$ $=y_1{y}_2$	$P(x^2)$	$-{\log }_{2}P(x^2)$ Shannon情報量	$I(x^2)=\lceil -{\log }_{2}P(x^2)\rceil$ ${\chi }^2$上の確率質量凾数$P(x^2)$から求める符号長	$\pi (x^2)$	$\mathcal{l}(x^2)$ $=|\pi (x^2)|$	${\pi }^{\prime }(x^2)$	${\mathcal{l}}^{\prime }(x^2)$ $=|{\pi }^{\prime }(x^2)|$	${\pi }^{″}(x^2)$	${\mathcal{l}}^{″}(x^2)$ $=|{\pi }^{″}(x^2)|$
0	0	00	$\frac{1}{8}$	$-{\log }_2\frac{1}{8}=3$	$\lceil -{\log }_2\frac{1}{8}\rceil =3$	000	3	1	1	00	2
0	1	01	$\frac{1}{8}$	$-{\log }_2\frac{1}{8}=3$	$\lceil -{\log }_2\frac{1}{8}\rceil =3$	001	3	01	2	01	2
1	0	10	$\frac{1}{4}$	$-{\log }_2\frac{1}{4}=2$	$\lceil -{\log }_2\frac{1}{4}\rceil =2$	01	2	001	3	10	2
1	1	11	$\frac{1}{2}$	$-{\log }_2\frac{1}{2}=1$	$\lceil -{\log }_2\frac{1}{2}\rceil =1$	1	1	000	3	11	2

上記例で$\mathcal{l}(x^2)$が$I$と等しい符号化($\pi$)の平均符号長

$$\begin{array}{rcl}{\displaystyle E[\mathcal{l}(x^2)]}& =& {\displaystyle \sum _{x^2\in {\chi }^2}\mathcal{l}(x^2)P(x^2)}\\ & =& {\displaystyle 3\times \frac{1}{8}+3\times \frac{1}{8}+2\times \frac{1}{4}+1\times \frac{1}{2}}\\ & =& {\displaystyle \frac{3+3+4+4}{8}=\frac{14}{8}}\\ & =& {\displaystyle 1+\frac{3}{4}=1.75}\end{array}$$

上記例で${\mathcal{l}}^{\prime }(x^2)$が$I$と等しくない符号化(${\pi }^{\prime }$)の平均符号長

$$\begin{array}{rcl}{\displaystyle E[{\mathcal{l}}^{\prime }(x^2)]}& =& {\displaystyle \sum _{x^2\in {\chi }^2}{\mathcal{l}}^{\prime }(x^2)P(x^2)}\\ & =& {\displaystyle 1\times \frac{1}{8}+2\times \frac{1}{8}+3\times \frac{1}{4}+3\times \frac{1}{2}}\\ & =& {\displaystyle \frac{1+2+6+12}{8}=\frac{21}{8}}\\ & =& {\displaystyle 2+\frac{5}{8}=2.625}\end{array}$$

上記例で$\mathcal{l}(x^n)=2$と常に一定となる符号化(${\pi }^{″}$)の平均符号長

$$\begin{array}{rcl}{\displaystyle E[{\mathcal{l}}^{″}(x^2)]}& =& {\displaystyle \sum _{x^2\in {\chi }^2}{\mathcal{l}}^{″}(x^2)P(x^2)}\\ & =& {\displaystyle 2\times \frac{1}{8}+2\times \frac{1}{8}+2\times \frac{1}{4}+2\times \frac{1}{2}}\\ & =& {\displaystyle 2\times (\frac{1}{8}+\frac{1}{8}+\frac{1}{4}+\frac{1}{2})}\\ & =& {\displaystyle 2\times 1}\\ & =& {\displaystyle 2}\end{array}$$

データ系列・符号化・符号長(語頭属性, 語頭符号, 語頭符号化)

データ系列

$$\begin{array}{rl}y\in \chi & \dots y\mathrm{は}\mathrm{集}\mathrm{合}\chi \mathrm{の}\mathrm{要}\mathrm{素}\\ x^n(=y_1{y}_2\dots y_n)\in {\chi }^n& \dots \mathrm{集}\mathrm{合}\chi \mathrm{の}\mathrm{要}\mathrm{素}\mathrm{を}\mathrm{並}\mathrm{べ}\mathrm{た}\mathrm{長}\mathrm{さ}n\mathrm{の}\mathrm{デ}\mathrm{ー}\mathrm{タ}\mathrm{系}\mathrm{列}{x}^n\\ P(x^n)& \dots {\chi }^n\mathrm{上}\mathrm{の}\mathrm{確}\mathrm{率}\mathrm{質}\mathrm{量}\mathrm{凾}\mathrm{数}(probabilitymassfunction)\\ -{\log }_{2}P(x^n)& \dots Shannon\mathrm{情}\mathrm{報}\mathrm{量}(Shannoninformation)\end{array}$$

符号化・符号長

$$\begin{array}{rl}\{0,1\}\ast & \dots 0\mathrm{と}1\mathrm{の}\mathrm{任}\mathrm{意}\mathrm{長}\mathrm{さ}\mathrm{の}\mathrm{系}\mathrm{列}\mathrm{集}\mathrm{合}\\ \pi :{\chi }^n\to \{0,1\}\ast & \dots \mathrm{符}\mathrm{号}\mathrm{化}(coding)\\ \pi (x^n)& \dots \mathrm{符}\mathrm{号}\mathrm{・}\mathrm{符}\mathrm{号}\mathrm{語}(codeword)\\ |\pi (x^n)|& \dots \mathrm{符}\mathrm{号}\mathrm{・}\mathrm{符}\mathrm{号}\mathrm{語}(\pi (x^n))\mathrm{の}\mathrm{長}\mathrm{さ},\mathrm{符}\mathrm{号}\mathrm{長}(codewordlength)\\ \mathcal{l}(x^n)=|\pi (x^n)|& \dots \mathcal{l}:{\chi }^n\to {\mathbb{R}}^{+}({\mathbb{R}}^{+}\mathrm{は}\mathrm{正}\mathrm{の}\mathrm{実}\mathrm{数})\end{array}$$ 任意の$x_1,x_2\in {\chi }^n$に対して$\pi (x_1),\pi (x_2)$の一方が他方の先頭部分に一致しない性質(語頭属性(prefix property))を持つ符号を語頭符号(prefix code)，語頭符号へ変換する$\pi$を語頭符号化(prefix coding)と呼ぶ．