hw05

第 1 题

题目 设 $X,Y,Z$ 为随机变量，证明 $I(X;(Y,Z))=I(X;Z)+I(X;Y\mid Z).$

证明 用互信息的链式法则。从定义出发： $I(X;(Y,Z))=H(X)-H(X\mid Y,Z).$

在右边加减 $H(X\mid Z)$： $I(X;(Y,Z))=[H(X)-H(X\mid Z)]+[H(X\mid Z)-H(X\mid Y,Z)].$

分别辨认两个括号：

• $H(X)-H(X\mid Z)=I(X;Z)$，由互信息定义。
• $H(X\mid Z)-H(X\mid Y,Z)=I(X;Y\mid Z)$，由条件互信息定义。

因此 $I(X;(Y,Z))=I(X;Z)+I(X;Y\mid Z).$

---

第 2 题（30 分）

题目 设 $X_1,X_2\in {0,1}^n$ 为相关随机向量，对每一坐标 $i$ 有 $\mathrm{Pr}[X_{1,i}=X_{2,i}]=p$（坐标之间独立）。设 $N\in {0,1}^n$ 为独立的 Bernoulli($\epsilon$) 噪声。定义 $Y_1=X_1\oplus N,Y_2=X_2\oplus N.$ 求 $I(X_1,X_2;Y_1,Y_2)$。

设 $X_1,X_2$ 的边际均匀分布（每个 $X_j$ 在 ${0,1}^n$ 上均匀），且各坐标 i.i.d.，于是问题化为 $n$ 倍的单比特情形。

单比特计算： 利用 $I(X_1,X_2;Y_1,Y_2)=H(Y_1,Y_2)-H(Y_1,Y_2\mid X_1,X_2).$ 给定 $(X_1,X_2)$ 时，$(Y_1,Y_2)=(X_1\oplus N,X_2\oplus N)$ 完全由 $N$ 决定；反之由 $(X_1,Y_1)$ 可恢复 $N=X_1\oplus Y_1$，所以 $H(Y_1,Y_2\mid X_1,X_2)=H(N)=H(\epsilon ),$ 其中 $H(\epsilon )=-\epsilon {\log }_2\epsilon -(1-\epsilon ){\log }_2(1-\epsilon )$ 为二元熵函数。

$(Y_1,Y_2)$ 的联合熵。 每个 $Y_j$ 在 $0,1$ 上均匀，而 $\mathrm{Pr}[Y_1=Y_2]=\mathrm{Pr}[X_1=X_2]=p,$ 因为 $Y_1\oplus Y_2=X_1\oplus X_2$，噪声 $N$ 在异或中抵消。所以 $(Y_1,Y_2)$ 的联合分布为 $\mathrm{Pr}(0,0)=\mathrm{Pr}(1,1)=\frac{p}{2},\mathrm{Pr}(0,1)=\mathrm{Pr}(1,0)=\frac{1-p}{2},$ 从而 $H(Y_1,Y_2)=1+H(p).$

单比特互信息 $I(X_1,X_2;Y_1,Y_2{)}_{\text{1 比特}}=1+H(p)-H(\epsilon ).$

$n$ 比特答案： 由坐标 i.i.d.， $I(X_1,X_2;Y_1,Y_2)=n[1+H(p)-H(\epsilon )].$

验证特殊情形：

• $\epsilon =0$（无噪声）：$I=n[1+H(p)]=H(X_1,X_2)$，接收方得到全部信息。
• $\epsilon =1/2$（最大噪声）：$H(\epsilon )=1$，故 $I=n,H(p)=H(X_1\oplus X_2)$，仅泄露异或。 ✓
• $p=1$（$X_1=X_2$）：$I=n[1-H(\epsilon )]$，即单个 BSC 的容量表达式。

---

第 3 题（40 分）

设定 $X,K\in {0,1}^n$ 独立且均匀分布；$Y=X\oplus K$。

(a) 求 $H(Y\mid X)$

给定 $X=x$ 时，$Y=x\oplus K$ 是 $K$ 的双射函数，所以 $H(Y\mid X=x)=H(K)=n.$ 对 $x$ 取平均得 $H(Y\mid X)=n\text{ 比特}.$

(b) 求 $H(Y)$

对任意固定的 $x$，$Y=x\oplus K$ 在 ${0,1}^n$ 上均匀（因为 $K$ 均匀）。所以 $Y$ 的边际分布均匀，从而 $H(Y)=n\text{ 比特}.$

(c) 求 $I(X;Y)$

$I(X;Y)=H(Y)-H(Y\mid X)=n-n=0.$