信息论 | 期末考试

时间: 2025.6.10, 08:30-10:30, 闭卷.

1 KL-divergence

Problem 设集合 \(\mathcal{X}\) 上的两个离散随机变量分别有分布密度 \(p,q\), 定义 KL-散度为 \[ D(p\parallel q) := \sum_{x\in\mathcal{X}} p(x) \log\frac{p(x)}{q(x)}. \]

1. 证明 \(D(p\parallel q)\) 是关于 \((p,q)\) 的凸函数.
2. 设集合 \(\mathcal{X}\times\mathcal{Y}\) 上两个离散随机向量的联合分布密度分别为 \(p_{XY}\) 和 \(q_{XY}\), 其关于 \(X\) 的边缘分布密度分别为 \(p_X\) 和 \(q_X\), 证明 \(D(p_{XY}\parallel q_{XY})\geq D(p_X\parallel q_X)\).

第一问. 对于有限支随机变量, 可以使用 Hessian 的半正定性验证 KL-散度的凸性. 这里使用另一种方法——对数和不等式, 它容易推广到无穷离散随机变量.

Lemma (对数和不等式) 设非负实数 \(a_1,\dots,a_n\) 及 \(b_1,\dots,b_n\), 则 \[ \sum_{i=1}^n a_i \log\frac{a_i}{b_i} \geq a\log\frac{a}{b}, \] 其中 \(a,b\) 分别是 \(a_1,\dots,a_n\) 和 \(b_1,\dots,b_n\) 的和.

Pf 设 \(f(x):=x\log{x}\), 则 \(f(x)\) 是凸函数. 设 \(\beta_i:=b_i/b\), 则 \((\beta_i)\) 是一个分布密度. 记 \(x_i:=a_i/b_i\), 由 Jensen 不等式, \[ \sum_{i=1}^n \beta_i f(x_i) \geq f\!\pqty{\sum_{i=1}^n \beta_ix_i}, \] 代入 \(f(x)\) 并化简即得对数和不等式.

回到原题. 直接验证凸函数的定义, \[ \Align{ & D\Bigl( (1-\lambda)p_1+\lambda p_2 \parallel (1-\lambda)q_1+\lambda q_2 \Bigr) \\ &\quad= \sum_{x\in\mathcal{X}} \Bigl[(1-\lambda)p_1(x) + \lambda p_2(x)\Bigr] \log\frac {(1-\lambda)p_1(x) + \lambda p_2(x)} {(1-\lambda)q_1(x) + \lambda q_2(x)} \\ &\quad\leq \sum_{x\in\mathcal{X}} \biggl[ (1-\lambda)p_1(x)\log\frac{(1-\lambda)p_1(x)}{(1-\lambda)q_1(x)} + \lambda p_2(x)\log\frac{\lambda p_2(x)}{\lambda q_2(x)} \biggr] \\ &\quad= (1-\lambda) \sum_{x\in\mathcal{X}} \Bigl[ p_1(x)\log\frac{p_1(x)}{q_1(x)} \Bigr] + \lambda \sum_{x\in\mathcal{X}} \Bigl[ p_2(x)\log\frac{p_2(x)}{q_2(x)} \Bigr] \\ &\quad= (1-\lambda) D(p_1 \parallel q_1) + \lambda D(p_2 \parallel q_2). } \] 其中第二步利用了二元的对数和不等式.

