% Homework template for Inference and Information % UPDATE: September 26, 2017 by Xiangxiang \documentclass[a4paper]{article} \usepackage{ctex} \ctexset{ proofname = \heiti{证明} } \usepackage{amsmath, amssymb, amsthm} % amsmath: equation*, amssymb: mathbb, amsthm: proof \usepackage{moreenum} \usepackage{mathtools} \usepackage{url} \usepackage{bm} \usepackage{enumitem} \usepackage{graphicx} \usepackage{subcaption} \usepackage{booktabs} % toprule \usepackage[mathcal]{eucal} \usepackage[thehwcnt = 1]{iidef} \thecourseinstitute{清华大学深圳研究生院} \thecoursename{应用信息论} \theterm{2018年春季学期} \hwname{作业} \slname{\heiti{解}} \begin{document} \courseheader \name{YOUR NAME} \begin{enumerate} \setlength{\itemsep}{3\parskip} \item 设$X$和$Y$是各有均值$m_x,m_y$,方差为$\sigma_x^2,\sigma_y^2$,且相互独立的高斯随机变量,已知$U=X+Y,V=X-Y$。试求$I(U;V)$。 \begin{solution} $U,V$的联合分布是均值为$[\mu_x+\mu_y,\mu_x-\mu_y]$,协方差矩阵为 $$\Lambda_{U,V}=\begin{bmatrix} 1 & 1\\ 1 & -1\\ \end{bmatrix} \begin{bmatrix} \sigma_x^2 & 0\\ 0 & \sigma_x^2\\ \end{bmatrix} \begin{bmatrix} 1 & 1\\ 1 & -1\\ \end{bmatrix}^T =\begin{bmatrix} \sigma_x^2+\sigma_y^2 & \sigma_x^2-\sigma_y^2\\ \sigma_x^2-\sigma_y^2 & \sigma_x^2+\sigma_y^2\\ \end{bmatrix} $$ 由多元高斯分布微分熵的公式 $$ h(U)=\frac{1}{2}\log ((2\pi e)^2 |\Lambda_{U,V}|)=\frac{1}{2}\log(16\pi^2 e^2 \sigma^2_x\sigma^2_y) $$ $U|V=v$也是高斯分布,方差为$\frac{4\sigma_x^2\sigma_y^2}{\sigma_x^2+\sigma_y^2}$,与$v$无关,因此 $$ h(U|V)=\E_{V}[h(U|V=v)]=\frac{1}{2}\log(2\pi e \frac{4\sigma_x^2\sigma_y^2}{\sigma_x^2+\sigma_y^2})\Rightarrow $$ \begin{align*} I(U;V)=& h(U)-h(U|V)\\ =&\frac{1}{2}\log(16\pi^2 e^2 \sigma^2_x\sigma^ 2_y)-\frac{1}{2}\log(2\pi e \frac{4\sigma_x^2\sigma_y^2}{\sigma_x^2+\sigma_y^2})\\ =&\frac{1}{2}\log(2\pi e (\sigma_x^2+\sigma_y^2)) \end{align*} %$$ %p(u,v)=\frac{1}{4\pi \sigma_x\sigma_y}\exp(-\frac{(\frac{u+v}{2}-\mu_x)^2+(\frac{u+v}{2}-\mu_y)^2}{2}) %$$ \end{solution} \item 设有随机变量$X,Y,Z$均取值于$\{0,1\}$,已知$I(X;Y)=0,I(X;Y|Z)=1$。求证$H(Z)=1,H(X,Y,Z)=2$ \begin{proof} $I(X;Y|Z)=H(X|Z)-H(X|Y,Z)\leq H(X|Z)\leq H(X)\leq \log(2)=1$ 所以等号全都成立$\Rightarrow X\sim B(\frac{1}{2})$。 同理可知$Y\sim B(\frac{1}{2})$。 另外$H(Y|Z)=H(Y)\Rightarrow I(Y;Z)=0\Rightarrow H(Z|Y)=H(Z)$ \begin{align*} &H(X|Y,Z)=0 \\ \iff &H(X,Y,Z)=H(Y,Z)\\ \iff &H(X,Y)+H(Z|X,Y)=H(Y)+H(Z|Y)\\ \iff &2+H(Z|X,Y)=1+H(Z)\\ \iff &H(Z)=1+H(Z|X,Y) \end{align*} 由上式推出$H(Z)\geq 1$,又$H(Z)\leq 1\Rightarrow H(Z)=1\Rightarrow H(X,Y,Z)=2$ \end{proof} \item 设有信号$X$经过处理器$A$后获输出$Y$,$Y$再经处理器$B$后获输出$Z$。已知处理器$A$和$B$ 分别独立处理$X$和$Y$。试证:$I(X;Z)\leq I(X;Y)$ \begin{proof} $I(X;Z)=H(Z)-H(Z|X)=H(Z);I(Y;Z)=H(Y)$因为$Z$是$Y$的函数$\Rightarrow H(Z)\leq H(Y) \Rightarrow I(X;Z)\leq I(X;Y)$ \end{proof} \item 已知随机变量$X$和$Y$的联合概率密度$p(a_k,b_j)$满足 $$ p(a_1)=\frac{1}{2},p(a_2)=p(a_3)=\frac{1}{4},p(b_1)=\frac{2}{3},p(b_2)=p(b_3)=\frac{1}{6} $$ 试求能使$H(X,Y)$取得最大值的联合概率密度分布。 \begin{solution} $H(X,Y)=H(X)+H(Y)-I(X;Y)\leq H(X)+H(Y)=\frac{7}{6}+\log 3$ 等号成立当且仅当$X,Y$相互独立$\Rightarrow p(x,y)=p(x)p(y)$ \end{solution} \item 设随机变量$X,Y,Z$满足$p(x,y,z)=p(x)p(y|x)p(z|y)$。求证$I(X;Y)\geq I(X;Y|Z)$ \begin{proof} 因为$p(x,y,z)=p(x)p(y|x)p(z|y,x)\Rightarrow p(z|y,x)=p(z|x)\Rightarrow x$ 与$z$关于$y$条件独立$\Rightarrow I(X;Y|Z)=H(X|Z)-H(X|Y,Z)= H(X|Z)-H(X|Y)\leq H(X)-H(X|Y) =I(X;Y)$ \end{proof} \item 求证$I(X;Y;Z)=H(X,Y,Z)-H(X)-H(Y)-H(Z)+I(X;Y)+I(Y;Z)+I(Z;X)$,其中 $I(X;Y;Z)\triangleq I(X;Y)-I(X;Y|Z)$ \begin{proof} \begin{align*} I(X;Y;Z) =& I(X;Y)-I(X;Y|Z) \\ =& H(X)+H(Y)-H(X,Y)-(H(X|Z)-H(X|Y,Z))\\ =& H(X)+H(Y)-H(X,Y)-(H(X,Z)-H(Z))+H(X,Y,Z)-H(Y,Z)\\ =& H(X,Y,Z)-H(X)-H(Y)-H(Z)+(H(X)+H(Y)-H(X,Y))\\ +&(H(Y)+H(Z)-H(Y,Z))+(H(Z)+H(X)-H(X,Z))\\ =& H(X,Y,Z)-H(X)-H(Y)-H(Z)+I(X;Y)+I(Y;Z)+I(Z;X) \end{align*} \end{proof} \item 令$p=(p_1,p_2,\dots,p_a)$是一个概率分布,满足$p_1\geq p_2\geq \dots p_a$,假设$\epsilon >0 $使得$p_1-\epsilon \geq p_2+\epsilon$成立,证明:$H(p_1,p_2,\dots,p_a) \leq H(p_1-\epsilon,p_2+\epsilon,p_3,\dots,p_a)$ \begin{proof} 设$f(\epsilon)=(p_1-\epsilon)\log(p_1-\epsilon)+(p_2+\epsilon)\log(p_2+\epsilon)$ 由已知$0\leq \epsilon \frac{p_2-p_1}{2}$ $f'(\epsilon)=\log\frac{p_2+\epsilon}{p_1-\epsilon}\leq 0$ $\Rightarrow f(\epsilon)\leq f(0)\Rightarrow H(p_1,p_2,\dots,p_a)\leq H(p_1-\epsilon,p_2+\epsilon,p_3,\dots,p_a)$ \end{proof} \item 设$p_i(x)\sim N(\mu_i,\sigma_i^2)$,试求相对熵$D(p_2||p_1)$ \begin{solution} \begin{align*} D(p_2||p_1)=& \int_{\mathbb{R}} p_2(x) \log \frac{p_2(x)}{p_1(x)}dx\\ =& \int_{\mathbb{R}} p_2(x) \left(\log \frac{\sigma_1^2}{\sigma_2^2}+\frac{1}{2}((x-\mu_1)^2-(x-\mu_2)^2)\log e\right)dx\\ =& 2\log \frac{\sigma_1}{\sigma_2}+\frac{1}{2}(\mu_1^2-\mu_2^2)\log e+(\mu_2-\mu_1)\mu_2\log e\\ =& 2\log \frac{\sigma_1}{\sigma_2}+\frac{1}{2}(\mu_1-\mu_2)^2\log e \end{align*} \end{solution} \item 若$f(x)$分别是区间$(0,0.01),(0,0.5),(0,1),(0,2),(0,5)$上均匀分布的分布函数,计算$f(x)$的微分熵。 \begin{solution} 设$U_t$是$(0,t)$上的均匀分布,则$h(U_t)=\log t$ \begin{itemize} \item $h(U_{0.01})=\log 0.01$ \item $h(U_{0.5})=-1$ \item $h(U_{1})=0$ \item $h(U_{2})=1$ \item $h(U_{5})=\log 5$ \end{itemize} \end{solution} \item 设 \begin{align*} p_1(x,y)=& \frac{1}{2\pi \sigma_x\sigma_y}\exp[-\frac{1}{2}(\frac{x^2}{\sigma_x^2}+\frac{y^2}{\sigma_y^2})]\\ p_2(x,y)=& \frac{1}{2\pi \sigma_x\sigma_y\sqrt{1-\rho^2}}\exp[-\frac{1}{2(1-\rho^2)}(\frac{x^2}{\sigma_x^2}-2\rho\frac{xy}{\sigma_x\sigma_y}+\frac{y^2}{\sigma_y^2})] \end{align*} 试求$D(p_2||p_1)$和$I(X;Y)$,其中$X,Y\sim p_2$ \begin{solution} \begin{align*} D(p_2||p_1) = & \iint_{\mathbb{R}^2} p_2(x,y)\log \frac{p_2(x,y)}{p_1(x,y)}dxdy \\ -&\frac{1}{2}\log(1-\rho^2)\\ -&\frac{1}{2}(\log e)\iint_{\mathbb{R}^2} p_2(x,y)\left[\frac{\rho^2 x^2}{\sigma_x^2(1-\rho^2)}+\frac{\rho^2 y^2}{\sigma_y^2(1-\rho^2)}-\frac{2\rho xy}{(1-\rho^2)\sigma_x\sigma_y}\right]dxdy\\ =&-\frac{1}{2}\log(1-\rho^2) \end{align*} $X|Y=y$服从高斯分布,方差为$(1-\rho^2)\sigma_x^2$ \begin{align*} I(X;Y) = & h(X)-h(X|Y)\\ = & \frac{1}{2}\log(2\pi e \sigma_x^2) - \frac{1}{2}\log(2\pi e \sigma_x^2(1-\rho^2))\\ = & \frac{1}{2}\log(\frac{2\pi e}{1-\rho^2}) \end{align*} \end{solution} \end{enumerate} \end{document} \begin{equation} \end{equation} %%% Local Variables: %%% mode: late\rvx %%% TeX-master: t %%% End: