Elements of Information Theory 读书笔记 Part I

因为量子计算的书提到了一点信息论，所以来简单补一下信息论的基础知识，主要是 data compression 和 data transmission 相关的内容。看一下《Elements of Information Theory》这本书的前 7 章。

2. Entropy, Relative Entropy, and Mutual Information

令 $X$ 为离散随机变量，对应 alphabet $\mathcal{X}$，以及概率质量函数 $p(x)=Pr\{X=x\}$（probability mass function，注意这个和 probability density function 不同，这个是用来形容离散随机变量的）我们定义熵（entropy）为：

$H(X)=-\sum_{x\in\mathcal{X}}p(x)\log_2 p(x)$

我们用 $H_b(X)$ 来表示 log 的底数为 $b$ 的值。可以通过公理化的方式来反推出 entropy（见习题 2.46）。

熵有这样的性质：

$H(X)\ge0\\ H_b(X)=(\log_ba)H_a(X)$

若 $X\sim \text{Bern}(p)$，定义

$H(p)=H(X)=-p\log p-(1-p)\log(1-p)$

注意 $H(p)\le1$ 是它的上界，在 $p=1/2$ 时取到。

定义一对离散随机变量的联合熵（joint entropy）为：

$H(X,Y)=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log p(x,y)\\ H(X,Y)=-E\log p(X,Y)$

定义条件熵（conditional entropy）为：

$\begin{aligned} H(Y|X)&=\sum_{x\in\mathcal{X}}p(x)H(Y|X=x)\\ &=-\sum_{x\in\mathcal{X}}p(x)\sum_{y\in\mathcal{Y}}p(y|x)\log p(y|x)\\ &=-\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log p(y|x)\\ &=-E\log p(Y|X) \end{aligned}$

（注意这里多了一层求和）。他们有这样的性质：

$H(X,Y)=H(X)+H(Y|X)\\ H(X,Y|Z)=H(X|Z)+H(Y|X,Z)\\ H(X|X)=0$

定义概率密度函数 $p(x)$ 和 $q(x)$ 间的 relative entropy 或 KL 距离（Kullback-Leibler distance）为：

$D(p||q)=\sum_{x\in\mathcal{X}}p(x)\log\frac{p(x)}{q(x)}=E_p\log\frac{p(X)}{q(X)}$

这里我们补充定义 $0\log\frac{0}{0}=0,0\log\frac{0}{q}=0,p\log\frac{p}{0}=\infty$。所以如果存在 $p(x)>0,q(x)=0$ 那么距离无穷大。

相对熵是用来表示概率密度之间的距离的，尤其是如果原本分布为 $p$ 的随机变量可以用 $H(p)$ 描述，但是如果用 $q$ 来描述它，就需要 $H(p)+D(p||q)$ 来表述了。

定义 mutual information $I(X;Y)$ 是 joint distribution 和 product distribution 之间的 relative entropy：

$\begin{aligned} I(X;Y)&=\sum_{x\in\mathcal{X}}\sum_{y\in\mathcal{Y}}p(x,y)\log\frac{p(x,y)}{p(x)p(y)}\\ &=D(p(x,y)||p(x)p(y))\\ &=E_{p(x,y)}\log\frac{p(X,Y)}{p(X)p(Y)} \end{aligned}$

有这样的性质：

$\begin{aligned} I(X;Y)&=H(X)-H(X|Y)\\ I(X;Y)&=H(Y)-H(Y|X)\\ I(X;Y)&=H(X)+H(Y)-H(X,Y)\\ I(X;Y)&=I(Y;X)\\ I(X;X)&=H(X) \end{aligned}$

还有 chain rule for entropy：

$H(X_1,X_2,...,X_n)=\sum_{i=1}^nH(X_i|X_{i-1},...,X_1)$

定义 conditional mutual information 为：

