エントロピー

$g(t):=t-1-\log t$（$t>0$）は $g'(t)=1-\frac1t$ により $t=1$ で最小値 $0$ をとり、$t\ne1$ では $g(t)>0$ である。すなわち $\log t\le t-1$ で、等号は $t=1$ のときに限る。
$D(p\|q)=\infty$ なら主張は明らかなので、$D(p\|q)< \infty$ とする（とくに $p(x)>0$ なら $q(x)>0$ である）。$S:=\{x\mid p(x)>0\}$ とおくと
$$ -D(p\|q)=\sum_{x\in S}p(x)\log\frac{q(x)}{p(x)}\le\sum_{x\in S}p(x)\Bigl(\frac{q(x)}{p(x)}-1\Bigr)=\sum_{x\in S}q(x)-1\le0 $$
である（項ごとの不等式を足した。両辺の和はどちらも収束する）。よって $D(p\|q)\ge0$ である。等号が成り立てば、上の 2 つの不等号がどちらも等号である。最初の等号から、すべての $x\in S$ で $q(x)/p(x)=1$ である。次の等号から $\sum_{x\in S}q(x)=1$ なので、$S$ の外では $q(x)=0=p(x)$ である。よって $p=q$ である。逆に $p=q$ なら各項が $0$ である。$\square$

$0\le t\le1$ なら $-t\log t\ge0$ で、等号は $t\in\{0,1\}$ のときに限る。よって $H(X)\ge0$ で、等号はすべての $p(x)$ が $0$ か $1$ のとき、すなわちある $x_0$ で $p(x_0)=1$ のときに限る。右の不等式は、$u$ を一様分布として thm-ent-gibbs を使うと
$$ 0\le D(p\|u)=\sum_{x:\,p(x)>0}p(x)\log\bigl(n\,p(x)\bigr)=\log n-H(X) $$
から従い、等号は $p=u$ のときに限る。$\square$

1。 $p(x,y)>0$ なら $p(x)>0$ で $p(x,y)=p(x)\,p(y\mid x)$ なので、$-\log p(x,y)=-\log p(x)-\log p(y\mid x)$ である。両辺に $p(x,y)$ を掛けて $p(x,y)>0$ となる $(x,y)$ について足すと、左辺は $H(X,Y)$、右辺の第 1 項は $\sum_xp(x)(-\log p(x))=H(X)$、第 2 項は $\sum_xp(x)\sum_yp(y\mid x)(-\log p(y\mid x))=H(Y\mid X)$ である。
2。 $p(x,y)>0$ なら $p(x)p(y)>0$ である。$H(X)=-\sum_{x,y}p(x,y)\log p(x)$、$H(Y)=-\sum_{x,y}p(x,y)\log p(y)$ と書き直すと
$$ I(X;Y)=\sum_{(x,y):\,p(x,y)>0}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}=D\bigl(p_{XY}\,\|\,p_X\otimes p_Y\bigr) $$
である。$p_X\otimes p_Y$ は確率分布なので、thm-ent-gibbs により $I(X;Y)\ge0$ で、等号はすべての $(x,y)$ で $p(x,y)=p(x)p(y)$、すなわち $X,Y$ が独立なときに限る。
3。 1 により $H(Y)-H(Y\mid X)=H(X)+H(Y)-H(X,Y)=I(X;Y)\ge0$ である。$Y=f(X)$ とすると $(X,f(X))$ の値は $X$ の値で決まり単射に対応するので $H(X,f(X))=H(X)$ であり、1 を $X$ と $f(X)$ の順を入れ替えて使うと $H(X)=H(f(X))+H(X\mid f(X))\ge H(f(X))$ である。$\square$

