由条件熵与无条件熵的关系引出的不等式证明题（不会抄答案系列）

• 枯燥预警，证明很繁琐，实际上尽力记住公式内涵即可，重点掌握詹森不等式。
• 选自《信息论（第四版）——基础理论与应用》傅祖芸编著$P68,2.15,2.16$，解答抄答案

• 写在前面：条件熵与无条件熵的关系为
  $$H(X_2/X_1)⩽H(X_2)$$
• 证明：
  在区域$[0,1]$中，设$f(x)=-xlogx$，它是区域内的 $\bigcap$ 型凸函数。并设$x_i=P(a_j/a_i)=p_{ij}$，而$P(a_i)=p_i$，有
  $$\sum _{i=1}^q{p}_i=1$$
  所以根据詹森不等式
  $$\sum _{i=1}^q{p}_{i}f(x_i)⩽f(\sum _{i=1}^q{p}_i{x}_i)$$
  得
  $$-\sum _{i=1}^q{p}_i{p}_{ij}log{p}_{ij}⩽-\sum _{i=1}^q{p}_i{p}_{ij}log(\sum _{i=1}^q{p}_i{p}_{ij})=-p_{j}log{p}_j\text{\hspace{1em}(1)}$$

$$\sum _{i=1}^q{p}_i{p}_{ij}=\sum _{i=1}^{q}P(a_i)P(a_j/a_i)=\sum _{i=1}^{q}P(a_i{a}_j)=P(a_j)=p_j$$

然后将式子$(1)$两边对所有 $j$ 求和，得
$$-\sum _{i=1}^q\sum _{j=1}^q{p}_i{p}_{ij}log{p}_{ij}⩽-\sum _{j=1}^q{p}_{j}log{p}_j$$
即

• 试证明离散平稳信源有$H(X_3/X_1{X}_2)⩽H(X_2/X_1)$，并说明等式成立条件。

• 证明：

1. 假设
   离散平稳信源输出的随机序列符号为$\cdots X_1,X_2,X_3,\cdots$。又设$x_1\in X_1,x_2\in X_2,x_3\in X_3$，而且$x_1,x_2,x_3$都取自于同一符号集 A = { a 1 , a 2 , ⋯   , a 3 } A= {a_1,a_2,cdots ,a_3} A={a1​,a2​,⋯,a3​}，并满足有
   $$\begin{gathered} \sum _{X_2}P(x_2/x_1)=1,\sum _{X_3}P(x_3/x_2)=1,\sum _{X_3}P(x_3/x_1{x}_2)=1 \\ \sum _{X_1}P(x_1)=\sum _{X_2}P(x_2)=\sum _{X_3}P(x_3)=1 \end{gathered}$$
   得到
   $$\begin{gathered} \sum _{X_1{X}_2}P(x_1{x}_2)=\sum _{X_2{X}_3}P(x_2{x}_3)=\sum _{X_1{X}_3}P(x_1{x}_3)=1 \\ \sum _{X_1{X}_2{X}_3}P(x_1{x}_2{x}_3)=1 \\ \sum _{X_1}P(x_1{x}_2{x}_3)=P(x_2{x}_3) \\ \sum _{X_2}P(x_1{x}_2{x}_3)=P(x_1{x}_3) \\ \sum _{X_3}P(x_1{x}_2{x}_3)=P(x_1{x}_2) \end{gathered}$$

• 方法一
  在区域$[0,1]$内设$f(x)=-xlogx,f(x)$在$[0,1]$内是$\bigcap$型凸函数，所以满足詹森不等式
  $$\begin{gathered} \sum _{i=1}^q{P}_{i}f(x_i)⩽f(\sum _{i=1}^q{P}_i{x}_i)其中\sum _{i=1}^q{P}_i=1 \\ 现今x_i=P(x_3/x_1{x}_2)，设其概率空间为P(x_1/x_2)，并满足 \\ \sum _{X_1}P(x_1/x_2)=1 \end{gathered}$$
  所以根据詹森不等式得
  $$\sum _{X_1}P(x_1/x_2)[-x_{i}log{x}_i]⩽-\left[\sum _{X_1}P(x_1/x_2)x_i\right]log\left[\sum _{X_1}P(x_1/x_2)x_i\right]$$

