2015-02-10

情報理論の復習と「情報理論基礎と広がり」の演習問題メモ

情報理論のメモ

http://www.t.kyoto-u.ac.jp/syllabus-s/?mode=subject&lang=ja&year=2014&b=6&c=91200
　主に授業の内容と上記参考文献の演習問題の回答についてのメモ。正しいかどうかはわからないので自己責任で。走り書きなので細かい定義はすべてかっ飛ばしている、だから記事もあんまり長くないし内容もない感じ。講義でのメモは灰色枠。

参考文献

情報理論基礎と広がり: Thomas M.Cover, Joy A.Thomas, 山本博資, 古賀弘樹, 有村光晴, 岩本貢

第2章　エントロピー，相対エントロピー，相互情報量

${ H(X) \geq 0 \\ H(X,Y) = H(X) + H(Y|X) \\ D(p||q) = \sum p(x) \log \frac{p(x)}{q(x)} \\ I(X;Y) = D(p(x,y)||p(x)p(y) ) }$

${ H(X_1,\dots,X_n) = \sum H(X_i|X_{i-1},\dots,X_1) \\ I(X;Y|Z) = H(X|Z) - H(Y|X,Z) = E(\log \frac{p(X,Y|Z)}{p(X|Z)p(Y|Z) } ) \\ D(p||q) \geq 0 \\ H(X|Y) \leq H(X) }$

${ 相対エントロピー \\ マルコフ連鎖 \\ データ処理不等式 \\ ファノ不等式 (1 + P_e \log |\chi| \geq H(X|\hat{X})) \\ }$

相対エントロピー*1

定義

エントロピー

${ H(X) = - \sum p(x) \log p(x) = E \log \frac{1}{p(x)} ( > 0 ) \\ H(X,Y) = - \sum p(x,y) \log p(x,y) }$

条件付きエントロピー

${ H(X|Y) = \sum p(y) \log p(X|Y = y) \\ = \sum p(y) \sum p(x|y) \log p(x|y) \\ = \sum \sum p(x,y) \log p(x|y) }$

そして {X,Y} のエントロピーは {X} のエントロピーと {X} が決まっている時の {Y} のエントロピーの和と考えると
{H(X,Y) = H(X) + H(Y|X)}
は納得の行く等式。成り立つ理由は
${ -H(X,Y) \\ = \sum \sum p(x,y) \log (p(y|x)p(x) ) = \sum_x \sum_y p(x,y) \log p(y|x) - \sum_x \sum_y p(x,y) \log p(x) \\ = -H(Y|X) - H(X) }$
だから。両辺に条件をつけた
{
H(X,Y|Z) = -H(Y|X,Z) + H(X|Z)
}
も言える。

相互情報量(カルバックライブラー距離)

${ I(X;Y) = \sum p(x,y) \log \frac{p(x,y) }{p(x) p(y)} = D(p(x,y)||p(x)p(y)) }$
と記述する。明らかに0なのは二変数が独立しているとき。式を展開して
{
I(X;Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y)
}
が言える。

チェイン則

${ H(X_1,\dots,X_n) = \sum H(X_i | X_{i-1},\dots,X_1) }$
これは全体のばらつきは ${X_1}$ のばらつき、 ${X_1}$ のばらつきを求めたから ${X_1}$ を決め打ちしたときの ${X_2}$ のばらつき、...と足していくということだと思う。そして直感にあっている。

Jensen's inequarity

（要約すると） ${ E f(X) \geq f(EX)}$ が下に凸な関数で成り立つ。
証明：
　参考文献に記載あり。それ以外では関数を平均まわりでテイラー展開して二次以降の項を無視、そのあと両辺の平均をとれば式を示せるはず。この不等式は相互情報量が0以上であることの証明に利用するために必要。

データ処理不等式

　データは加工すればするほど、もとのデータを予測しにくくなることを数式で示す。マルコフ連鎖に付いては省略、Wikipedia参照*2。 {X -> Y -> Z} などと書く。
　が成り立つとき
　 ${I(X;Y) \geq I(X;Z) }$
が成り立ち、これをデータ処理不等式と呼ぶ。
証明：
{　I(X;Y,Z) = I(X;Y|Z) + I(X;Z) = I(X;Z|Y) + I(X;Y) }
がなりたつ、だけど今マルコフ連鎖であるという仮定があるから {I(X;Z|Y)=0} 、さらに相互情報量は非負の値をとるからデータ処理不等式が成り立つ。

ファノの不等式

${P_e := Pr(\hat{X} \neq X)}$
${\hat{X} = }$ 通信路を経過して得られた {Y} から {X} を推測した値
としたときに、不等式

