平均符号長の下限(エントロピー, 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) &\leq& 1&\quad\dotso P(x^n)は確率質量凾数なので総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \displaystyle \sum_{x^n \in \chi^n}2^{-\mathcal{l}(x^n)}&\leq&1&\quad\dotso 2^{-\mathcal{l}(x^n)}=P(x^n)なのでやはり総和は1,\;P(x^n)を劣確率凾数とするケースを考える場合は総和は1以下\\ \end{array}$$ 劣確率凾数は \(P(x)\geq0\) の条件は確率(質量)凾数と同じで，\(\sum P(x) \leq 1\)となる凾数．

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

$$\begin{array}{rcl} E^{n}_{P}\left[\mathcal{l}(X^n)\right]&\geq&H_n(P)&\quad\dotso 符号長の期待値・平均符号長の下限\\ H_n(P)&\overset{\mathrm{def}}{=}& E^{n}_{P}\left[-\log_2{P(X^n)}\right]&\quad\dotso 確率P(x^n)に基づく符号化の長さであることが条件\,\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^{n}_{P}\left[-\log_2{Q(X^n)}\right] &=&\displaystyle E^{n}_{P}\left[-\log_2{P(X^n)}\right]+E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ &=&\displaystyle H_n(P)+D_n(P\parallel Q)\\ D_n(P\parallel Q)&\overset{\mathrm{def}}{=}&E^{n}_{P}\left[\log_2{\frac{P(X^n)}{Q(X^n)}}\right]\\ \end{array}$$ \(D_n(P\parallel Q)\)をKullback-Leiblerダイバージェンス(Kullback-Leibler divergence)と呼ぶ．