Homework 01¶

约 2317 个字 16 张图片预计阅读时间 12 分钟

2.1¶

设 \(y_1\) 表示说真话，\(y_2\) 表示说假话，\(y_3\) 表示拒绝回答，那么有：

\[ \begin{aligned} P(y_1)&=0.5p+0.3(1-p)\\ P(y_2)&=0.3p+0.5(1-p)\\ P(y_3)&=0.2p+0.2(1-p)=0.2\\ H(Y)&=-\sum\limits_{i=1}^3P(y_i)\log P(y_i)\\ H(Y|X)&=P(A)H(Y|X=A)+P(B)H(Y|X=B)\\ &=-0.5\log 0.5-0.3\log 0.3-0.2\log 0.2=1.485\text{ bit}\\ I(X;Y)&=H(Y)-H(Y|X) \end{aligned} \]

要想让 \(I(X;Y)\) 最大，即让 \(H(Y)\) 最大：

\[ H(Y)=-(0.3+0.2p)\log(0.3+0.2p) - (0.5-0.2p)\log(0.5-0.2p) - 0.2\log 0.2 \]

求导：

\[ \begin{aligned} \frac{dH(Y)}{dp} &=\log e(0.2\ln\frac{5-2p}{3+2p})=\log e(0.2\ln(\frac{8}{3+2p}-1)) \end{aligned} \]

当导数为 0，即当 \(p=0.5\) 时，\(I(X;Y)\) 最大，此时：

\[ \begin{aligned} H(Y)&=0.4\log 0.4+0.4\log 0.4+0.2\log 0.2=1.522\text{ bit}\\ I(X;Y)&=H(Y)-H(Y|X)=0.037\text{ bit} \end{aligned} \]

2.2¶

设 \(X=x_1\) 表示抛掷骰子出现 1,2,3,4 点；\(X=x_2\) 表示抛掷骰子出现 5,6 点；\(Y=y_i\) 表示投掷硬币正面的出现次数，那么有：

\[ \begin{aligned} P(X=x_1)&=\frac{2}{3},P(X=x_2)=\frac{1}{3}\\ P(Y=y_0)&=\frac{5}{12},P(Y=y_1)=\frac{1}{2},P(Y=y_2)=\frac{1}{12}\\ \end{aligned} \]

所以：

\[ \begin{aligned} I(X;Y)&=H(Y)-H(Y|X)\\ &=H(\frac{5}{12},\frac{1}{2},\frac{1}{12})-\frac{2}{3}H(\frac{1}{2},\frac{1}{2})-\frac{1}{3}H(\frac{1}{4},\frac{1}{2},\frac{1}{4})\\ &=0.158\text{ bit} \end{aligned} \]

2.4¶

设第 \(i\) 个骰子的结果为 \(X_i\)

\[ \begin{aligned} H(X)&=H(X_1)=H(X_2)=H(X_3)=\log_2 6=2.585\text{ bit}\\ H(Y)&=H(X_1+X_2)=\sum\limits_{y_i}P(y_i)\log P(y_i)=3.274\text{ bit}\\ H(Z|Y)&=H(X_3)=2.585\text{ bit} \end{aligned} \]

\(H(X|Y)=H(X)+H(Y|X)-H(Y)=H(X)+H(X_2)-H(Y)=1.896\text{ bit}\)
\(H(Y|X)=H(X_2)=2.585\text{ bit}\)
\(H(Z|X,Y)=H(X_3)=2.585\text{ bit}\)
\(H(X,Z|Y)=H(X|Y)+H(Z|X,Y)=4.481\text{ bit}\)
\(H(Z|X)=H(X_2+X_3)=H(Y)=3.274\text{ bit}\)

2.5¶

设 \(X\) 表示发送的数字，\(Y\) 表示接收的数字，那么有：

\[ I(X;Y)=\sum\limits_{x\in\mathcal{X}}\sum\limits_{y\in\mathcal{Y}}p(x,y)\log\frac{p(x|y)}{q(x)} \]

（1）如果发送的是偶数，那么有：

\[ I(X;Y)_{\text{even}}=5\times\frac{1}{10}\log\frac{1}{0.1}=1.661\text{ bit} \]

（2）如果发送的是奇数，且接收正确，有：

\[ I(X;Y)_{\text{right odd}}=5\times 0.05\log\frac{0.5}{0.1}=0.581\text{ bit} \]

（3）如果发送的是奇数，且接收错误，有：

\[ I(X;Y)_{\text{wrong odd}}=20\times 0.0125\log\frac{0.125}{0.1}=0.08\text{ bit} \]

