summaryrefslogtreecommitdiff
path: root/macros/latex/contrib/thucoursework/ithw.tex
blob: 053257193d4c787a4ed1f2bb88aac780ab507a07 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
% 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: