東京工業大学 工学院 情報通信系 2018年8月実施 概率统计

标签：

• TITech
• Expectation-and-Variance

Author

思齐塾, 祭音Myyura

Description

S2.

$X$ と $Y$ をそれぞれ $M$ 個の実数値 $\{x_1, x_2, \dots, x_M\}$ と $N$ 個の実数値 $\{y_1, y_2, \dots, y_N\}$ のいずれかの値を取る確率変数とし、その同時確率分布を $P_{XY}$ によって、またその周辺分布を $P_X$ と $P_Y$ によって表す。ただし、 $M \ge 2, N \ge 2$ とし、 $P_{XY}(x_i, y_j) > 0 (i = 1, 2, \dots, M, j = 1, 2, \dots, N)$ とする。

1. エントロピー $H(X)$ 、条件付きエントロピー $H(Y|X)$ 、同時エントロピー $H(X, Y)$ 、相互情報量 $I(X; Y)$ を確率分布 $P_{XY}, P_X$ ならびに $P_Y$ を用いて書け。ただし、エントロピーの単位はビットとする。

2. 2 つの恒等式

$$H(X, Y) = H(X) + H(Y|X)$$

$$I(X; Y) = H(Y) - H(Y|X)$$

が成り立つことを示せ。

3. 実数値関数 $f$ は、任意の $\lambda \in [0, 1]$ と任意の正の実数 $x, y$ について

$$\lambda f(x) + (1 - \lambda)f(y) \le f(\lambda x + (1 - \lambda)y)$$

が成り立つとき、上に凸の関数であるという。関数 $f$ が上に凸の関数であるとき、任意の $M$ に対して

$$\sum_{i=1}^M P_X(x_i)f(z_i) \le f\left( \sum_{i=1}^M P_X(x_i)z_i \right)$$

が成り立つことを数学的帰納法を用いて証明せよ。ただし、 $z_1, z_2, \dots, z_M$ は任意の正の実数とする。

4. 3 つの不等式

$$0 \le H(X)$$

$$H(X) \le \log_2 M$$

$$H(Y|X) \le H(Y)$$

が成り立つことを証明せよ。 $\log_2 x$ が上に凸の関数であることに注意せよ。

题目描述

随机变量 $X$、$Y$ 分别取 $M$ 个实数值 $\{x_1,\ldots,x_M\}$ 和 $N$ 个实数值 $\{y_1,\ldots,y_N\}$，其中 $M,N\geq2$。用 $P_{XY}$ 表示联合分布，$P_X,P_Y$ 表示边缘分布，并假设

$$P_{XY}(x_i,y_j)>0 \quad (i=1,\ldots,M;\ j=1,\ldots,N).$$

1. 用 $P_{XY},P_X,P_Y$ 写出熵 $H(X)$、条件熵 $H(Y\mid X)$、联合熵 $H(X,Y)$ 和互信息 $I(X;Y)$；熵的单位取 bit。
2. 证明恒等式

$$H(X,Y)=H(X)+H(Y\mid X),$$

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

3. 若实函数 $f$ 对每个 $\lambda\in[0,1]$ 及任意正实数 $x,y$ 都满足

$$\lambda f(x)+(1-\lambda)f(y) \leq f\bigl(\lambda x+(1-\lambda)y\bigr),$$

则称 $f$ 为上凸函数。假设 $f$ 上凸，用数学归纳法证明对任意 $M$ 及任意正实数 $z_1,\ldots,z_M$，

$$\sum_{i=1}^MP_X(x_i)f(z_i) \leq f\!\left(\sum_{i=1}^MP_X(x_i)z_i\right).$$

4. 注意到 $\log_2x$ 是上凸函数，证明

$$0\leq H(X),\qquad H(X)\leq\log_2M,\qquad H(Y\mid X)\leq H(Y).$$

Kai

S2

以下， $p_{ij}=P_{XY}(x_i,y_j)$ , $p_i=P_X(x_i)$ , $q_j=P_Y(y_j)$ と略記する。仮定よりこれらは正である。

1)

ビットを単位とする各量は

$$\boxed{H(X)=-\sum_{i=1}^{M}p_i\log_2p_i},$$

$$\boxed{H(Y\mid X)=-\sum_{i=1}^{M}\sum_{j=1}^{N}p_{ij} \log_2\frac{p_{ij}}{p_i}},$$

$$\boxed{H(X,Y)=-\sum_{i=1}^{M}\sum_{j=1}^{N}p_{ij}\log_2p_{ij}},$$

$$\boxed{I(X;Y)=\sum_{i=1}^{M}\sum_{j=1}^{N}p_{ij} \log_2\frac{p_{ij}}{p_iq_j}}.$$

2)

$\log(p_{ij}/p_i)=\log p_{ij}-\log p_i$ と周辺化 $\sum_jp_{ij}=p_i$ を使えば

$$\begin{aligned} H(X)+H(Y\mid X) &=-\sum_i p_i\log_2p_i -\sum_{i,j}p_{ij}(\log_2p_{ij}-\log_2p_i)\\ &=-\sum_{i,j}p_{ij}\log_2p_{ij}=H(X,Y). \end{aligned}$$

また

$$\begin{aligned} H(Y)-H(Y\mid X) &=-\sum_jq_j\log_2q_j +\sum_{i,j}p_{ij}\log_2\frac{p_{ij}}{p_i}\\ &=\sum_{i,j}p_{ij}\log_2\frac{p_{ij}}{p_iq_j} =I(X;Y). \end{aligned}$$

よって二つの恒等式が示された。

3)

重みを $p_i=P_X(x_i)$ と書く。 $M=1$ は等号であり， $M=2$ は上に凸の定義そのものである。ある $M$ で成立すると仮定し， $M+1$ 個の正の重みについて

$$q=\sum_{i=1}^{M}p_i=1-p_{M+1}\quad(0<q<1),\qquad \bar z=\sum_{i=1}^{M}\frac{p_i}{q}z_i$$

とおく。帰納法の仮定と二点に対する凸性から

$$\begin{aligned} \sum_{i=1}^{M+1}p_if(z_i) &=q\sum_{i=1}^{M}\frac{p_i}{q}f(z_i)+p_{M+1}f(z_{M+1})\\ &\le qf(\bar z)+p_{M+1}f(z_{M+1})\\ &\le f(q\bar z+p_{M+1}z_{M+1})\\ &=f\left(\sum_{i=1}^{M+1}p_iz_i\right). \end{aligned}$$

したがって数学的帰納法により任意の $M$ で主張が成り立つ。

4)

各 $p_i\in(0,1]$ なので $-\log_2p_i\ge0$ であり，直ちに

$$\boxed{0\le H(X)}$$

を得る。

次に 3) を上に凸な $\log_2$ と $z_i=1/p_i$ に適用すると

$$H(X)=\sum_ip_i\log_2\frac1{p_i} \le\log_2\left(\sum_ip_i\frac1{p_i}\right) =\boxed{\log_2M}.$$

最後に相互情報量の非負性を同じ不等式で示す。 $\log_2$ の上への凸性より

$$\begin{aligned} -I(X;Y) &=\sum_{i,j}p_{ij}\log_2\frac{p_iq_j}{p_{ij}}\\ &\le\log_2\left(\sum_{i,j}p_{ij}\frac{p_iq_j}{p_{ij}}\right) =\log_2\left(\sum_{i,j}p_iq_j\right)=0. \end{aligned}$$

ゆえに $I(X;Y)\ge0$ 。2) の恒等式 $I(X;Y)=H(Y)-H(Y\mid X)$ から

$$\boxed{H(Y\mid X)\le H(Y)}$$

が従う。