$\begin{aligned} I(X;Y|Z)&=H(X|Z)-H(X|Y,Z)\\ &=E_{p(x,y,z)}\log\frac{p(X,Y|Z)}{p(X|Z)p(Y|Z)} \end{aligned}$

以及 chain rule for information：

$I(X_1,X_2,...,X_n;Y)=\sum_{i=1}^nI(X_i;Y|X_{i-1},...,X_1)$

定义 conditional relative entropy 为：

$\begin{aligned} D(p(y|x)||q(y|x))&=\sum_xp(x)\sum_yp(y|x)\log\frac{p(y|x)}{q(y|x)}\\ &=E_{p(x,y)}\log\frac{p(Y|X)}{q(Y|X)} \end{aligned}$

（注意这个定义比 relative entropy 多了一层求和）。它有兴致：

$D(p(x,y)||q(x,y))=D(p(x)||q(x))+D(p(y|x)||q(y|x))$

information inequality：

$D(p||q)=E_p\log\frac{p(X)}{q(X)}=-E_p\log\frac{q(X)}{p(X)}\ge \log E_p\frac{q(X)}{p(X)}=0$

这里 $E_p$ 和 $\log$ 的交换来源于 $\log$ 的凸性。类似地，我们有 $I(X;Y)\ge0$，以及 $I(X;Y|Z)\ge0$。

由此，有推论，$I(X;Y)\ge0$，$D(p(y|x)||q(y|x))\ge0$，$I(X,Y|Z)\ge0$。

另外有，

$H(X)\le\log|\mathcal{X}|$

因为：

$0\le D(p||u)=\sum p(x)\log\frac{p(x)}{u(x)}=\log|\mathcal{X}|-H(X)$

这里给了 $H(X)$ 的上界。

以及：

$H(X|Y)=H(X)-I(X;Y)\le H(X)$

拓展出去，还有：

$H(X_1,X_2,...,X_n)\le\sum_{i=1}^nH(X_i)$

通过 $\log$ 的凸性，有：

$\sum_{i=1}^na_i\log\frac{a_i}{b_i}\ge(\sum_{i=1}^na_i)\log\frac{\sum_{i=1}^nb_i}{\sum_{i=1}^na_i}$

我们可以由此证明 $D(p||q)$ 的凸性。再由于 $H(X)=\log|\mathcal{X}|+D(p||u)$，也是凸的。我们还可以证明，如果固定 $p(x)$ 或固定 $p(y|x)$，那么 $I(X;Y)$ 是凸的。

定义 如果 $X,Y,Z$ 满足 $p(x,y,z)=p(x)p(y|x)p(z|y)$，则他们组成了 Markov chain，标记为 $X\rightarrow Y\rightarrow Z$

定理 data inequality theorem：如果 $X\rightarrow Y\rightarrow Z$，则 $I(X;Y)\ge I(X;Z)$ 以及 $I(Y;Z)\ge I(X;Z)$。

• 这里的证明之后要补一下，但是直观上很好理解，隔了一层，相关信息肯定降低了。

定理 Fano's inequality：假如我们希望用从 $p(y|x)$ 观测到的 $Y$，通过 $g(Y)=\hat{X}$，预测有分布 $p(x)$ 的 $X$，也就是有 $X\rightarrow Y\rightarrow\hat{X}$，并定义

$P_e=Pr\{\hat{X}\ne X\}$

那么有：

$1 + P_e\log|\mathcal{X}|\ge H(P_e)+P_e\log|\mathcal{X}|\ge H(X|\hat{X})\ge H(X|Y)$

这个定理给了 conditional entropy 一个上界。

• 我们来尝试证明中间的这个不等式。定义随机变量 $E$ 为 $X$ 是否等于 $\hat{X}$，不等的时候值为 1，相等时值为 0。因为 $E$ 完全由 $X,\hat{X}$ 决定，所以有：

  $H(X|\hat{X})=H(E,X|\hat{X})-H(E|X,\hat{X})=H(E,X|\hat{X})$

  继续展开有：

  $\begin{aligned} H(E,X|\hat{X})&=H(E|\hat{X})+H(X|E,\hat{X})\\ &=H(E|\hat{X})+Pr(E=0)H(X|E=0,\hat{X})+Pr(E=1)H(X|E=1,\hat{X})\\ &=H(E|\hat{X}) + (1-P_e)0 + P_eH(X|E=1,\hat{X})\\ &\le H(P_e)+P_e\log|\mathcal{X}|\\ &\le 1+P_e\log|\mathcal{X}| \end{aligned}$

  （这个证明的核心在于，如果一个事件由其他事件决定了，那么它的条件熵就为 0 了。

有一个不那么明显的引理：如果 $X$ 和 $X'$ 遵从 i.i.d.，那么：

$\text{Pr}(X=X')=\sum_xp(x)^2=\sum_xp(x)2^{\log p(x)}\ge2^{\sum p(x)\log p(x)}=2^{-H(X)}$

3. Asymptotic Equipartition Property

在信息论中，大数定律对应的就是 asynnptotic equipartition property（AEP）。

定义 convergence of random variables：给一个随机变量序列 $X_1,X_2,...$，我们称这个序列

1. 依概率（in probability）收敛于 $X$，如果 $\forall \epsilon>0,\text{Pr}\{|X_n-X|>\epsilon\}\rightarrow0$
2. 依 mean square 收敛于 $X$，如果 $E(X_n-X)^2\rightarrow0$
3. 收敛于 $X$ 的概率为 1，如果 $\text{Pr}\{\lim_{n\rightarrow\infty}X_n=X\}=1$

定理 AEP：如果 $X_1,X_2,...$ i.i.d $\sim p(x)$，那么：

$-\frac{1}{n}\log p(X_1,X_2,...,X_n)\rightarrow H(X)\quad \text{in probability}$

• 根据大数定律

  $-\frac{1}{n}\log p(X_1,X_2,...,X_n)=-\frac{1}{n}\sum_i\log p(X_i)\rightarrow-E\log p(X)=H(X)$

注意 AEP 可以扩展到 ergodic process，这个 process 的定义就是保证了大数定律的 process，所以证明上差别不大。

定义 typical set $A_\epsilon^{(n)}$ w.r.t $p(x)$，是序列 $(x_1,x_2,...,x_n)\in\mathcal{X}^n$（它们是 i.i.d. 地取出来的，或者扩展出去也是由 ergodic process 得到的）满足：

$2^{-n(H(x)+\epsilon)}\le p(x_1,x_2,...,x_n)\le 2^{-n(H(x)-\epsilon)}$

的序列集合。

typical set 有这样的一些性质：

1. 如果 $(x_1,x_2,...,x_n)\in A_\epsilon^{(n)}$，那么 $H(X)-\epsilon\le-\frac{1}{n}\log p(x_1,x_2,...,x_n)\le H(X)+\epsilon$；

   这个由定义显然。

2. 对于足够大的 $n$，$\text{Pr}\{A_\epsilon^{(n)}\}>1-\epsilon$；

   这个结论还是很厉害的，就是说不在 $A_\epsilon^{(n)}$ 的序列很少。这个证明则是要去考虑啥叫 $\text{Pr}\{A_\epsilon^{(n)}\}$，其实就是想说：

   $\text{Pr}\{A_\epsilon^{(n)}\}=\text{Pr}\{|-\frac{1}{n}\log p(X_1,X_2,...,X_n)-H(X)|<\epsilon\}>1-\epsilon$

   这个可以直接用 AEP 了。

3. 由 2，有 $(1-\epsilon)2^{n(H(X)-\epsilon)}\le|A_\epsilon^{(n)}|\le 2^{n(H(X)+\epsilon)}$

我们可以用 typical set 构造出一种编码方式，满足如下的定理（这个构造挺有意思的，建议看原书）

定理：令 $X^n$ 为 i.i.d $\sim p(x)$，对于任意 $\epsilon>0$，当 $n$ 足够大时，存在一种编码方式，将 $x^n$ 一一映射为二进制字符串，并满足：

$E[\frac{1}{n}l(X^N)]\le H(X)+\epsilon$

接下来有一些结论可以证明，typical set 几乎就是所有序列中概率最大的那部分序列了。（这个结论也挺神奇的）

4. Entropy Rates of a Stocastic Process

定义：随机过程为 stationary 意味着，对于任意 $n,l$，都有

$\text{Pr}\{X_1=x_1,X_2=x_2,...,X_n=x_n\}=\text{Pr}\{X_{1+l}=x_1,X_2=x_{2+l},...,X_n=x_{n+l}\}$

定义：Markov chain 或者 Markov 过程为：

$\text{Pr}\{X_{n+1}=x_{n+1}|X_{n}=x_n,X_{n-1}=x_{n-1},...,X_1=x_1\}=\text{Pr}\{X_{n+1}=x_{n+1}|X_{n}=x_n\}$

定义：time invariant Markov chain 为：

$\text{Pr}\{X_{n+1}=b|X_{n}=a\}=\text{Pr}\{X_2=b|X_1=a\}\quad\forall a,b\in\mathcal{X}$

我们默认认为 Markov chain 是 time invariant 的。

定义：随机过程 $\{X_i\}$ 的熵为：

$H(\mathcal{X})=\lim_{n\rightarrow\infty}\frac{1}{n}H(X_1,X_2,...,X_n)$

但是显然这个极限不一定存在。所以我们得研究一下啥时候他存在。

定理：对于 stationary 随机过程，$H(x_n|X_{n-1},...,X_1)$ 为不增序列，极限为 $H'(\mathcal{X})$。

• 这是因为 $H(x_{n+1}|X_{n},...,X_2,X_1)\le H(x_{n+1}|X_{n},...,X_2)=H(x_n|X_{n-1},...,X_1)$。而其恒大于 0，故有极限。

定理 Cesaro mean：如果 $a_n\rightarrow a$，且 $b_n=\frac{1}{n}\sum_{i=1}^n a_i$，则 $b_n\rightarrow a$。

• 这个感觉还挺好证的

定理：stationary 随机过程的 $H(\mathcal{X})$ 存在，并等于 $H'(\mathcal{X})$。

• 这是可以把 joint distribution 变成一堆 conditional distribution 之和。

对于 stationary ergodic process，会有类似的 AEP，也就收敛到这个 $H'(\mathcal{X})$。对于 stationary Markov chain，则收敛到 $H(X_2|X_1)$。

5. Data Compression

定义：$X$ 的 source code $C$ 指一个从 $\mathcal{X}$ 到 $D*$，即词表为 $D$ 的有限长字符串集合的映射。$C(x)$ 为对应的 codeword，$l(x)$ 为对应的长度。

定义：expect length $L(C)$ 为：$L(C)=\sum_{x\in\mathcal{X}}p(x)l(x)$。

定义：若 $x\ne x'\Rightarrow C(x)\ne C(x')$，我们称这个 code nonsingular。

