χ^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}$$