${ H(P_e) + P_e \log | \chi | \geq H(X|\hat{X}) \geq H(X|Y) }$
であり、ここから
${ P_e \geq \frac{H(X|Y) - 1}{\log (| \chi | - 1)} }$
が導ける。
理由：

エントロピーの最大値は1
ある記号に対して誤りが発生するパターンは ${ |\chi| - 1}$ 通り

証明：
~~後ほど追記予定。~~
確率変数 {E} を新たに定義する、それは
${ E = \left\{ \begin{array}{l} 0　if　\hat{E} = E \\ 1　if　\hat{E} \neq E \end{array} \right. }$
となる確率変数でここで推測したときの入力とその推測が正しいか（を示す確率変数）のばらつき具合をしめす条件つきエントロピーを考える。
${ H(E,X | \hat{X}) \\ = H(X | \hat{X} ) + H(E| X, \hat{X}) \\ = H(E | \hat{X} ) + H(X |E,\hat{X} ) \\ \leq H(P_e) + P_e \log |\chi - 1| }$
と二通りに展開できる。ここで「推測値」と「実際の値」が条件についていたらそれが外れているかどうかがわかるから ${H(E| X, \hat{X})=0}$ である。最後の不等式は条件付きエントロピーは条件なしより大きくなることはないこと、エントロピーを最大にするのは一様分布であり誤りかたは ${|\chi - 1|}$ 個あることから分かる。

相互情報量は0以上

証明：
${ -D(p||q) = - \sum_x p_x \log \frac{p_x}{q_x} \leq \log \sum_x p_x \frac{p_x}{q_x} \leq \log 1 = 0 }$

演習問題2.1

(a)
${ \displaystyle H(X) = -\sum_{n=0}^{\infty} pq^{n-1}log(pq^{n-1}) \\ = - ( \sum_{n = 0}^{\infty} pq^nlogp + \sum_{n = 0}^{\infty} npq^n logq )\\ = \frac{-plogp}{1 - q} - \frac{pqlogq}{p^2}\\ = -\frac{ plogp + qlogq }{p}\\ = \frac{H(p)}{p} bit\\ }$
(b)同じ。

演習問題2.2

${ \displaystyle y = f(x) とする。\\ \sum_{x\in\{x:f(x) = y\}}^{} p(x)\\ }$

の式を考える、もしもxとyが一対一に対応していれば、y=f(x)となるxはyを決めれば一つに決まる。また、
${ \displaystyle \sum_{x\in\{x:f(x) = y\}}^{} p(x)log p(x)\\ = \sum_{x\in\{x:f(x) = y\}}^{} p(x)log p(y) \\ = p(y) log p(y)\\ }$
である。はじめの不等式はlogが増加関数であることから、二つ目の等式は
$\sum_{x\in\{x:f(x) = y\}}^{} p(x)$ を代入すれば得られる。
以上の式を用いると、Xのエントロピーについて、
${ \displaystyle H(X) \\ = - \sum_{x} p(x)log p(x) : エントロピーの定義式\\ = - \sum_{y} \sum_{x\in\{x:f(x) = y\}}^{} p(x)log p(x) :\\サメンションの部分はすべてのxについての和だから、\\それをy=f(x)となるxについての和、すべてのyについての和、と分割する\\ \geq - \sum_{y} p(y)log p(y) :上の不等式を代入\\ = H(Y)\\ }$
となる。この不等式の等号が成り立つのは、

${ \displaystyle \sum_{x\in\{x:f(x) = y\}}^{} p(x)log p(x)\\ = \sum_{x\in\{x:f(x) = y\}}^{} p(x)log p(y) \\ = p(y) log p(y)\\ }$

で等号が成り立つときのみで、それはxとyが一対一に対応しているとき。よって解答は(a) H(X) = H(Y) (b) H(X) => H(Y) となる。

演習問題2.3

${ \displaystyle H(p) = - \sum_{k=0}^{N} p_k log p_k }$
上の式を最小にする時、
${ \displaystyle - p_k log p_k >= 0 }$
が成り立つ、この式の最小値はp=0,1の時の0である。
${ \displaystyle p_1 = 1, p_2 = ... = p_N = 0 の時、\\ H( p ) = 0 }$
となる。

演習問題2.4

${ \displaystyle (a) H(X,g(X)) = H(X) + H(g(X)|X) - チェイン則より\\ (b) H(g(X)|X) = 0 - Xが決まればg(X)の値はただ一つに決まる\\ (c) チェイン則より成り立つ\\ (d) gが1対1対応の写像とは限らないため }$

演習問題2.5

H(Y|X)=0ということは、Xが決まると曖昧さが全くなくYが決まるということ、直感的には。式で書いて証明すると、
${ \displaystyle - H(Y|X) \\ = \sum_{x} p(x) \sum_{y} p(y|x) lg p(y|x) \\ }$
ここでもしも、YがXの関数でないならあるx'が存在して、それに対応するy’、y''が存在する。このようなx',y',y''がある時、上の式が0にならないことを示せば背理法で問が正しいことを示せる。
ここで、上の式のサメンション（Σ）について、特にx'に注目すると
${ \displaystyle (p(y'|x')lg p(y'|x') + p(y''|x')lg p(y''|x')) }$
という項とp(x')との積の項がある。p(x')>0と仮定しているのでこの式が0でないと、H(Y|X)=0ではない。そして、p(y'|x')>0,p(y''|x')>0と仮定しているので成り立たない。

演習問題2.06

${ \displaystyle (a) I(X,Y|Z) < I(X;Y) \\ (b) I(X,Y|Z) > I(X;Y) }$
となるような例を作る。
(a) Zの条件がついたら情報量が下がるのだからZの値とX、Yの値に関連があるはず。よって必ずY＝Z、Y＝Xとなる時、Zが分かっている条件だと何もあたらしい情報がなく
${ I(X,Y|Z) = 0 \\ I(X;Y) = 1 }$
となる。

(b)こんどはZが分かっている時の方が相互情報量がおおい、つまりZがXとYの情報の”共通部分”に関する情報をもっている。
簡単にするためにXとYは全く独立とすれば、 {I(X;Y) = 0} .
そして　Z＝X * Y とすればいい。

演習問題2.11

a

${ \displaystyle ρ \\ = \frac{H(X_1) - H(X_2|X_1)}{H(X_1)} }$
${X_1}$ と ${X_2}$ は同一の文応だからエントロピーも同じであり
${ \displaystyle = \frac{H(X_2) - H(X_2|X_1)}{H(X_1)} \\ = \frac{I(X_1;X_2)}{H(X_1)} }$

b

${ \displaystyle 0 \leq H(X_1|X_2) \leq H(X_2) = H(X_1) }$
だから
${ \displaystyle 1 - \frac{H(X_2|X_1)}{H(X_1)} }$
が0未満になることはない.

c

aの式より二変数の相互情報量が0の時。
それは二変数が同一分布で独立な時。

d

aの式より $\frac{I(X_1;X_2)}{H(X_1)}$ が0の時。それは二変数が等しいとき、もっと一般的には二変数が一対一対応しているとき。

演習問題2.14

a　H ( Z | X ) = H ( Y | X )

${ \displaystyle A_b = \sum_{k=0}^{N} a_k }$

Z = X + Yなのだから、
{
p(Z = z | X = x) = p(Y = z - x | X = x)
}
が成り立つ。このことから、
${ H(Z | X) \\ = \sum p(x) H( Z | X = x )\\ = \sum \sum p(x) \{ - p( Z = z | X = x ) \log p( Z = z | X = x ) \} \\ = \sum \sum p(x) \{ - p(Y = z - x | X = x) \log p(Y = z - x | X = x) \} \\ = \sum p(x) H(Y|X=x) \\ = H(Y|X) }$

　x、Yが完全に独立な確率変数ならば、 { H(Y) = H(Y|X) } である。この場合、
${ H(Z) \geq H(Z|X) = H(Y|X) = H(Y) }$
となる。

b

{X} と {Y} の和が常に限られた値しかとらないにもかかわらず、 {X} と {Y} の値が定まらないような分布にする。 {X} の分布と {-Y} の分布が同じになるようにすればいい。

c

　 {Z} は {X} と {Y} の値に依存した確率変数だから、

${H(Z) \leq H(X) + H(Y)}$

は明らか。もっと詳しく記述すると

${H(Z) \leq H(X,Y) ＝ H(X) + H(Y|X) \leq H(X) + H(Y)}$

となる。すべての部分で等号が成り立つためには
「XとYは完全に独立」
「ZはXとYの関数」
である必要がある。

演習問題2.15

${ \displaystyle I(X_1;X_2) }$

演習問題2.29

a

${ \displaystyle H(X,Y|Z) = H(X|Z) + H(Y|Z,X) \geq H(X|Z) }$

b

${ I(X,Y;Z) = I(X;Z) + I(Y;Z|X) \geq I(X;Z) }$

c

${ H(X,Y,Z) - H(X,Y) \\ = H(Z|X,Y) \\ = H(Z|X) - I(Y;Z|X) \\ \geq H(Z|X) \\ = H(X,Z) - H(X) }$

d

{
I(X,Y;Z) = I(Y;Z|X) + I(X;Z) = I(Z;Y|X) + I(X;Z)
}
であり、
{
I(X,Y;Z) = I(X;Z|Y) + I(Z;Y)
}
でここから
{
I(Z;Y|X) + I(X;Z) = I(X;Z|Y) + I(Z;Y)
}
よって
{
I(X;Z|Y) = I(Z;Y|X) - I(Z;Y) + I(X;Z)
}
となる。

演習問題2.33

　ラグランジュ未定乗数法*3 *4を用いてファノ不等式を証明する、もしくは式変形？

最大化すべき目的関数は
${ H(\vec{p}) \\ = - \sum_i p_i \log p_i \\ = - \sum_i \frac{p_i}{P_e}{P_e} \log \frac{p_i}{P_e} P_e \\ = - {P_e} \sum_i \frac{p_i}{P_e} \log \frac{p_i}{P_e} - {P_e} \log {P_e} \\ = - {P_e} \sum_i \frac{p_i}{P_e} \log \frac{p_i}{P_e} + (- {P_e} \log {P_e} - (1 - P_e) \log (1 - P_e)) + (1 - P_e) \log (1 - P_e) \\ = - {P_e} \sum_i \frac{p_i}{P_e} \log \frac{p_i}{P_e} + H(P_e) + p_1 \log p_1 \\ \leq - {P_e} \sum_{2 \leq i \leq m} \frac{p_i}{P_e} \log \frac{p_i}{P_e} + 1 }$
とかける。だから ${H(\vec{p}) }$ を最大化するためには ${- {P_e} \sum_{2 \leq i \leq m} \frac{p_i}{P_e} \log \frac{p_i}{P_e}}$ が最大になる必要がある。そして離散の値をとる確率変数のエントロピーは一様分布のときに最大となるのだから、

${ H(\vec{p}) \leq - {P_e} \sum_{2 \leq i \leq m} \frac{p_i}{P_e} \log \frac{p_i}{P_e} + 1 \leq {P_e} \log (m - 1) + 1 }$

とできる。よって

${ P_e \geq \frac{H(X) - 1}{\log (m - 1)} }$
　ラグランジュ未定乗数法なら
${ P_e = 1 - p_1 }$
という条件が与えられているのでこれを等号の束縛条件とみて
${ P_e + p_1 - 1 = 0 }$
と書き換える。さらに
${ \sum p_i - 1 = 0 }$
も束縛条件。 ${H(\vec{p})}$ は最大のところで極値をもつと考えて
${ H(\vec{p}) - \lambda_1 (P_e + p_1 - 1) - \lambda_2 (\sum p_i - 1) }$
にたいして偏微分をとる、というかこっちの方がいい。

第3章　AEP

${ 　典型集合: 2^{-n(H(X) + \epsilon) \leq p(x_1,\dots,x_n) \leq 2^{-n(H(X) - \epsilon) }} \\ E( \frac{1}{n} length(X^n)) \leq H(X) + \epsilon }$

　大数の法則のエントロピー版のイメージがある。また典型集合という概念を導入する。たとえ0が1より出やすくても「00000」よりも「00100」「01000」「00001」のような列の方がよく出現しそう...、そんな列の集まり。

漸近等分割性(AEP)

もしも確率変数 ${X_i　(i = 1,¥\dots,n)}$ が独立で同一な分布 {p(X)} に従うならば
${ - \frac{1}{n} \log p(X_1,\dots,X_n) -> H(X) in probability. }$
である。 {in probability} は確率収束*5の意味。

典型集合(typical set)

　典型集合 ${A_{\epsilon}^{(n)}}$ を以下のように定義。
${ 2^{-n(H(X) + \epsilon)} \leq p(x_1,\dots,x_n) \leq 2^{-n(H(X) - \epsilon)} }$
となるような列 ${(x_1,\dots,x_n)}$ の集合。

典型集合が満たす性質

　むしろ満たすようにうまく定義したように感じる。

*1 \\ = max_{p(x)} (H(Y) - \sum_x p(x) H(Y|X = x)) \\ = max_{p(x)} H(Y) - H(\alpha) }"/>
特に、について

だから
${ H(Y) = H( \alpha ) + \alpha H( \pi ) }$
と考えられる。実際、
${ H(Y) = H( ( 1 - \pi )( 1 - \alpha ), \alpha ,\pi ( 1 - \alpha ) ) = H( \alpha ) + \alpha H( \pi ) }$
と書ける。以上から二元対称通信路の通信路容量は
${ C \\ = max_{p(x)} H(Y) - H(\alpha) \\ = max_{p(x)} \{H(\alpha) + (1 - \alpha) \alpha H(\pi)\} - H(\alpha) \\ = 1 - \alpha }$

対称通信路

　二元対称通信路*21の一般化。通信路行列によって {p(Y|X)} の条件付き分布が与えられているとすればその行列の第 {i} 行は入力 ${X_i}$ を条件付けしたときの ${Y_1,\dots,Y_j}$ の分布でありその行ベクトルを ${\vec{r_i}}$ と記述する。

${ I(X;Y) = H(Y) - H(Y|X) \\ 　 = H(Y) - \sum p(x_i)H(Y|X=x_i) \\ = H(Y) - \sum p(x_i)H(\vec{r_i}) \\ = H(Y) - H(\vec{r}) \\ \geq \log |Yの要素数| - - H(\vec{r}) }$

とできる。等号が成り立つのは出力が一様分布の時（そもそも、離散ならばエントロピーを最大にする分布は一様分布、連続ならばガウス分布）。そして出力を一様分布にするような入力の分布を求めればいい。対称通信路だからそれも同様に一様分布だと分かる。

**通信路符号化定理(the chanel coding theorem)*22
追記予定。

演習問題7.01

a

　今、 {X} が通信路をとおり {Y} となってそれに対して変換 ${G(y)= \hat{Y}}$ としたのだからこの一連の変換 ${X -> Y -> \hat{Y}}$ に対してデータ処理不等式

${ I(X;Y) \geq I(X;\hat{Y})}$

が言える。通信路容量の定義式に当てはめると

${ max_{p(x)} I(X;Y) \geq max_{p(x)} I(X;\hat{Y}) }$

となるので、通信路容量は改善しない。

b

${ I(X;Y) \geq I(X;\hat{Y})}$
で等号がなり縦倍いのだから、 ${Y -> \hat{Y}}$ が1対1の変換であればいい。

演習問題7.02

{ Y = X + Z } であり ${ Z \in \{0,a\}}$ 、 ${X \in \{0,1\}}$ だから ${Y \in \{0,a,1,1+a\}}$ 。なので {Y} の要素の数によって場合分けする。

　 {Z} によって入力にノイズが加わることはないから、 ${ C = max_{p(x)} I(X;Y) = max_{p(x)} H(X) = 1}$ 。

　 {Z} によって入力にノイズが加わることで {Y} の要素が増える。
　 ${ C = max_{p(x)} I(X;Y) = max_{x}max_{y} p(x,y) \log \frac{p(x,y)}{p(x)p(y)}}$ を計算。

　 {Z} によって入力にノイズが加わっても {1 + a} は入力でないと分かるから、 ${ C = max_{p(x)} I(X;Y) = max_{p(x)} H(X) = 1}$ 。

第8章　微分 エントロピー

微分 エントロピーの定義

${ h(X) = - \int_S f(x) \log f(x) dx }$
を連続な密度関数をもつ確率変数 {X} に対して定義。
省略。

第9章　ガウス型通信路*23

省略。

第4章　確率過程のエントロピーレート

マルコフ連鎖

　説明略。信州大学の資料*10があったのでそれを参考資料としてメモしておく。要は現在の状態になるための遷移確率は直前の状態からのみ決定して、それ以前の過去の遷移（履歴）は全く関係しない。

time invariant

　Wikipedia *11には難しいことが書いてあるけれど、現在の文脈においては”添字に関係しない”ということで、ただそれだけ。つまり ${ Pr(X_4 = 1 | X_3 = 0) = Pr(X_2 = 1 | X_1 = 0)}$ 。

　この章の内容はマルコフ連鎖のエントロピーレートの求め方など。めもは省略、だけど大切な内容。

演習問題4.03

条件がついたらもちろんエントロピーは下がりうる。

演習問題4.04

${ H(X_n|X_1) \leq H(X_n|X_2,X_1) = H(X_n|X_2) = H(X_{n-1}|X_1) }$

演習問題4.09

　データ処理不等式から ${I(X_0;X_{n-1}) \geq I(X_0;X_n)}$ が言える。この式の両辺を変形すると問題の式が導ける。
( ${ I(X_0;X_n) = H(X_0) - H(X_0|X_n) = H(X_n) - H(X_n|X_0)}$ の展開。)
要は元になるデータを加工しまくるほど、元データが何だったかが分かりにくくなる。

演習問題4.11

a

真。なぜならば
${ H(X_n | X_0) = H(X_n,X_0) - H(X_0) = H(X_0,X_{-n}) - H(X_0) \\ = H(X_{-n},X_0) - H(X_0) = H(X_{-n} | X_0) }$

b

　偽。データ処理不等式の考えからすると元の ${X_0}$ から離れるほど「当てにくい」ことから真っぽく見える。だけど問題に「マルコフ連鎖である必要は無い(not necessarily Markov)」ところに注目。マルコフ連鎖は直前の状態にのみ依存して現在の状態の確率が決まる。ここを「 ${X_0}$ の状態に依存して現在の状態が決まる」としたとき、この不等式はいつも真とは限らない、と言えるようにしたい。
　いつも真では無いことを言えばいいのだからnをある定数kとする。すると「確率変数の値はk個前の状態に依存して"一意に"決まる」ような確率過程はこの不等式を満たさないと分かる。
( ${X_k}$ は ${X_0}$ によって一意に決定するのだから ${H(X_n|X_0) = 0}$ )

c

　真。
${ H(X_n | X_{1,\dots,n-1},X_{n+1}) = H(X_{n+1} | X_{1+1,\dots,n-1 + 1},X_{n+1+1}) = H(X_{n+1} | X_{2,\dots,n},X_{n+2}) }$
ここで条件が増えればエントロピーはさが（りう）ることを示した不等式を用いれば、
${ H(X_n | X_{2,\dots,n},X_{n+2}) \leq H(X_{n+1} | X_{1,\dots,n},X_{n+2}) }$
このことからnが増加したのに式の値が増えていないことが言える。

d

　真。
${ H(X_n | X_{1,\dots,n-1},X_{n+1,\dots,2n}) = H(X_{n+1} | X_{1+1,\dots,n-1 + 1},X_{n+1+1,\dots,2n+1}) = X_{2,\dots,n},X_{n+2,\dots,2n+1}) \\ \leq X_{1,\dots,n},X_{n+1,\dots,2n+1}) }$

演習問題4.14

　エントロピーレートの式をXについて書き下すと
${ lim \frac{H(X_0,\dots,X_n)}{n} }$
なのだからエントロピーレートの大小関係は分母の ${H(X_0,\dots,X_n)}$ の大小関係が言えればいい。
ここでXを関数によって写像した先がYなのだから、Xが決まればYの値は有限個の候補しかない。よってどんな ${X_i}$ に対しても ${H(Y) \leq H(X)}$ と言っていい。Zについても ${H(Z_i) \leq H(Z_i,Z_{i+1})}$ 。このことから
${ (Yのエントロピーレート) \leq (Xのエントロピーレート) \\ (Zのエントロピーレート) \leq (Xのエントロピーレート) }$

演習問題4.15

　与式を条件付きエントロピーのチェイン則に従って展開する。*12より成り立つ。

演習問題4.18

a

0? Xは二種類のコインのうちどちらを選んだか。Yはそれを投げる試行を二回行ったこととできまる。
相互情報量の定義の式に当てはめると

${ I(X;Y) = \sum_{y_1} \sum_{y_2} p(y_1,y_2|x) \log \frac{p(y_1,y_2|x)}{p(y_1|x)p(y_2|x)} }$

この式を見ると、そもそもコインを選ぶことによってコインの表が出る確率が変わるけれどそのコインを条件付けされたら ${\frac{p(y_1,y_2|x)}{p(y_1|x)p(y_2|x)} = 1}$ になるので0.だろう。

