信息论

对数是凹函数，因此「平均而言」它位于其切线下方。吉布斯不等式正是将詹森不等式应用于凹函数 $\log_2$（以 $p$ 加权）：它表明，若在对数内部把每个比值 $q_i/p_i$ 替换为其 $p$-加权平均值（恰好等于 $1$），只会使总和增大，从而迫使该散度必须非负。

从对所有 $x > 0$ 成立的初等不等式 $\ln x \le x - 1$ 出发，等号仅在 $x=1$ 处成立（这是因为 $f(x) = \ln x - (x-1)$ 满足 $f(1)=0$，$f'(x) = 1/x - 1$，当 $x<1$ 时为正、当 $x>1$ 时为负，故 $f$ 在 $x=1$ 处有唯一的最大值）。两边除以 $\ln 2$ 得到 $\log_2 x \le (x-1)/\ln 2$。

对每个 $i$ 令 $x = q_i/p_i$ 应用此式：$\log_2(q_i/p_i) \le (q_i/p_i - 1)/\ln 2$。两边乘以 $p_i > 0$（不改变不等号方向）并对 $i$ 求和：$\sum_i p_i \log_2(q_i/p_i) \le \frac{1}{\ln 2}\sum_i (q_i - p_i) = \frac{1}{\ln 2}\left(\sum_i q_i - \sum_i p_i\right) = \frac{1}{\ln 2}(1 - 1) = 0$，因为 $p$ 与 $q$ 都是和为 $1$ 的概率分布。

左边恰好是 $-D(p\|q)$（注意对数内是 $q_i/p_i$ 而非 $p_i/q_i$ 所带来的符号翻转），因此这就证明了 $D(p\|q) \ge 0$。

处处等号成立要求对每个满足 $p_i > 0$ 的 $i$，$\ln x \le x-1$ 都取等号，而这仅当所有这样的 $i$ 都满足 $q_i/p_i = 1$ 时才会发生，即 $p = q$。

下界表明熵是一个坚硬的底线：任何无损前缀码平均而言都无法优于每个符号 $H(X)$ 比特，因为做得更好就要求编码所诱导的分布以吉布斯不等式所禁止的方式偏离 $X$ 的真实分布。上界表明这个底线几乎可以达到：把每个理想长度 $-\log_2 p_i$ 向上取整为整数，平均浪费不到一比特。

对于下界，设 $l_i$ 为任意前缀码的长度，则 $\sum_{i=1}^n 2^{-l_i} \le 1$ 成立。令 $q_i = 2^{-l_i}/Z$，其中 $Z=\sum_j 2^{-l_j} \le 1$，于是 $q$ 是一个概率分布。由吉布斯不等式，$0 \le D(p\|q) = \sum_i p_i \log_2(p_i/q_i) = \sum_i p_i\log_2 p_i - \sum_i p_i \log_2(2^{-l_i}/Z) = -H(X) + \sum_i p_i l_i + \log_2 Z$。由于 $Z \le 1$，故 $\log_2 Z \le 0$，因此 $0 \le -H(X) + L + \log_2 Z \le -H(X) + L$，整理即得 $L \ge H(X)$。

对于上界（可达性），对每个 $i$ 选取 $l_i = \lceil -\log_2 p_i \rceil$（将理想长度向上取整为最近的整数）。这些长度满足克拉夫特不等式，因为 $2^{-l_i} \le 2^{-(-\log_2 p_i)} = p_i$，所以 $\sum_i 2^{-l_i} \le \sum_i p_i = 1$；根据 Kraft–McMillan 构造，这样的长度总能实现为一个真正的前缀码（在二叉树中逐层分配二进制串来构造编码）。

由向上取整的定义，$l_i < -\log_2 p_i + 1$。乘以 $p_i \ge 0$ 并对 $i$ 求和得到 $L = \sum_i p_i l_i < \sum_i p_i(-\log_2 p_i + 1) = H(X) + 1$。

结合两部分，这一构造达到了 $H(X) \le L < H(X) + 1$。

容量不仅仅是一个方便的公式——它是一堵真实存在的墙。低于它时，把每条消息展开到足够长的分组上，可以让看似随机的码字在噪声中依然可区分，从而把错误率降到零；高于它时，无论编码多么巧妙，信道破坏信息的速度都快于任何编码所能保护的速度。

**逆定理（$R > C \Rightarrow P_e \not\to 0$）。** Fano 不等式限制了在给定有噪输出的情况下，接收方对消息剩余的不确定性：$H(X\mid Y) \le 1 + P_e \log_2(n-1)$，其中 $n$ 是可能消息的个数。同时，信道的数据处理结构迫使每次使用都满足 $I(X;Y) \le C$，因此在 $N$ 次信道使用组成的一个分组上，接收方能提取的总信息至多为 $NC$ 比特。若真实速率 $R > C$（每次使用），则消息携带 $NR$ 比特的熵，但信道大约只能提供其中 $NC < NR$ 比特；此时 Fano 不等式迫使 $P_e$ 在 $N$ 增大时始终远离 $0$，因为剩余的不确定性 $H(X\mid Y)$ 无法被消除。

**可达性概述（$R < C \Rightarrow P_e \to 0$）。** 固定一个能达到容量的输入分布 $p(x)$，从 $p(x)^N$ 中独立随机生成 $2^{NR}$ 个长度为 $N$ 的码字，构成码本。解码时，接收方寻找与接收序列联合典型（即统计模式表现得像真正的输入-输出对）的唯一码字。由于 $R < C$，候选码字数（$2^{NR}$）远小于统计上可区分的信道输出数（$\approx 2^{NC}$），因此当 $N \to \infty$ 时，某个未发送的其他码字恰好与接收序列联合典型的概率会缩小到 $0$，平均到码本的随机选择上，解码错误概率也随之缩小——因此至少存在一个码本能达到任意小的 $P_e$。