第二问. 直接使用对数和不等式, \[ \Align{ D(p_{XY} \parallel q_{XY}) &= \sum_{x\in\mathcal{X}} \Biggl[ \sum_{y\in\mathcal{Y}} p_{XY}(x,y) \log\frac{p_{XY}(x,y)}{q_{XY}(x,y)} \Biggr] \\ &\leq \sum_{x\in\mathcal{X}} \Biggl[ \pqty{\textstyle\sum_{y\in\mathcal{Y}} p_{XY}(x,y)} \log\frac {\sum_{y\in\mathcal{Y}} p_{XY}(x,y)} {\sum_{y\in\mathcal{Y}} q_{XY}(x,y)} \Biggr] \\ &= \sum_{x\in\mathcal{X}} p_X(x)\log\frac{p_X(x)}{q_X(x)} \vphantom{\Biggl[} \\ &= D(p_X \parallel q_X) \vphantom{\biggl[}. } \]

2 Weighted minimum coding length

Problem 设离散随机变量 \(X\) 的概率密度为 \((p_1,\dots,p_n)\). 现考虑用码长 \((\ell_1,\dots,\ell_n)\) 的 uniquely decodable code 对 \(X\) 进行编码, 并且最小化加权平均码长 \[ L := \sum_{i=1}^n w_ip_i\ell_i, \] 其中权重 \(w_i>0\).

1. 当 \(\ell_i\) 为正实数时, 求出最小加权平均码长 \(L^*\).
2. 当 \(\ell_i\) 为正整数时, 构造出满足加权平均码长最小的编码.
3. 证明 2 中的编码的加权平均码长 \(L\) 满足 \(L^*\leq L\leq L^*+\sum_{i=1}^n w_ip_i\).

第一问. 为了把问题转化为不加权的情形, 令 \[ r_i := \frac{w_ip_i}{W},\qquad W:=\sum_{i=1}^n w_i \] 则 \(\sum_{i=1}^n r_i=1\), 换言之, \(R=(r_1,\dots,r_n)\) 是一个概率密度.

接下来的步骤是标准的. 由于每个 uniquely decodable code 都与一个长度相同的 prefix code 对应, 我们只考虑 prefix code. 为了让长度尽可能小, 需要 Kraft 不等式取等, 即 \(\sum_{i=1}^n2^{-\ell_i}=1\). 令 \[ q_i := 2^{-\ell_i}, \] 则 \(Q=(q_1,\dots,q_n)\) 是一个概率密度. 加权平均码长 \[ L = W \sum_{i=1}^n r_i \log\frac{1}{q_i}. \] 由 KL-散度的非负性, \[ 0 \leq D(R\parallel Q) = \sum_{i=1}^n r_i \log r_i + \sum_{i=1}^n r_i\log\frac{1}{q_i}, \] 取等当且仅当 \(Q=R\). 因此 \[ \Align{ L &\geq W\sum_{i=1}^n r_i\log\frac{1}{r_i} \\ &= \sum_{i=1}^n w_ip_i\log\frac{W}{w_ip_i} =: L^*, } \] 取等当且仅当 \(Q=R\), 即 \(\ell^*_i=\log\frac{W}{w_ip_i}\).

第二问. 以 \(r_i\) 为概率值构造 Huffman 编码即可.

第三问. 下界是显然的. 对于上界, 记 \(\ell_i:=\lceil\log\frac{W}{w_ip_i}\rceil\), 注意到 \[ \sum_{i=1}^n 2^{-\ell_i} \leq \sum_{i=1}^n 2^{-\log\frac{W}{w_ip_i}} = \sum_{i=1}^n \frac{w_ip_i}{W} \leq 1, \] 故存在以 \(\ell_i\) 为码长的 prefix code, 该编码的加权平均码长为 \[ \sum_{i=1}^n w_ip_i\ell_i \leq \sum_{i=1}^n w_ip_i \pqty{\log\frac{W}{w_ip_i}+1} = L^* + \sum_{i=1}^n w_ip_i. \] 由于 Huffman 编码不差于该编码, 可得加权平均码长的上界.

3 The ISBN-10 error detecting code

Problem 国际标准书号 (ISBN) 是国际通用的图书编号, 由 \(10\) 或 \(13\) 位数字构成. ISBN-10 的格式如下: \[ x_1 - x_2\,x_3\,x_4 - x_5\,x_6\,x_7\,x_8\,x_9 - x_{10}, \] 其中 \(x_1\) 为组号, \(x_2\,x_3\,x_4\) 为出版社号, \(x_5\,x_6\,x_7\,x_8\) 为书号, 满足 \(x_i\in\{0,\dots,9\}\) (\(1\leq i\leq9\)). 校验位 \(x_{10}\) 根据前面 \(9\) 位计算得到: \[ x_{10} = \pqty{\sum_{n=1}^9nx_n}\bmod11\in\{0,\dots,10\}, \] 若 \(x_{10}=10\), 则在 ISBN 中用 X 表示.

1. 证明 \((\sum_{n=1}^{10}nx_n)\bmod11=0\).

2. 证明 ISBN 可以检出任意一位 \(x_i\) (\(i=1,\dots,10\)) 的错误 (即错误的编码不满足检验条件).

3. 证明 ISBN 可以检出任意相邻两位交换的错误.

4. 分别把 ISBN-10 的第 \(10\) 位改成

   (a) \(x_{10}=(\sum_{n=1}^9 nx_n)\bmod10\), 其中 \(x_{10}\in\{0,\dots,9\}\), 以及

   (b) \(x_{10}=(\sum_{n=1}^9 nx_n)\bmod12\), 其中 \(x_{10}\in\{0,\dots,11\}\).

   比较 (a), (b) 与原 ISBN-10 三者在 2, 3 情形下的检错能力 (以未能检出的错误数之和计), 并排序.

第一问. 我们有 \[ \sum_{n=1}^{10}nx_n = \sum_{n=1}^{9}nx_n + 10x_{10} \equiv x_{10} + 10x_{10} = 11x_{10} \equiv 0 \pmod{11}. \] 第二问. 记 \[ S := \sum_{n=1}^{10} nx_n \] 该编码可以检测出错误当且仅当 \(11\not\mid S\).

假设 \(x_i\) 变为 \(x_i'\) (\(x_i'\neq x_i\)), 则 \[ S' - S = i(x_i'-x_i). \] 因为 \(11\) 是质数, \(11\mid i(x_i'-x_i)\) 当且仅当 \(11\mid i\) 或者 \(11\mid(x_i'-x_i)\), 然而 \(1\leq i\leq10\) 且 \(-10\leq x_i'-x_i\leq 10\), 都是不可能的. 总之 \(11\not\mid(S'-S)\), 即 \(11\not\mid S'\), 可以检出错误.

第三问. 假设 \(x_i\) 和 \(x_{i+1}\) 交换位置 (\(x_i\neq x_{i+1}\)), 则 \[ S' - S = x_i - x_{i+1}. \] 因为 \(-10\leq x_i-x_{i+1}\leq10\), 有 \(11\not\mid(S'-S)\), 可以检出错误.