b

${ I(X;Y_1,Y_2) \\ = I(Y_1,Y_2;X) \\ = H(Y_1,Y_2) - H(Y_1,Y_2 | X) \\ = H(Y_1,Y_2) - H(Y_1 | X) - H(Y_2|X) \\ }$
コイントスの結果とコイントスの順番は関係ないはずだから ${H(Y_1 | X) = H(Y_2|X)}$ とする。以上から
${ 与式 = H(Y_1,Y_2) - 2H(p) }$

c

未回答

演習問題4.32

直感的には { k = n + 1} 。なぜなら {0} から {n} だけ離れているから。

${ H(X_{-n}|X_1,X_0) \\ = H(X_{-n},X_1,X_0) - H(X_1,X_0) \\ = H(X_1,X_0,X_{-n}) - H(X_1,X_0) \\ = H(X_1|X_0,X_{-n}) + H(X_0,X_{-n}) - H(X_1|X_0) - H(X_0) \\ = H(X_1|X_0,X_{-n}) + H(X_0|X_{-n}) + H(X_{-n})- H(X_1|X_0) - H(X_0) \\ = H(X_1|X_0) + H(X_n|X_0) + H(X_{-n})- H(X_1|X_0) - H(X_0) \\ = H(X_n|X_0) + H(X_0) - H(X_0) \\ = H(X_n|X_0) \\ = H(X_{n+1}|X_1) \\ = H(X_{n+1}|X_1,X_0) \\ }$

演習問題4.33

~~未回答。~~
${ I(X_a,X_b) = H(X_a) - H(X_a|X_b) = H(X_b) - H(X_b|X_a) \\ -> I(X_a,X_b) - H(X_a) = - H(X_a|X_b) }$
を踏まえて与式の両辺から ${H(X_1),H(X_2)}$ を引くと
${ I(X_1;X_3) - H(X_1) + I(X_2;X_4) - H(X_2) \leq I(X_1;X_4) - H(X_1) + I(X_2;X_3) - H(X_2) -> - H(X_1|X_3) - H(X_2|X_4) \leq - H(X_1|X_4) - H(X_2|X_3) \\ -> H(X_2|X_3) - H(X_1|X_3) + H(X_1|X_4) - H(X_2|X_4) \leq 0 }$
を示せばいい。
${ H(X_2|X_3) - H(X_1|X_3) + H(X_1|X_4) - H(X_2|X_4) \\ = H(X_2,X_3) - H(X_1,X_3) + H(X_1,X_4) - H(X_2,X_4) \\ = ..? }$

追記:
いろいろいじった結果
${ ..? \\ = -I(X_2,X_3 |X_1,X_4) \leq 0 }$
になる、かも。

第5章　データ圧縮

符号の種類

${　瞬時符号 \subseteq 一意的復号可能符号 \subseteq 正則符号 \subseteq 符号全体}$