$\prod_iq_i^{k_i}=\exp\bigl(\sum_ik_i\log q_i\bigr)=\exp\bigl(n\sum_iq_i\log q_i\bigr)=e^{-nH(q)}$ である（$k_i=0$ の因子は $q_i^0=1$）。
上からの評価。 多項定理により
$$ 1=(q_1+\dots+q_m)^n=\sum_{k'}\binom{n}{k'_1,\dots,k'_m}\prod_iq_i^{k'_i}\ge\binom{n}{k_1,\dots,k_m}e^{-nH(q)} $$
である。和は $k'_1+\dots+k'_m=n$ を満たす $0$ 以上の整数の組 $k'$ 全体にわたり、各項は $0$ 以上である。
下からの評価。 $T(k'):=\binom{n}{k'_1,\dots,k'_m}\prod_iq_i^{k'_i}$ とおく。すべての $k'$ について $T(k')\le T(k)$ であることを示す。ある $i$ で $k_i=0< k'_i$ なら $q_i=0$ なので $T(k')=0$ である。そうでないとき、整数 $a\ge1$、$b\ge0$ について $\frac{a!}{b!}\le a^{a-b}$ が成り立つ（$b\le a$ なら左辺は $a$ 以下の $a-b$ 個の数の積、$b>a$ なら左辺は $a+1$ 以上の $b-a$ 個の数の積の逆数）。これを $a=k_i>0$、$b=k'_i$ に使うと
$$ \frac{T(k')}{T(k)}=\prod_{i:\,k_i>0}\frac{k_i!}{k'_i!}\Bigl(\frac{k_i}n\Bigr)^{k'_i-k_i}\le\prod_{i:\,k_i>0}k_i^{k_i-k'_i}\,k_i^{k'_i-k_i}\,n^{k_i-k'_i}=n^{\sum_i(k_i-k'_i)}=1 $$
である（$k_i=0$ の $i$ では $k'_i=0$ で因子は $1$）。組 $k'$ は $k'_1,\dots,k'_{m-1}\in\{0,\dots,n\}$ で決まるので高々 $(n+1)^{m-1}$ 個あり、上の多項定理の式から $1=\sum_{k'}T(k')\le(n+1)^{m-1}T(k)$ である。$T(k)=\binom{n}{k_1,\dots,k_m}e^{-nH(q)}$ なので下からの評価が従う。$\square$

$Z_i:=-\log p(X_i)$ は互いに独立で同じ分布に従い（独立な確率変数の関数）、有限個の値しかとらないので期待値 $E[Z_i]=H$ と分散 $\sigma^2$ をもつ。$-\frac1n\log p^n(X_1,\dots,X_n)=\frac1n\sum_{i=1}^nZ_i$ なので、大数の法則 の定理「大数の弱法則」により 1 が成り立つ。
$\mathbf x\in T_n^\varepsilon$ なら $e^{-n(H+\varepsilon)}\le p^n(\mathbf x)\le e^{-n(H-\varepsilon)}$ である。左の不等式を $T_n^\varepsilon$ の上で足すと $1\ge\sum_{\mathbf x\in T_n^\varepsilon}p^n(\mathbf x)\ge\#T_n^\varepsilon\,e^{-n(H+\varepsilon)}$ である。右の不等式を足すと $P\bigl((X_1,\dots,X_n)\in T_n^\varepsilon\bigr)\le\#T_n^\varepsilon\,e^{-n(H-\varepsilon)}$ であり、1 と合わせて 2 の左の不等式を得る。$\square$

1。 $c:=\sum_i2^{-d_i}$ とおくと、二分木 の定理「葉の深さの不等式」により $0< c\le1$ である。$r_i:=2^{-d_i}/c$ は確率分布なので、thm-ent-gibbs を $\log2$ で割った形により
$$ 0\le\sum_ip_i\log_2\frac{p_i}{r_i}=\sum_ip_i\log_2p_i+\sum_ip_id_i+\log_2c=-H_2(X)+L+\log_2c $$
であり、$\log_2c\le0$ から $L\ge H_2(X)$ である。
2。 $d_i\ge\log_2(1/p_i)$ より $2^{-d_i}\le p_i$ なので $\sum_i2^{-d_i}\le1$ であり、二分木 の定理「葉の深さの不等式」の 2 によりこの長さの接頭符号がある。$d_i< \log_2(1/p_i)+1$ を $p_i$ を掛けて足すと $L< H_2(X)+1$ である。$\square$

組 $(X_1,\dots,X_n)$ は確率がすべて正の $m^n$ 個の値をとり、thm-ent-chain の 2（独立なら等号）を繰り返し使うと $H_2(X_1,\dots,X_n)=nH_2(X)$ である。thm-ent-coding を組に使い、$n$ で割ればよい。$\square$