第四问. 假设将最后一位改成模 \(N\). 如果发生了错误, 但是 \(N\mid(S'-S)\), 就说明该编码不能检出该错误.

• 对于第三问的情形, 由于 \(-(N-1)\leq x_i-x_{i+1}\leq N-1\) 且 \(x_i\neq x_{i+1}\), 必定有 \(N\not\mid(S'-S)\), 故一定可以检出错误.
• 对于第二问的情形, 可以分别枚举 \(N=10\) 和 \(N=12\) 的失败情况:
  • \(N=10\) (\(-9\leq x_i'-x_i\leq9\)),
    • \(i=2\) 且 \(x_i'-x_i\in\{\pm5\}\),
    • \(i=5\) 且 \(x_i'-x_i\in\{\pm2,\pm4,\pm6,\pm8\}\).
  • \(N=12\) (\(-11\leq x_i'-x_i\leq11\)),
    • \(i=2\) 且 \(x_i'-x_i\in\{\pm6\}\),
    • \(i=3\) 且 \(x_i'-x_i\in\{\pm4,\pm8\}\),
    • \(i=4\) 且 \(x_i'-x_i\in\{\pm3,\pm6,\pm9\}\),
    • \(i=6\) 且 \(x_i'-x_i\in\{\pm2,\pm4,\pm6,\pm8,\pm10\}\).

因此检错能力 \(N=11\) 最好, \(N=10\) 次之, \(N=12\) 最差.

4 Channel capacity

Problem 设离散随机变量 \(X\) 的分布为 \(P(X=i)=q_i\) (\(i=1,\dots,n\)), 随机变量 \(Y\sim\textsf{Bernoulli}(p)\), 且两者独立. 设 \(Z=XY\).

1. 给出 \(H(X),H(Y),H(Z)\) 的关系式.
2. 当 \(p_1,\dots,p_n,q\) 取何值时, 熵 \(H(Z)\) 最大?
3. 设信道的输入为 \(X\), 输出为 \(Z\), 求该信道的容量.

第一问. 可得 \(P(Z=0)=1-p\) 及 \(P(Z=i)=pq_i\) (\(i=1,\dots,n\)), 因此 \[ \Align{ H(Z) &= \sum_{i=0}^n P(Z=i) \log\frac{1}{P(Z=i)} \\ &= (1-p)\log\frac{1}{1-p} + \sum_{i=1}^n pq_i \log\frac{1}{pq_i} \\ &= (1-p)\log\frac{1}{1-p} + \sum_{i=1}^n pq_i \log\frac{1}{p} + \sum_{i=1}^n pq_i \log\frac{1}{q_i} \\ &= (1-p)\log\frac{1}{1-p} + p\log\frac{1}{p} + p\sum_{i=1}^n q_i \log\frac{1}{q_i} \\ &= H(Y) + pH(X). } \] 第二问. 当 \(Z\) 为 \(\{0,1,\dots,n\}\) 上的均匀分布, 即 \[ q_i = \frac{1}{n},\qquad p = \frac{n}{n+1} \] 时, \(H(Z)\) 取到最大值 \(\log(1+n)\).

第三问. 注意到 \(H(Z\mid X=i)=H(Y)\). 互信息为 \[ \Align{ I(X;Z) &= H(Z) - H(Z\mid X) \\ &= H(Z) - \sum_{i=1}^n H(Z\mid X=i) P(X=x_i) \\ &= H(Z) - \sum_{i=1}^n H(Y) P(X=x_i) \\ &= H(Z) - H(Y) \vphantom{\sum} \\ &= pH(X) \vphantom{\sum}. } \] 当 \(X\) 为 \(\{1,\dots,n\}\) 上的均匀分布时, \(H(X)\) 取到最大值 \(\log{n}\). 因此信道容量 \[ C = p\log{n}. \]

5 Encryption and entropy

Problem 考虑一种加密算法. 将信息 \(M\) 用密钥 \(K\) 加密为三个密文片段 \((X_1,X_2,X_3)\).反之, 利用 \((X_1,X_2,X_3)\) 也可以还原出 \(M\) 和 \(K\), 但只利用其中两个则无法还原.

具体来说, 设 \(M,K,X_1,X_2,X_3\) 都是随机变量, 且满足 (1) \(K,M\) 相互独立; (2) 存在函数 \(f,g\), 使得 \[ (X_1,X_2,X_3) = f(K,M), \qquad (K,M) = g(X_1,X_2,X_3); \] (3) \(I(X_i,X_j;M)\leq cH(X)\) 对任意 \(1\leq i<j\leq3\), 其中常数 \(c\in(0,1]\).

1. 对一般的离散随机变量 \(X,Y\), 证明: 若存在函数 \(f\) 使得 \(Y=f(X)\), 则 \(H(Y)\leq H(X)\).

2. 对一般的离散随机变量 \(X_1,X_2,X_3\), 证明: \[ 2H(X_1,X_2,X_3) \leq H(X_1,X_2)+H(X_2,X_3)+H(X_3,X_1). \]

3. 证明 \(H(K)\geq(2-3c)H(M)\). (提示: 先证明 \(H(X_i,X_j)\leq H(K)+cH(M)\).)

本题看似复杂, 但若理解熵的物理含义的话是很简单的. 建议画 Venn 图.

第一问. 注意此时 \(Y\) 完全由 \(X\) 确定 (给定 \(X\) 的值后, \(Y\) 是确定分布), 而 \(X\) 不一定由 \(Y\) 确定, 故 \[ H(Y\mid X) = 0,\qquad H(X\mid Y)\geq0. \] 根据恒等式 \[ H(X) - H(X\mid Y) = I(X;Y) = H(Y) - H(Y\mid X), \] 有 \[ H(X) - H(Y) = H(X\mid Y) - H(Y\mid X) \geq 0. \] 第二问. 根据条件熵与联合熵的关系, \[ \Align{ H(X_1,X_2,X_3) &= H(X_1,X_2) + H(X_3\mid X_1,X_2), \\ H(X_1,X_2,X_3) &= H(X_2,X_3) + H(X_1\mid X_2,X_3), \\ } \] 两式相加, 并减去待证不等式的右边, 得到 \[ \Align{ & 2H(X_1,X_2,X_3) - \sum_{i<j} H(X_i,X_j) \\ &\quad= H(X_3\mid X_1,X_2) + H(X_1\mid X_2,X_3) - H(X_1,X_3) \vphantom{\sum} \\ &\quad= \orange{H(X_3\mid X_1,X_2)} + \blue{H(X_1\mid X_2,X_3)} \blue{ {} - H(X_1)} \orange{ {}- H(X_3\mid X_1)} \vphantom{\sum} \\ &\quad\leq 0. } \] 其中橙色部分和蓝色部分分别小于零 (condition reduces entropy).

第三问. 我们先证明 \[ H(X_i,X_j) \leq H(K)+cH(M). \tag{$\spadesuit$} \] 根据条件 (3), 有 \[ \Align{ cH(M) \geq I(X_i,X_j;M) = H(X_i,X_j) - H(X_i,X_j\mid M). } \] 为了得到 \((\spadesuit)\) 式, 我们只需说明 \(H(X_i,X_j\mid M)\leq H(K)\). 因为 \((X_i,X_j)\) 是 \((K,M)\) 的函数, 由第一问的结论, 有 \[ H(X_i,X_j\mid M) \leq H(K,M\mid M) = H(K\mid M) = H(K). \] (最后一个等号根据条件 (1) \(K,M\) 独立.) 这便证明了 \((\spadesuit)\). 因此 \[ \Align{ 2[H(K) + H(M)] &\stackrel{\textsf{(a)}}{=} 2[H(K,M)] \vphantom{\sum} \\ &\stackrel{\textsf{(b)}}{=} 2H(X_1,X_2,X_3) \vphantom{\sum} \\ &\stackrel{\textsf{(c)}}{\leq} \sum_{i<j} H(X_i,X_j) \\ &\stackrel{\textsf{(d)}}{\leq}3[H(K) + cH(M)] \vphantom{\sum}. } \] 其中步骤 (a) 根据条件 (1); 步骤 (b) 根据条件二和第一问的结论; 步骤 (c) 根据第二问的结论; 步骤 (d) 是不等式 \((\spadesuit)\). 将上式两边化简即得待证不等式.