定义：$C(x_1x_2...x_n)=C(x_1)C(x_2)...C(x_n)$ 为 $C$ 的 extension。

定义：如果 code 的 extension 是 nonsingular 的，那么称其为 uniquely decodable。

定义：如果没有 codeword 是其他 codeword 的 prefix，那么我们称这种 code 为 prefix code 或 instantaneous code。

注意到，instantaneous code 一定是 uniquely decodable 的。

定理 Kraft inequality：对于 instantaneous code，

$\sum_iD^{-l_i}\le1$

反过来，如果有这样的一组 codeword 长度，我们可以构建一套 instantaneous code。

• 证明是考虑 $D$ 叉树，每个枝头都只能有一个，所以合起来不到 1。

定理 extended Kraft inequality：对于可数个 codeword 组成的 instantaneous code，

$\sum_{i=1}^\infty D^{-l_i}\le1$

反过来也是一样。

• 证明是对 $D$ 进制小数的有理数区间，还挺有意思的。

定理 McMillan inequality 对于 unique decodable D-ary code 或者 infinite source $\mathcal{X}$ 也满足 Kraft inequality。

定理：$L\ge H_D(X)$，只有在 $D^{-l_i}=p_i$ 的时候取等。

定理：optimal codeword length 满足 $H_D(X)\le L^*\le H_D(X)+1$。