正則符号

　 {non-singular code} *13より引用すると、

A code is non-singular if each source symbol is mapped to a different non-empty bit string, i.e. the mapping from source symbols to bit strings is injective.

　要は情報源の記号それぞれに、別々の符号化が与えられているとき。

一意的復号可能符号

　符号の列全体を受け取って、それをもとの記号列にデコードするときにただ一通りにしかデコードできないような符号。

瞬時符号*14

　符号の列を先頭から読み取っていきながら、現在までに読み取っている列がなんらかの符号にマッチしているか調べてマッチしたらその場で符号を決めてしまってもいいような符号。

任意の符号語が他のいかなる符号語の接頭部にもなっていないという属性*15

という性質が必ず必要。

ハフマン符号

ハフマン符号更生法 - Google 検索

クラフト不等式とマクミラン不等式

　証明は英語版のWikipediaに記述あり、そしてそれは参考文献に記載されたものと全く同じもの。

Kraft's inequality - Wikipedia, the free encyclopedia
- Kraft, Leon G. (1949), A device for quantizing, grouping, and coding amplitude modulated pulses, Cambridge, MA: MS Thesis, Electrical Engineering Department, Massachusetts Institute of Technology.
- McMillan, Brockway (1956), "Two inequalities implied by unique decipherability", IEEE Trans. Information Theory 2 (4): 115–116, doi:10.1109/TIT.1956.1056818

