14.1.1 从概率分布到熵
设离散随机变量 \(X\) 取值于有限字母表 \(\mathcal X\)，其概率质量函数为 \(p(x)\)。本节的对数均以 \(2\) 为底，单位为比特；约定 \(0\log_2 0=0\)。先把概率为零的符号删去，不影响分布与编码问题。以下定义依赖整个概率分布，不能只凭某一次观察是否出人意料来判断。
条件熵是各条件分布的熵再对 \(Y\) 取平均。把联合概率写成 \(p(x,y)=p(y)p(x\mid y)\)，代入定义并拆开对数，得到链式公式 \(H(X,Y)=H(Y)+H(X\mid Y)\)。重复这一计算可得 \(H(X_1,\ldots,X_n)=\sum_{j=1}^nH(X_j\mid X_1,\ldots,X_{j-1})\)。
二元分布的熵记为 \(h_2(p)=-p\log_2p-(1-p)\log_2(1-p)\)。在 \(0<p<1\) 上，\(h_2'(p)=\log_2((1-p)/p)\)，故它在 \(p=1/2\) 处达到最大值 \(1\)，而在确定性分布 \(p=0,1\) 处为零。
14.1.2 相对熵非负与数据处理
若存在 \(p(x)>0=q(x)\)，则相对熵为 \(+\infty\)。相对熵也称 Kullback–Leibler 散度，通常不对称，因此不能把它当作满足对称性与三角不等式的距离。
存在上述零概率冲突时，非负性显然。否则用自然对数的基本不等式 \(-\ln u\ge1-u\)，有
等号要求每个正概率点上 \(q(x)=p(x)\)，同时 \(Q\) 在其余点无质量，故 \(D(P\Vert Q)=0\) 当且仅当 \(P=Q\)。令 \(Q\) 为 \(m\) 个符号上的均匀分布，又得 \(H(X)\le\log_2m\)，等号恰在均匀分布成立。
将互信息的对数拆开可得 \(I(X;Y)=H(X)-H(X\mid Y)\)。因此条件熵平均而言不超过原熵；这不是对每一个条件取值都成立的逐点比较。互信息为零等价于 \(X,Y\) 独立。进一步定义条件互信息为各条件联合分布的相对熵对条件变量取平均，于是 \(I(X;Y\mid Z)\ge0\)。链式公式给出
若 \(X\to Y\to Z\) 构成马尔可夫链，即给定 \(Y\) 后 \(X,Z\) 条件独立，则 \(I(X;Z)\le I(X;Y)\)。证明只需在上式中令 \(I(X;Z\mid Y)=0\)，再利用 \(I(X;Y\mid Z)\ge0\)。这里允许 \(Z\) 是对 \(Y\) 的随机处理，条件是处理过程中不额外读取 \(X\)。
令 \(X\) 为均匀二元变量，\(Y=X\oplus N_1\)、\(Z=Y\oplus N_2\)，其中 \(N_1,N_2\) 与 \(X\) 相互独立，且均为参数 \(0.1\) 的伯努利变量。\(Y,Z\) 仍均匀，故 \(I(X;Y)=1-h_2(0.1)\approx0.5310\)。两次翻转的总错误率为恰有一次翻转的概率 \(0.1\times0.9+0.9\times0.1=0.18\)，所以 \(I(X;Z)=1-h_2(0.18)\approx0.3199\)，满足数据处理不等式。
14.1.3 前缀码与平均码长
二元前缀码（prefix code）把每个符号映为有限比特串，且任一码字都不是另一码字的前缀。这样连续读取一串码字时，一旦到达一个码字末端，就能立即辨认该符号。设各码长为非负整数 \(\ell_i\)，平均码长为 \(L=\sum_i p_i\ell_i\)。
前缀码的长度满足 \(K=\sum_i2^{-\ell_i}\le1\)。反之，有限个非负整数若满足此式，就存在相应长度的二元前缀码。
长度为 \(\ell\) 的比特串对应 \([0,1)\) 内一个长 \(2^{-\ell}\) 的半开二进制区间。一个串是另一个的前缀，当且仅当对应区间包含后者；前缀码的这些区间两两不交，总长度至多为 \(1\)。反向构造时，先按长度从短到长排序，把区间依次紧邻排列。放置长度 \(2^{-\ell_j}\) 的第 \(j\) 个区间前，已占长度是 \(2^{-\ell_j}\) 的整数倍，因为前面各 \(\ell_i\le\ell_j\)。所以新起点恰在对应的二进制网格上。总长不超过 \(1\)，所有区间都能放入；读取其二进制前缀便得到所需码。
令 \(q_i=2^{-\ell_i}/K\)，这是一个概率分布。直接计算可得
另一方面，对每个正概率符号取 \(\ell_i=\lceil-\log_2p_i\rceil\)，则 \(\sum_i2^{-\ell_i}\le\sum_i p_i=1\)。Kraft 逆命题保证码存在，而 \(\ell_i<-\log_2p_i+1\)，所以存在前缀码使 \(H(X)\le L<H(X)+1\)。该上界是存在性结论，不是每个前缀码都满足。若只有一个可能符号，可以用空串，码长为零。
对图中的四个符号，\(H(X)=\tfrac12\cdot1+\tfrac14\cdot2+2\cdot\tfrac18\cdot3=1.75\) 比特。前缀码 \(0,10,110,111\) 的平均码长同样为 \(1.75\)，因此达到最优。四个符号若统一用两位编码，平均码长则为 \(2\)。差异来自符号的概率不均匀，不需要符号之间存在相关性。
14.1.4 典型集为何决定编码速率
现在令 \(X_1,X_2,\ldots\) 为有限字母表上的 iid 序列。由强大数定律，随机变量 \(-\log_2p(X_i)\) 的样本平均几乎必然趋于其期望 \(H(X_1)\)。独立性又使联合概率为乘积，因此
式中 \(P(X_1,\ldots,X_n)\) 表示联合概率质量函数在随机样本处的值。这个结论称为渐近均分性质（asymptotic equipartition property，AEP）。记 \(H=H(X_1)\)，把满足 \(|-n^{-1}\log_2p(x^n)-H|\le\varepsilon\) 的序列组成典型集 \(T_{n,\varepsilon}\)。其概率趋于 \(1\)，且其中每个序列的概率位于 \(2^{-n(H+\varepsilon)}\) 与 \(2^{-n(H-\varepsilon)}\) 之间。把这些概率相加，得到在 \(n\) 足够大时
每个长度为 \(n\) 的样本块若允许使用至多 \(2^{\lfloor nR\rfloor}\) 个码字，则任何 \(R>H\) 都能使解码错误概率趋于零；若 \(R<H\)，任意这样的编码的正确概率都趋于零。
当 \(R>H\) 时，取 \(\varepsilon>0\) 使 \(H+\varepsilon<R\)。足够大的 \(n\) 下，码字数多于典型集大小，可为每个典型序列分配一个码字；非典型序列任意编码。解码错误概率至多为非典型集的概率，因而趋零。当 \(R<H\) 时，取 \(\varepsilon>0\) 使 \(R<H-\varepsilon\)。任何码最多正确恢复 \(2^{\lfloor nR\rfloor}\) 个序列，其中典型序列的总概率至多为 \(2^{nR}2^{-n(H-\varepsilon)}\to0\)，非典型部分的概率也趋于零，故结论成立。边界 \(R=H\) 的行为不由这段严格不等式的论证决定。
这里允许小概率解码错误。另一个问题是变长前缀码要求每个样本块都无误解码：对整块应用上一节的界，并用独立性得 \(H(X_1,\ldots,X_n)=nH\)，便有某个块前缀码满足 \(H\le L_n/n<H+1/n\)。必须区分定长与变长、错误概率趋零与零错误，才能正确解释“压缩到熵”。
14.1.5 连续变量的边界
有密度 \(f\) 的实随机变量可以定义微分熵 \(h(X)=-\int f(x)\log_2 f(x)\,dx\)，前提是积分有定义。它与离散熵的性质并不完全一致。例如 \(X\sim\operatorname{Unif}(0,a)\) 时，\(h(X)=\log_2a\)，在 \(a<1\) 时为负；把测量单位改变，相当于乘以常数，也会改变微分熵。
有限比特串只有可数多个，不能逐一表示连续分布的全部实数取值。实际编码须规定量化精度或失真标准。微分熵可参与量化极限的计算，但负微分熵不意味着负码长。对一般分布，相对熵仍可利用拉东—尼科迪姆导数定义；本节有限字母证明避免了积分存在性与无穷大相减的问题。
14.1.6 习题与解答
习题 14.1-1 · 伯努利分布的相对熵
令 \(P=\operatorname{Bernoulli}(1/4)\)，\(Q=\operatorname{Bernoulli}(1/2)\)。求 \(D(P\Vert Q)\) 与 \(D(Q\Vert P)\)，并判断它们是否相等。
第一项为 \(1-h_2(1/4)\approx0.188722\)。反方向为 \(\tfrac12\log_2 2+\tfrac12\log_2(2/3)=\tfrac12\log_2(4/3)\approx0.207519\)。两者都非负但不相等。如果改用只在 \(0\) 上有质量的 \(Q\)，原来的 \(P\) 在 \(1\) 上仍有正概率，因而 \(D(P\Vert Q)=+\infty\)。
习题 14.1-2 · 条件熵为何必须取平均
设 \(P(Y=1)=0.2\)，给定 \(Y=1\) 时 \(X\) 在 \(0,1\) 上均匀，给定 \(Y=0\) 时 \(X=0\)。计算原熵、两个条件熵及互信息。
全概率公式给出 \(P(X=1)=0.2\times0.5=0.1\)，故 \(H(X)=h_2(0.1)\approx0.468996\)。但 \(H(X\mid Y=1)=1\)，大于原熵；另一条件下为零。因此 \(H(X\mid Y)=0.2\)，而 \(I(X;Y)=0.468996-0.2=0.268996\)。该例否定逐点的“条件越多熵越小”，同时符合平均意义的不等式。
习题 14.1-3 · 码长能否实现
三符号码长 \((1,1,2)\) 能否由前缀码实现？对于三个等概率符号，构造码长 \((1,2,2)\) 的码并比较其平均码长与熵。
第一组的 Kraft 和为 \(1/2+1/2+1/4=5/4>1\)，不可能。第二组 Kraft 和为 \(1\)，例如码字 \(0,10,11\)。平均码长 \(L=5/3\approx1.666667\)，而熵为 \(\log_2 3\approx1.584963\)，差约 \(0.081704\)。整数码长约束使这个单符号编码无法恰好达到熵。
习题 14.1-4 · 固定速率的可达与不可达
对 iid 参数 \(1/4\) 的伯努利信源，证明每符号 \(0.9\) 比特可实现错误概率趋零，而每符号 \(0.7\) 比特时正确概率趋零。
熵为 \(H=h_2(1/4)\approx0.811278\)。取 \(\varepsilon=0.04\)。典型集至多含 \(2^{0.851278n}\) 个序列，小于足够大 \(n\) 时的 \(2^{\lfloor0.9n\rfloor}\)，故能逐一编码。若速率为 \(0.7\)，正确恢复的典型序列总概率至多为 \(2^{0.7n}2^{-0.771278n}=2^{-0.071278n}\)。再加上趋零的非典型概率，正确概率仍趋零。两部分都直接来自强大数定律定义的典型集。
关键术语
- 熵与条件熵：平均自信息及条件分布的平均熵。
- 相对熵：比较概率分布的非负散度，允许无穷大。
- 互信息：联合分布相对边缘乘积分布的相对熵。
- 数据处理不等式：马尔可夫处理不能增加关于输入的互信息。
- 前缀码与 Kraft 不等式：码树的结构约束与长度可实现性。
- 典型集与 AEP：样本块的归一化自信息趋于熵。
- 编码速率：每个源符号可用的平均或固定比特数，须区分编码约束。
- 微分熵：密度对应的积分量，不能直接当作离散码长。
参考文献
- Polyanskiy, Y. & Wu, Y. (2016). MIT 6.441 Information Theory，讲义第 1–3 章：熵、相对熵、互信息与数据处理。
- 同一课程，第 6 章 Variable-Length Lossless Compression：前缀码与变长无损编码。
- 同一课程，第 7 章 Fixed-length (almost lossless) compression：定长信源编码及更一般的带边信息问题。