定理：对于 stochastic process，更是有：

$\frac{H(X_1,X_2,...,X_n)}{n}\le L_n^*\le \frac{H(X_1,X_2,...,X_n)}{n}+\frac{1}{n}$

对于 stationary 随机过程，就有 $L_n^*\rightarrow H(\mathcal{X})$。

定理 wrong code：如果用 $p(x)$ 对应了长度为 $l(x)=\left\lceil\log\frac{1}{q(x)}\right\rceil$（Shannon code），那么：

$L(x)=D(p||q)+H(p)+1$

定理：Huffman code 为 $L^*=\min_{\sum D^{-l_i}\le1}\sum p_il_i$，是 optimal 的，即 $H_D(X)\le L^*\le H_D(X)+1$。

这附近有一些关于怎么构造编码的东西，暂时不太感兴趣，先跳过了。

有一个比较重要的观察，就是 2 进制编码的每一维都应该相当于扔硬币，也就是每一位的熵都是 1。

6. Gambling and Data Compression

暂时不感兴趣，跳过。

7. Channel Capacity

定义：discrete channel 是一个由输入 alphabet $\mathcal{X}$，输出 alphabet $\mathcal{Y}$，一个 probability transition matrix $p(y|x)$ 表示输入 $x$ 得到 $y$ 的概率分布。用 $(\mathcal{X}, p(y|x), \mathcal{Y})$ 表示。

定义：我们称 channel 为 memoryless 如果输出仅依赖于这次的输入，和之前输入无关。

定义：我们定义 discrete memoryless channel 的 "information" channel capactiy 为：

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

我们会在后面定义 "operational" channel capacity，并证明这俩相等。

data compression 和 data transmission 实际上是对偶的问题。data compression 的目的是去除数据中的 redundancy，而 data transmission 是要靠增加 redundancy 来对抗噪音。

channel capacity 有这些特点：

1. 因为 $I(X;Y)\ge0$，所以 $C\ge0$；
2. $C=\max I(X;Y)\le \max H(X)=\log|\mathcal{X}|$；
3. 同理 $C\le \log|\mathcal{Y}|$。

定义：$(\mathcal{X}, p(y|x), \mathcal{Y})$ 的 $(M,n)$ code 包括：

1. 一个 index set $\{1,2,...,M\}$；
2. 一个 encoding function $X^n:\{1,2,...,M\}\rightarrow\mathcal{X}^n$，输出的 codeword 为 $x^n(1),x^n(2),...,x^n(M)$，codeword 的集合称为 codebook；

3. decoding function

   $g:\mathcal{Y}^n\rightarrow\{1,2,...,M\}$

   其为一个确定性的规则。

定义：conditional probability of error 为：

$\lambda_i=\text{Pr}(g(Y^n)\ne i|X^n=x^n(i))=\sum_{y^n,g(y^n)\ne i}p(y^n|x^n(i))$

定义：$(M,n)$ code 的 maximal probability of error $\lambda^{(n)}$ 为：

$\lambda^{(n)}=\max_{i\in\{1,2,...,M\}}\lambda_i$

定义：$(M,n)$ code 的 (arithmetic) avverage probability of error $P_e^{(n)}$ 为：