クラフト不等式

${ \sum_i D^{-l_i} \leq 1 \\ \\ D := 符号アルファベット数 \\ l_i := 情報源記号iに対する符号の長さ \\ }$
を瞬時符号は満たす。
証明：上記英語Wikipwdia参照。

マクミラン不等式

${ \sum_i D^{-l_i} \leq 1 \\ \\ D := 符号アルファベット数 \\ l_i := 情報源記号iに対する符号の長さ \\ }$
を一意的復号可能符号は満たす。
証明：上記英語Wikipwdia参照。参考文献の定理5.5.1。

最適化の下限

　どんな最適（一情報源記号あたりの平均符号長を最短にした）化を行ったとしても、その結果得られる符号の長さは
${ H(X) \leq E(L) \leq H(X) + 1 }$
を満たす。

式の導出：
以下の最適化問題を定義。
${ 　目的関数:　min \sum_i p_i l_i \\ 　制約条件:　\sum_i D^{-l_i} - 1\leq 0　\\ }$

この時、
${ \frac{d}{d l_i} ( \sum_i p_i l_i + \lambda (\sum_i D^{-l_i} - 1) ) = 0 }$
となるような ${D^{-l_i}}$ を求めると ${D^{-l_i} = \frac{p_i}{\lambda \log D} }$ であり、このとき制約条件が有効制約となるためには ${\lambda = \frac{1}{D^{-l_i}}}$ である。よって ${p_i = D^{-l_i}}$ と求められる。ここからもっとも短い場合で ${ l_i = - log_D p_i}$ となることが分かる。

演習問題5.04

a

　略。もっとも確率の低い葉を二つ選んでまとめる。そのまとめたものを「二つの葉の確率の和」をそのまとめたものの出現確率として一つの葉にする。以上の繰り返し。木の構造は一通りだけど、0,1の付け方は二通りある。

b

略。3 + 2n 個の葉をもつ木だからダミーの要素を加える必要もない。

演習問題5.05

　一つ目の分布のシンボルをハフマン符号化するとその平均符号長は ${\frac{12}{5}}$ 。

ハフマン符号（ハフマンふごう、Huffman coding）とは、1952年にデビット・ハフマン（英語版）によって開発された符号である。コンパクト符号やエントロピー符号の一つ。*16

コンパクト符号（コンパクトふごう）とは、一意に復号可能な符号のうち、同じ符号アルファベットを用いる他の任意の符号よりも、平均符号長が大きくない符号のこと。*17

二つ目の符号をハフマン符号化して平均符号長をもとめると ${\frac{12}{5}}$ 。ハフマン符号はコンパクト符号だからこの符号長を下回る平均符号長をもつ符号は無い。

演習問題5.06

a

　○。三要素でハフマン符号化したら同じになる。

b

　×。符号長1の葉が既に無い。

c

　×。符号長1の葉が既に無い。

演習問題5.09

　符号長は常に自然数をとるのに、エントロピーは連続な関数だから自然数の値をとるとは限らない。だからエントロピー関数の値が自然数にならないような確率分布を与えればよいのだから例えば { Pr(X = x) = 0.1} のような記号が含まれる符号を作る。

演習問題5.12

a

　略。

b

　すべて平均符号長が2になる。

c

　すべての符号の確率について ${ \log \frac{1}{p} }$ を計算する、その値とハフマン符号化した結果の符号長をくらべると ${ \log \frac{1}{p} }$ のほうが小さい部分が出てくる。ことが分かる。(ただしハフマンはコンパクト符号だからこの符号長を下回る平均符号長をもつ符号は無い、だから平均したらハフマンのほうが短い。)

※シャノン符号化

符号化の原理
圧縮したいデータに出現する記号の個数を求め、その個数で記号をソートする。
ソートしたデータを、なるべく総数が等しくなるようなところで二分割する。分割した片方のデータに0、もう片方のデータに1を割り当てる。
分割して出来た2つのデータをそれぞれ更に二分割していき、同様に0と1を割り当てていく。
*18

演習問題5.14

　はじめに、確率変数 { X } のとりうる値が6種類しかないから符号アルファベットの種類が三種類のときにはそのままではうまくハフマン符号を作るための木が構成できない。だから一つダミー（出現確率0の葉）を加えればいい。

a

　略。平均符号長 ${\frac{51}{21} }$ 。

b

　ダミーを追加、平均符号長 ${ \frac{34}{21} }$

c

　符号アルファベットの種類が三種類の場合の方が平均符号長が少ないことが以上より分かる。

演習問題5.16

　長いので後ほど追記するかも。

演習問題5.27

　Sardinas–Patterson algorithm*19 などを参照。

演習問題5.28

a

　 ${ \log p_i \leq \lceil \log p_i \rceil \leq \log p_i + 1 }$ であることは天井関数の定義から言える。ここから

${ {p_i}\log \frac{1}{p_i} \leq {p_i}\lceil \log \frac{1}{p_i} \rceil \leq {p_i}\log \frac{1}{p_i} + {p_i} }$

この式を {i} に関して総和をとって

${ \sum_i {p_i}\log \frac{1}{p_i} \leq \sum_i {p_i}\lceil \log \frac{1}{p_i} \rceil \leq \sum_i {p_i}\log \frac{1}{p_i} + \sum_i {p_i} }$

上記の式と問題の与えられた式は等しい。■

b

　略。

第6章　ギャンブルとデータ圧縮

　省略します。

第7章　通信路容量

通信路容量

${C = max_{p(x)} I(X;Y) }$

通信路の入力に関する確率変数を,出力に関する確率変数を[tes:{Y}]と見る。
が通信路を通った結果のに重なりが無かったら常にを見たら入力のが分かる。

の値に関わらず出力の分布が同じならば

${ I(X;Y)\\ = H(Y) - H(Y|X) \\ = H(Y) - \sum_x p(x) H(Y|X = x) \\ = H(Y) - \sum_x p(x) H(p) \\ = H(Y) - H(p) \\ \leq 1 - H(p) }$
と式変形できる。

二元消失通信路*20

　図はリンク先参照。 ${\alpha}$ の確率で入力が消失してしまうとき