所以总信息量为 \(2.322\text{ bit}\)

2.6¶

（a）\(\text{LHS}\geq H(X|Y,Z)+H(Y|Z)=H(X,Y|Z)\geq H(X|Z)\)

（b）由 \(H(X|Y)=H(X,Y)-H(Y)\geq H(X,Y)-H(Y|Z)-H(Z)\Leftrightarrow H(X,Y)\leq H(X|Y)+H(Y|Z)+H(Z)\)

同理，有 \(H(Y,Z)\leq H(X|Y)+H(Y|Z)+H(Z)\)

所以有 \(LHS\geq\frac{H(X|Y)+H(Y|Z)}{H(X|Y)+H(Y|Z)+H(Z)}\geq\frac{H(X|Z)}{H(X|Z)+H(Y|Z)}\geq\frac{H(X|Z)}{H(X,Z)}\)

2.9¶

（a）

\[ \begin{aligned} H(Z)&=H(X,Y)-H(X,Y|Z)=H(X)+H(Y)-H(X,Y|Z)\\ &=H(X)+H(Y)-H(Y|Z)-H(X|Z,Y)\\ &=H(X)+H(Y)-H(Y|Z)=H(X)+I(Y;Z)\geq H(X) \end{aligned} \]

（b）同（a）类似

（c）由 \(H(Z)=H(X,Y)-H(X,Y|Z)\) 有 \(H(X,Y)\geq H(Z)\)

（d）

\[ \begin{aligned} H(Z)&=H(X)+H(Y)-H(X,Y|Z)\\ &=H(X)+H(Y)-H(X|Z)-H(Y|Z,X)\\ &=H(X)+H(Y)-H(X|Z)=H(Y)+I(X;Z)\\ \therefore I(X;Z)&=H(Z)-H(Y) \end{aligned} \]

（e）\(I(X,Y;Z)=H(Z)-H(Z|X,Y)=H(Z)\)

（f）\(I(X;Y,Z)=H(X)-H(X|Y,Z)=H(X)\)

（g）\(I(Y;Z|X)=H(Y|X)-H(Y|Z,X)=H(Y|X)=H(Y)\)

（h）\(I(X;Y|Z)=H(X|Z)-H(X|Y,Z)=H(X|Z)=H(Y|Z)\)

2.12¶

（a）

\[ \begin{aligned} H(Y,Z|X)&=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j,z_k|x_i)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)p(z_k|x_i,y_j)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)+\sum_{i,j,k}p(x_i,y_j,z_k)\log p(z_k|x_i,y_j)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)+\sum_{i,j,k}p(x_i,y_j)p(z_k|x_i,y_j)\log p(z_k|x_i,y_j)\\ &\leq-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)+\sum_{i,j,k}p(x_i,y_j)p(z_k|x_i,y_j)\log p(z_k|x_i)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)+\sum_{i,j,k}p(x_i,y_j,z_k)\log p(z_k|x_i)\\ &=-\sum_{i,j}p(x_i,y_j)\log p(y_j|x_i)+\sum_{i,k}p(x_i,z_k)\log p(z_k|x_i)\\ &=H(Y|X)+H(Z|X) \end{aligned} \]

当且仅当 \(p(y_j,z_k|x_i)=p(y_j|x_i)p(z_k|x_i)\) 成立时，等号成立

（b）

\[ \begin{aligned} H(Y, Z | X) &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j,z_k|x_i)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)p(z_k|x_i,y_j)\\ &=-\sum_{i,j,k}p(x_i,y_j,z_k)\log p(y_j|x_i)+\sum_{i,j,k}p(x_i,y_j,z_k)\log p(z_k|x_i,y_j)\\ &=H(Y|X)+H(Z|X, Y) \end{aligned} \]

（c）由（a）和（b）可得等号成立的充要条件为对一切 \(i, j, k\) 有 \(p(y_j,z_k|x_i)=p(y_j|z_k)p(z_k| x_i)\) 成立

2.13¶

（a）\(H(X)=H(\alpha,1-\alpha)+\alpha H(X_1)+(1-\alpha)H(X_2)\)

（b）

\[ \begin{aligned} H(X)&=H(\alpha,1-\alpha)+\alpha H(X_1)+(1-\alpha)H(X_2)\\ &=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha)+\alpha H(X_1)+(1-\alpha)H(X_2)\\ \end{aligned} \]

求导：

\[ \begin{aligned} \frac{dH(X)}{d\alpha}&=\log e(-\ln\alpha+\ln(1-\alpha))+H(X_1)-H(X_2)\\ &=\log\frac{1-\alpha}{\alpha}+H(X_1)-H(X_2) \end{aligned} \]

令导数为 0，底数为 2，有 \(\log\frac{1-\alpha}{\alpha}=H(X_2)-H(X_1)\)，解得 \(\alpha=\frac{1}{1+2^{H(X_2)-H(X_1)}}\)

\[ \begin{aligned} H(X)_{max}&=-\alpha\log\alpha-(1-\alpha)\log(1-\alpha)+\alpha H(X_1)+(1-\alpha)H(X_2)\\ &=-\log(1-\alpha)+\alpha\log(\frac{1-\alpha}{\alpha})+\alpha H(X_1)+(1-\alpha)H(X_2)\\ &=-\log(1-\frac{1}{1+2^{H(X_2)-H(X_1)}})+\alpha(H(X_2)-H(X_1))+\alpha H(X_1)+(1-\alpha)H(X_2)\\ &=-\log(\frac{2^{H(X_2)-H(X_1)}}{1+2^{H(X_2)-H(X_1)}})+H(X_2)\\ &=\log(\frac{2^{H(X_1)}+2^{H(X_2)}}{2^{H(X_2)}})+H(X_2)\\ &=\log(2^{H(X_1)}+2^{H(X_2)})\\ \end{aligned} \]

综上 \(2^{H(X)}\leq 2^{H(X_1)}+2^{H(X_2)}\)

2.19¶

\(p(x)=\frac{1}{2}, x\in[-1,1]\)，因此：

\[ H_C(X)=-\int p_X(x)\log p_X(x)dx=[-\frac{1}{2}\log\frac{1}{2}]·2=1\text{ bit} \]

令 \(Y=X^2\)，有 \(F_Y(y)=P(Y\leq y)=P(X^2\leq y)=P(-\sqrt{y}\leq X\leq \sqrt{y})=\int_{-\sqrt{y}}^{\sqrt{y}}\frac{1}{2}dx=\sqrt{y}\)