$P_e^{(n)}=\frac{1}{n}\sum_{i=1}^M\lambda_i$

定义：$(M,n)$ code 的 rate $R$ 为：

$R=\frac{\log M}{n}$

一个 rate 是 achievable 的，即存在当 $n\rightarrow\infty$ 时，存在 $(\left\lceil2^{nR}\right\rceil,n)$ code 满足 $\lambda^{(n)}\rightarrow 0$。

定义：channel 的 capacity 为 achievable 的最大 rate。

定义：序列 $\{(x^n,y^n)\}$ 的 jointly typical sequence 为：

$\begin{aligned} A_\epsilon^{(n)}=&\{(x^n,y^n)\in\mathcal{X}\times\mathcal{Y}:\\ &|-\frac{1}{n}\log p(x^n)-H(X)|<\epsilon\\ &|-\frac{1}{n}\log p(y^n)-H(Y)|<\epsilon\\ &|-\frac{1}{n}\log p(x^n,y^n)-H(X,Y)|<\epsilon\} \end{aligned}$

其中 $p(x^n,y^n)=\prod_{i=1}^np(x_i,y_i)$ 。

定理 joint AEP：令 $(X^n,Y^n)$ 为 i.i.d. 的长度为 $n$ 的序列，其分布为 $p(x^n,y^n)=\prod_{i=1}^np(x_i,y_i)$，那么：

1. 当 $n\rightarrow \infty$，$\text{Pr}((X^n,Y^n)\in A_\epsilon^{(n)})\rightarrow 1$

   • 证明用大数定律。

2. $|A_\epsilon^{(n)}|\le 2^{n(H(X,Y)+\epsilon)}$

   • 第 3 个概率限制展开有 $p(x^n,y^n)\ge2^{-n(H(X,Y)+\epsilon)}$

3. 若 $(\widetilde{X}^n,\widetilde{Y}^n)\sim p(x^n)p(y^n)$，即 $\widetilde{X}^n,\widetilde{Y}^n$ 是相互独立的，他们的分布是 $p(x,y)$ 的 marginal distribution，那么：

   $\text{Pr}((\widetilde{X}^n,\widetilde{Y}^n)\in A_\epsilon^{(n)})\le 2^{-n(I(X;Y-3\epsilon))}$

   且当 $n$ 足够大时：

   $\text{Pr}((\widetilde{X}^n,\widetilde{Y}^n)\in A_\epsilon^{(n)})\ge (1-\epsilon)2^{-n(I(X;Y+3\epsilon))}$
   • 前半部分因为前 2 个概率的限制有 $p(x^n)\le2^{-n(H(X)-\epsilon)},p(y^n)le2^{-n(H(Y)-\epsilon)}$，配合 2，就可以得到了。后半部分可以用反方向的限制配合 1 得到。

我们可以从 2 个角度理解上面的结论。

1. 理论上 $X^n$ 和 $Y^n$ 的 typical sequence 分别有 $2^{nH(X)}$ 和 $2^{nH(Y)}$ 那么多。但是 joint typical sequence 只有 $2^{nH(X,Y)}$ 这么多，随机选一对只有 $2^{-nI(X;Y)}$ 的概率选中，也就大致意味着有 $2^{nI(X;Y)}$ 多个相互独立的 $X^n$；
2. 固定一个 $Y^n$，有 $2^{nH(X|Y)}$ 个 typical $X^n$，所以随机选一个 $X^n$ 会 jointly typical with $Y^n$ 的概率为 $2^{nH(X|Y)}/2^{nH(X)}=2^{-nI(X;Y)}$，也就是我们大致可以选 $2^{nI(X;Y)}$ 个 $X^n$ 他们之间不会 confuse 为 $Y^n$。

定理 channel encoding theorem：对于 discrete memoryless channel，所有低于 capacity $C$ 的 rate $R$ 都是 achievable 的。反过来，achievable 的 $R$ 一定满足 $R\le C$。