情報源とは
情報源とは、事象が系列となって次々出てくるもので、ある事象の発生する確率が過去に発生した事象の依存する場合を言います。
例えばアルファベットの場合、情報源は26個の文字（$a,b,c,\cdots,z$）が手持ちとし、時刻 $t$ から｛$\mathrm{hello}\cdots$｝の順に文字が発生したとすると、確率変数 $x$ は次のように表されます。
$$x_t=’\mathrm{h}’ , x_{t+1}=’\mathrm{e}’ , x_{t+2}=’\mathrm{l}’ ,\cdots$$
情報源の確率
一般に発生する文字列が｛$x_{t-s},\cdots,x_{t-1},x_t$｝である確率を、
$$p(x_{t-s}\cdots x_{t-1}x_t)$$
文字列｛$x_{t-s}\cdots x_{t-1}$｝にの後に文字 $x_t$ が発生する確率を、
$$p(x_t|x_{t-s}\cdots x_{t-1})$$
で定義すると、これらの関係は以下で表されます。
$$p(x_{t-s}\cdots x_{t-1}x_t)=p(x_t|x_{t-s}\cdots x_{t-1})p(x_{t-s}\cdots x_{t-1})$$
情報源のエントロピー
情報源のエントロピーとは、情報源から出る文字のエントロピーです。時刻 $t$ に文字 $x_t$ が出る確率は $p(x_t)$ であるため、このエントロピー $H$ は以下で表されます。ここでの和は、文字の種類の和となります。
$$H(x_t)=-\sum_{x_t}p(x_t)\log_2{p(x_t)}$$
情報源は定常的で、文字の発生確率は時間により変化しない前提を置くと以下になります。
$$H(x)=-\sum_xp(x)\log_2{p(x)}$$
２文字の場合
情報源から続いて２文字 $x_1,x_2$ が出る場合のエントロピーは、
$$H(x_1x_2)=-\sum_{x_1,x_2}p(x_1x_2)\log_2{p(x_1x_2)}$$
２文字の間に相関があれば、独単である場合のエントロピーより小さくなります。
$$H(x_1x_2)\le H(x)$$
ｎ文字の場合
一般に $n$ 文字続く場合のエントロピーは、$x^n=x_1x_2\cdots x_n$ と置くと以下で表されます。
$$H(x^n)=-\sum_{x^n}p(x^n)\log_2{p(x^n)}$$
この場合、１文字当たりのエントロピー $H_n$ は、
$$H_n=\frac{H(x^n)}{n}$$
平均エントロピー
情報源の１文字当たりの平均エントロピーは以下で定義されます。
$$H\equiv\lim_{n\to\infty}H_n$$
情報源の冗長度
冗長度とは、同じエントロピーを出す無駄のない（文字間に相関が無い）情報源との差分です。言い換えると、同じ情報を伝えるという前提で、削減可能な文字数の割合です。
例えば、文字の種類が $k$ の場合、相関が無ければ文字は $p_i=1/k$ の確率で発生します。このときのエントロピーは、
$$H_0=-\sum_{i=1}^kp_i\log_2{p_i}=\log_2{k}$$
実際のエントロピーを $H$ とすると、冗長度 $r$ は以下で求められます。
$$r=\frac{H_0-H}{H_0}$$