$x_i=P(x_3/x_1{x}_2)$

$$\begin{gathered} -\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)logP(x_3/x_1{x}_2) \\ ⩽-\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)log\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2) \end{gathered}$$

这里的所以非常的莫名奇妙，不等号直接跨到等号，我觉得可以直接得出

所以$$\begin{gathered} \sum _{X_1}P(x_1{x}_2{x}_3)=P(x_2{x}_3) \\ \sum _{X_1}P(x_1{x}_3/x_2)P(x_2)=P(x_3/x_2)P(x_2) \end{gathered}$$
上式对所有$x_1,x_2,x_3$的取值都成立，所以

直观感受这里把$P(X_2)$约去了

$$\sum _{X_1}P(x_1{x}_3/x_2)=P(x_3/x_2)$$

为什么不能直接写
$$\sum _{X_1}P(x_1{x}_2/x_3)=P(x_2/x_3)$$

即
$$\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)=P(x_3/x_2)$$

$$\sum _{X_1}P((x_1{x}_3)/x_2)=\sum _{X_1}P\left(\frac{((x_3/x_1)(x_1))}{x_2}\right)=\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)$$

所以$$-\sum _{X_1}P(x_1{x}_3/x_2)logP(x_3/x_1{x}_2)⩽-P(x_3/x_2)logP(x_3/x_2)$$

$$\begin{gathered} -\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)logP(x_3/x_1{x}_2) \\ ⩽-\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2)log\sum _{X_1}P(x_1/x_2)P(x_3/x_1{x}_2) \end{gathered}$$

因为$0⩽P(x_2)⩽1$，$x_2\in X_2$，所以上式两边相乘，等号不变，有
$$-\sum _{X_1}P(x_2)P(x_1{x}_3/x_2)logP(x_3/x_1{x}_2)⩽-P(x_2)P(x_3/x_2)logP(x_3/x_2)$$
上式对所有$x_2$、$x_3$都成立，所以对所有$x_2$，$x_3$求和下式也成立
$$-\sum _{X_1}\sum _{X_2}\sum _{X_3}P(x_1{x}_2{x}_3)logP(x_3/x_1{x}_2)⩽-\sum _{X_2}\sum _{X_3}P(x_2{x}_3)logP(x_3/x_2)$$
因为 $H(X_3/X_1{X}_2)⩽H(X_3/X_2)$
所以是平稳信源 $H(X_3/X_2)=H(X_2/X_1)$
所以$H(X_3/X_1{X}_2)⩽H(X_2/X_1)$
只有当 $P(x_3/x_1{x}_2)=p(x_3/x_2)$（对所有$x_1,x_2,x_3$）时等式成立。

• 方法二更变态，但好像更通用，太长写不下，放个链接

• 试证明离散平稳信源有$H(X_1{X}_2\cdots X_N)⩽H(X_1)+H(X_2)+\cdots +H(X_N)$，并说明等式成立条件。

• 解：
  设离散平稳信源输出的随机符号序列为$\cdots X_1{X}_2\cdots X_{N-1}{X}_N{X}_{N+1}\cdots$，又设$x_1\in X_1,x_2\in X_2,\cdots ,x_{N-1}\in X_{N-1},x_N\in X_N$，而且$x_1,x_2,\cdots x_{N-1},x_N$都取自于同一个符号集$A:|a_1,a_2,\cdots ,a_q|$，并满足有
  $$\begin{gathered} \sum _{X_i}\sum _{X_{i+1}}P(x_i{x}_{i+1})=1i=1,2,\cdots ,N \\ \sum _{X_i}\sum _{X_{i+1}}\sum _{X_{i+2}}P(x_i{x}_{i+1}{x}_{i+2})=1i=1,2,\cdots ,N \\ ⋮ \\ \sum _{X_1}\sum _{X_2}\cdots \sum _{X_N}P(x_1{x}_2\cdots x_{N-1}{x}_N)=1 \end{gathered}$$

这其实是两个系列的式子

$$\begin{gathered} \sum _{X_i}P(x_i{x}_{i+1})=P(x_{i+1})i=1,2,\cdots ,N \\ \sum _{X_i}\sum _{X_{i+1}}P(x_i{x}_{i+1}{x}_{i+2})=P(x_{i+2})i=1,2,\cdots ,N \\ ⋮ \\ \sum _{X_1}\sum _{X_2}\cdots \sum _{X_{N-1}}P(x_1{x}_2\cdots x_{N-1}{x}_N)=P(x_N) \end{gathered}$$
根据离平稳信源的信息熵的表达式有
$$\begin{gathered} H(X_1{X}_2\cdots X_{N-1}{X}_N)=H(X_1)+H(X_2/X_1)+ \\ H(X_3/X_1{X}_2)+H(X_N/X_1{X}_2\cdots X_{N-1}) \end{gathered}$$
根据上题$(2)$式，现设

？？？喵喵喵，还带这样玩？
$$-\sum _{i=1}^q{P}_{i}log{P}_i⩽-\sum _{i=1}^q{P}_{i}log{P_i}^{{}^{\prime }}\text{\hspace{1em}(2)}$$

$$\begin{gathered} P_i=P(x_2/x_1)其满足0⩽P_i⩽1,\sum _{X_2}P(x_2/x_1)=1 \\ {P_i}^{{}^{\prime }}=P(x_2)也满足0⩽P_i^{{}^{\prime }}⩽1,\sum _{X_2}P(x_2)=1 \end{gathered}$$
则有
$$-\sum _{X_2}P(x_2/x_1)logP(x_2/x_1)⩽-\sum _{X_2}P(x_2/x_1)logP(x_2)\text{\hspace{1em}(2)}$$
因为$P(x_1)>0$，所以上式两边相乘，等号不变。
$$-\sum _{X_2}P(x_1)P(x_2/x_1)logP(x_2/x_1)⩽-\sum _{X_2}P(x_1)P(x_2/x_1)logP(x_2)$$

$$P(x_1)P(x_2/x_1)=P(x_2{x}_1)$$

上式对所有 $x_1$ 的取值成立，所以对所有 $x_1$ 求和，下式成立
$$\begin{array}{rl}-\sum _{X_1}\sum _{X_2}P(x_2{x}_1)logP(x_2/x_1)⩽& -\sum _{X_1}\sum _{X_2}P(x_1{x}_2)logP(x_2)\\ ⩽& -\sum _{X_2}P(x_2)logP(x_2)\\ =& H(X_2)\end{array}$$
证得$H(X_2/X_1)⩽H(X_2)$
只有当 $P(x_2/x_1)=P(x_2)$，（对所有$x_1,x_2$）时等式成立。
同理，设$P(x_i)=P(x_3/x_1{x}_2)$其满足 $0⩽P_i⩽1,\sum _{X_3}P(x_3/x_1{x}_2)=1$
$${P_i}^{{}^{\prime }}=P(x_3)也满足0⩽P_i^{{}^{\prime }}⩽1,\sum _{X_3}P(x_3)=1$$

继续补充$(2)$式
$$-\sum _{i=1}^q{P}_{i}log{P}_i⩽-\sum _{i=1}^q{P}_{i}log{P_i}^{{}^{\prime }}\text{\hspace{1em}(2)}$$

则有$-\sum _{X_3}P(x_3/x_1{x}_2)logP(x_3/x_1{x}_2)⩽\sum _{X_3}P(x_3/x_1{x}_2)logP(x_3)$
因为 $P(x_1{x}_2)>0$，所以上式两边相乘，符号不变，得
$$\begin{gathered} -\sum _{X_3}P(x_1{x}_2)P(x_3/x_1{x}_2)logP(x_3/x_1{x}_2) \\ ⩽-\sum _{X_3}P(x_1{x}_2)P(x_3/x_1{x}_2)logP(x_3) \end{gathered}$$
上式对所有 $x_1,x_2$ 的取值都成立，所以有
$$\begin{array}{rl}& -\sum _{X_1}\sum _{X_2}\sum _{X_3}P(x_1{x}_2{x}_3)logP(x_3/x_1{x}_2)\\ & ⩽-\sum _{X_1}\sum _{X_2}\sum _{X_3}P(x_1{x}_2{x}_3)logP(x_3)\\ & =-\sum _{X_3}P(x_3)logP(x_3)\end{array}$$
$$\Rightarrow H(X_3/X_1{X}_2)⩽H(X_3)$$
只有当 $P(x_3/x_1{x}_2)=P(x_3)$ （对所有$x_1,x_2,x_3$）时等式成立
依此类推，对于所有 $H(X_N/X_1{X}_2\cdots X_{N-1})$ 同理可设
$$P_i=P(x_N/x_1{x}_2\cdots x_{N-1})$$
其满足 $0⩽P_i⩽1$，则有
$$\sum _{X_N}P(x_N/x_1{x}_2\cdots x_{N-1})=1$$
又设$P_i^{{}^{\prime }}=P(x_N)$，也满足$0⩽P_i^{{}^{\prime }}⩽1\sum _{X_N}P(x_N)=1$，则有
$$\begin{gathered} -\sum _{X_N}P(x_N/x_1{x}_2\cdots x_{N-1})logP(x_N/x_1{x}_2\cdots x_{N-1}) \\ ⩽-\sum _{X_N}P(x_N/x_1{x}_2\cdots x_{N-1})logP(x_N) \end{gathered}$$

再来一遍$(2)$式
$$-\sum _{i=1}^q{P}_{i}log{P}_i⩽-\sum _{i=1}^q{P}_{i}log{P_i}^{{}^{\prime }}\text{\hspace{1em}(2)}$$

因为 $P(x_1{x}_2\cdots x_{N-1})>0$，所以上式两边相乘，符号不变，得
$$\begin{gathered} -\sum _{X_N}P(x_1{x}_2\cdots x_{N-1})P(x_N/x_1{x}_2\cdots x_{N-1})logP(x_N/x_1{x}_2\cdots x_{N-1}) \\ ⩽-\sum _{X_N}P(x_1{x}_2\cdots x_{N-1})P(x_N/x_1{x}_2\cdots x_{N-1})logP(x_N) \end{gathered}$$
上式对所有 $x_1,x_2,\cdots ,x_{N-1}$ 的取值都成立，所以对 $x_1,x_2,\cdots ,x_{N-1}$ 求和，下式成立
$$\begin{array}{rl}& -\sum _{X_1}\sum _{X_2}\cdots \sum _{X_{N-1}}\sum _{X_N}P(x_1{x}_2\cdots x_{N-1}{x}_N)logP(x_N/x_1{x}_2\cdots x_{N-1})\\ & ⩽-\sum _{X_1}\sum _{X_2}\cdots \sum _{X_{N-1}}\sum _{X_N}P(x_1{x}_2\cdots x_{N-1}{x}_N)logP(x_N)\\ & =-\sum _{X_N}P(x_N)logP(x_N)\\ & =H(x_N)\end{array}$$
$$\Rightarrow H(X_N/X_1{X}_2\cdots X_{N-1})⩽H(X_N)$$
只有当 $P(x_N/x_1{x}_2\cdots x_{N-1})=P(x_N)$ （对所有$x_1,x_2,\cdots ,x_{N-1},x_N$）时等式成立。
由此可证得
$$\begin{array}{rl}& H(X_1{X}_2\cdots X_{N-1}{X}_N)\\ & =H(X_1)+H(X_2/X_1)+H(X_3/X_2{X}_1)+\cdots +H(X_N/X_1{X}_2\cdots X_{N-1})\\ & ⩽H(X_1)+H(X_2)+H(X_3)+\cdots +H(X_N)\end{array}$$
只有当下列等式对所有 $x_1,x_2,\cdots ,x_{N-1},x_N$
$$\begin{array}{cc}P(x_2/x_1)=P(x_2)& \\ P(x_3/x_1{x}_2)=P(x_3)& \\ ⋮& \\ P(x_N/x_1{x}_2\cdots x_{N-1})=P(x_N)& \end{array}\}$$
同时成立时，等式成立。
即只有当 $P(x_1{x}_2\cdots x_{N-1}{x}_N)=P(x_1)P(x_2)\cdots P(x_{N-1})P(x_N)$ 满足时，等式成立。
这就表明只有当离散信源输出的 $N$ 长的随机序列之间彼此统计无依赖时，等式成立。

最后

以上就是兴奋蜻蜓为你收集整理的由条件熵与无条件熵的关系引出的不等式证明题（不会抄答案系列）的全部内容，希望文章能够帮你解决由条件熵与无条件熵的关系引出的不等式证明题（不会抄答案系列）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。