离散信号最大熵定理

对于离散信号，当所有信源符号出现的概率相等的时候取到最大的熵。

二元离散信号

对于二元离散信号的证明如下。

已知二元离散信号，概率为$(p,1-p)$。 信源熵为 $$ H(p) = -p\log p - (1-p)\log(1-p) $$

求导可以得到 $$\begin{align} \frac{\partial H(p)}{\partial p} =& -(1+\log p) + (1+\log(1-p)) \\ =& \log \frac{(1-p)}{p} > 0 \end{align}$$

可以得到在$p < \frac{1}{2}$时梯度为正，在$p > \frac{1}{2}$时梯度为负。

多元离散信号

对于多元离散信号的证明如下。 首先证明信息熵是一个凸函数，然后求解信息熵的最大值。

严格凸函数

要想证明信息熵是凸函数，相当于证明$H(\alpha P_1 + (1-\alpha)P_2) \geq \alpha H(P_1) + (1-\alpha)H(P_2)$

构建 $$\begin{align} & \alpha H(P_1) + (1-\alpha)H(P_2) - H(\alpha P_1 + (1-\alpha)P_2) \\ = & - \alpha\sum\limits_{i}p_1(x_i)\log p_1(x_i) - (1-\alpha)\sum\limits_{i}p_2(x_i)\log p_2(x_i) \\ & + \sum\limits_{i}(\alpha p_1(x_i)+(1-\alpha)p_2(x_i))\log (\alpha p_1(x_i)+(1-\alpha)p_2(x_i))\\ = & \alpha\sum\limits_{i}p_1(x_i)\log\frac{\alpha p_1(x_i)+(1-\alpha)p_2(x_i)}{p_1(x_i)} \\ & + (1-\alpha)\sum\limits_{i}p_2(x_i)\log\frac{\alpha p_1(x_i)+(1-\alpha)p_2(x_i)}{p_2(x_i)} \\ \leq & \alpha\log \sum\limits_{i}p_1(x_i)\frac{\alpha p_1(x_i)+(1-\alpha)p_2(x_i)}{p_1(x_i)} \\ & + (1-\alpha)\log \sum\limits_{i}p_2(x_i)\frac{\alpha p_1(x_i)+(1-\alpha)p_2(x_i)}{p_2(x_i)} \\ = & 0 \end{align}$$

所以 $\alpha H(P_1) + (1-\alpha)H(P_2) \leq H(\alpha P_1 + (1-\alpha)P_2)$ 得证。

考虑到Jensen不等式成立的条件为 $\forall i, \frac{\alpha p_1(x_i)+(1-\alpha)p_2(x_i)}{p_1(x_i)} = k$ 。 满足等号成立条件的有两种情况，即 $\alpha=1$ 或者 $p_1(X)=p_2(X)$ ，这与我们 $p_1(X) \neq p_2(X),0<\alpha<1$ 的假设不符合。

最大熵

已知多元离散信号，概率为 $p(x_i)$ ，并且满足约束条件 $\sum\limits_{i} p(x_i) = 1$ 。 使用Lagrange Multiplier方法，构建 $$ F = \sum\limits_{i}-p(x_i)\log p(x_i) - \lambda\left( \sum\limits_{i} p(x_i) - 1\right) $$

求导可以得到 $$\begin{align} \frac{\partial F}{\partial p(x_i)} =& -\log p(x_i) - 1 - \lambda = 0 \\ p(x_i) =& e^{ -\lambda - 1} \end{align}$$

已知$\sum\limits_{i} p(x_i) = 1$和$p(x_i) = e^{ -\lambda - 1}$可的$p(x_i) = \frac{1}{N}$。