\(P(Y=y)=F_Y'(y)=\frac{1}{2\sqrt{y}}, y\in[0,1]\)

\(\therefore H_C(X^2)=-\int_{0}^{1}\frac{1}{2\sqrt{y}}\log\frac{1}{2\sqrt{y}}dy=\log 2-\log e\text{ bit}\)

2.20¶

（a）

\[ p(y)=\sum_{x\in X}p(x)p(y|x)=\begin{cases} \frac{1}{8}, & -3<y\leq -1\\ \frac{1}{4}, & -1<y\leq 1\\ \frac{1}{8}, & 1<y\leq 3\\ 0, & y\leq -3 \text{ or } y>3 \end{cases} \]

（b）

\[ \begin{aligned} H(Y)&=-\int_{-3}^{-1}\frac{1}{8}\log\frac{1}{8}dy-\int_{-1}^{1}\frac{1}{4}\log\frac{1}{4}dy-\int_{1}^{3}\frac{1}{8}\log\frac{1}{8}dy\\ &=\frac{1}{4}\log 8 + \frac{1}{2}\log 4 + \frac{1}{4}\log 8\\ &=\frac{5}{2}\log 2 \end{aligned} \]

\[ \begin{aligned} H(Y|X)=\sum_{x\in X}p(x)H(Y|X=x)&=\frac{1}{2}H(Y|X=1)+\frac{1}{2}H(Y|X=-1)\\ &=\frac{1}{2}\left[-\int_{-1}^{3}\frac{1}{4}\log\frac{1}{4}dy-\int_{-3}^{1}\frac{1}{4}\log\frac{1}{4}dy\right]\\ &=2\log2\\ \end{aligned} \]

\(\therefore I(X;Y)=H(Y)-H(Y|X)=\frac{5}{2}\log2-2\log2=\frac{1}{2}\log2\)

（c）

\[ P(V)=\begin{cases} \frac{1}{4}, &-3<y\leq -1,V=-1\\ \frac{1}{2}, &-1<y\leq 1,V=0\\ \frac{1}{4}, &1<y\leq 3,V=1\\ 0, & \text{otherwise} \end{cases} \]

\(\therefore H(V)=-\frac{1}{4}\log\frac{1}{4}-\frac{1}{2}\log\frac{1}{2}-\frac{1}{4}\log\frac{1}{4}=1.5\log2\)

\[ P(V,X)=\begin{cases} \frac{1}{2}, &V=0,X=-1\\ \frac{1}{2}, &V=-1,X=-1\\ \frac{1}{2}, &V=0,X=1\\ \frac{1}{2}, &V=1,X=1\\ 0, & \text{otherwise} \end{cases} \]

\(\therefore H(V|X)=\frac{1}{2}H(V|X=1)+\frac{1}{2}H(V|X=-1)=\log2\)

\(I(V;X)=H(V)-H(V|X)=0.5\log2\)

2.23¶

（a）

\[ \begin{aligned} \mathbf{P}=\begin{bmatrix} 1-p & \frac{p}{2} & \frac{p}{2}\\ \frac{p}{2} & 1-p & \frac{p}{2}\\ \frac{p}{2} & \frac{p}{2} & 1-p \end{bmatrix}\\ \begin{cases} \mathbf{P}^T\begin{bmatrix} p(0)\\ p(1)\\ p(2) \end{bmatrix}=\begin{bmatrix} p(0)\\ p(1)\\ p(2) \end{bmatrix}\\ p(0)+p(1)+p(2)=1 \end{cases} \end{aligned} \]

联立解得 \(p(0)=p(1)=p(2)=\frac{1}{3}\)

（b）

\[ \begin{aligned} H_{\infty}&=H(X|S)\\ &=\frac{1}{3}H(X|S=0)+\frac{1}{3}H(X|S=1)+\frac{1}{3}H(X|S=2)\\ &=H(1-p,\frac{p}{2},\frac{p}{2})\\ &=-(1-p)\log(1-p)-p\log\frac{p}{2} \end{aligned} \]

（c）当信源无记忆时，概率分布等于平稳分布，即 \(p=\frac{2}{3}\)

此时 \(H(X)=\log 3\)

对 \(H_{\infty}\) 求导可得 \(H'_{\infty}=-(-\log(1-p)-1)-\log\frac{p}{2}-1=\log\frac{2(1-p)}{p}=0\Rightarrow p=\frac{2}{3}\)

即 \(H_{\infty}\leq H(X)\)

（d）\(p=\frac{2}{3}\) 时取最大值，\(p=0\) 时 \(H_{\infty}=0\)，\(p=1\) 时 \(H_{\infty}=\log 2\)

2.25¶

（a）

\[ \begin{aligned} \begin{bmatrix} \mu_1\\ \mu_2 \end{bmatrix} =\begin{bmatrix} 1-p_{01} & p_{01}\\ p_{10} & 1-p_{10} \end{bmatrix}^T\begin{bmatrix} \mu_1\\ \mu_2 \end{bmatrix} \end{aligned} \]

解得 \(\mu_1=\frac{p_{10}}{p_{01}+p_{10}},\mu_2=\frac{p_{01}}{p_{01}+p_{10}}\)

\(\therefore H_{\infty}=H(X|S)=\frac{p_{10}}{p_{01}+p_{10}}H(1-p_{01},p_{01})+\frac{p_{01}}{p_{01}+p_{10}}H(1-p_{10},p_{10})\)

（b）由对称性，当 \(p_{01}=p_{10}=\frac{1}{2}\) 时熵最大

（c）即取 \(p_{01}=p,p_{10}=1\)

\(H_{\infty}=H(X|S)=\frac{1}{1+p}H(1-p,p)+\frac{p}{1+p}H(0,1)=-\frac{1}{1+p}[(1-p)\log(1-p)+p\log p]\)

（d）求导得：

\[ \begin{aligned} H'_{\infty}&=-\frac{(1+p)(-\log(1-p)-1+\log p+1)-(1-p)\log(1-p)-p\log p}{(1+p)^2}\\ &=-\frac{\log p-2\log(1-p)}{(1+p)^2}=0\\ &\Rightarrow p=(1-p)^2\Rightarrow p=\frac{3-\sqrt{5}}{2} \end{aligned} \]

（e）对于长度为 \(t\) 的序列，若该序列结尾为 0，则前 \(t-1\) 长度的序列末位可以为 0 / 1；若该序列结尾为 1，则前 \(t-1\) 长度的序列末位只能为 0，则前 \(t-2\) 长度的序列末位可以为 0 / 1，因此有递推式 \(N(t)=N(t-1)+N(t-2),N(1)=2,N(2)=3\)

\(\therefore N(t)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^{t+2}-(\frac{1-\sqrt{5}}{2})^{t+2}]\)

\(H=\lim\limits_{t\rightarrow\infty}\frac{1}{t}\log N(t)=\log\frac{1+\sqrt{5}}{2}\)