0x0 破题
人类干过一件挺荒诞的事:猜了几千年谜,却一直没给"不确定性"这三个字定一个单位。猜天气、猜牌局、猜对方是不是在说真话,靠的都是同一种资源——信息——但这资源多少年来一直是笔糊涂账,只能定性,不能定量。1948 年,Claude Shannon 在贝尔实验室写了一篇论文,把"不确定性"称出了斤两,人类第一次知道,一枚硬币的悬念,原来值 1 bit。
我打算按周啃完"信息论 → 信息经济学 → 机制设计"这条线。第一周啃地基:概率工具,加上信息论最核心的四个量——entropy、conditional entropy、mutual information、KL divergence。这四个量啃不透,后面聊逆向选择、道德风险、机制设计,都是空中楼阁。
0x1 概率复习:期望与 Jensen's inequality
信息论的语言是概率论,这句话不是客套。一个离散随机变量 X,取值 x 的概率是 p(x),这是全部家当。期望 E[X] 是加权平均,没什么可展开的。真正值得单独拎出来的,是 Jensen's inequality。
对于凸函数 f,有 f(E[X]) ≤ E[f(X));对于凹函数,不等号反过来。直觉是:先算平均再代入函数,和先代入函数再算平均,凸函数会让后者更大——函数的"弯曲"本身会制造额外的量。这条不等式看着朴素,却是整个信息论大厦的承重墙:mutual information 非负、KL divergence 非负、entropy 是凹函数,证明都得从这里出发(ANU 信息论课程讲义把 Jensen's inequality、Gibbs' inequality 到 data processing inequality 排成一条推导链,逻辑上环环相扣)。记住这条,后面的非负性证明就不必逐条死记,推一遍就出来了。
0x2 Entropy:不确定性的度量单位
熵的定义并不绕:
H(X) = -Σ_x p(x) log p(x)
log 取以 2 为底,单位是 bit。这个公式在说什么?每个结果 x 出现时,它自带的"意外程度"是 -log p(x)——越稀罕的事件,意外值越高。熵就是这份意外值的期望,即平均每次观测能拿到多少信息量(这一表述与将熵定义为随机变量期望信息量的通行处理一致)。
拿硬币举例:一枚均匀硬币,正反各半, H(X) = -[0.5 log 0.5 + 0.5 log 0.5] = 1 bit,每次抛掷都货真价实地传递 1 bit 信息。如果硬币被做过手脚,99% 正面,结果基本可预测,熵就跌下去了——这也是熵常被理解为"意外程度"或"不可预测性"的原因。熵的另一条性质是:在给定取值个数的前提下,均匀分布的熵最大,分布越偏,熵越小,这一点后面讲信道编码时还会用到。
值得多说一句的是符号背后的野心。Shannon 证明了,一个信源不可能被压缩到低于其熵的比特数——这是一条硬约束,不是工程建议,后面 0x6、0x7 两节会具体展开。
0x3 联合熵与条件熵:知道了一个变量,还剩多少雾
两个变量 X、Y 放在一起看,联合熵是
H(X,Y) = -Σ_{x,y} p(x,y) log p(x,y)
条件熵定义为
H(X|Y) = H(X,Y) - H(Y)
意思是:先把 X、Y 一起的总不确定性算出来,再减去 Y 自身的不确定性,剩下的就是"已知 Y 之后,X 还剩多少雾"。这条定义直接推出一个链式法则:H(X,Y) = H(X) + H(Y|X),把联合不确定性拆成"先看 X 的不确定性"加上"看完 X 之后 Y 还剩的不确定性"。
一个几乎不需要证明就能猜到、但确实可以证明的性质是 H(X|Y) ≤ H(X)——条件永远不会增加不确定性,俗称"conditioning reduces entropy"。多知道一件事,雾只会变薄,不会变厚(极端情况下 Y 与 X 无关,雾厚度不变而已)。
0x4 Mutual information:两个变量之间到底掐着多少信息
把 0x3 的结论倒过来看,就是互信息:
I(X;Y) = H(X) - H(X|Y) = H(X) + H(Y) - H(X,Y)
它衡量的是"知道 Y 之后,X 的不确定性被压缩了多少",这个量对称——I(X;Y) = I(Y;X)——而且非负,等于零当且仅当 X 与 Y 独立。互信息还有一层更本质的写法:它就是联合分布与边缘分布乘积之间的 KL divergence,
I(X;Y) = D(p(x,y) ‖ p(x)p(y))
这句话把 0x4 和 0x5 焊在了一起:互信息不是一个孤立的新概念,而是 KL divergence 在"检验独立性"这个具体场景下的化身。
0x5 KL divergence:说错话要多付多少代价
KL divergence,又叫 relative entropy,定义为
D(p‖q) = Σ_x p(x) log [p(x)/q(x)]
它衡量的是"用分布 q 去近似真实分布 p"所付出的代价。这个量非负(由 0x1 的 Jensen's inequality 直接推出,业内称为 Gibbs' inequality),等于零当且仅当两个分布处处相等;但它不对称,D(p‖q) 一般不等于 D(q‖p),所以不是数学意义上的距离。
KL divergence 有一个特别落地的解释:如果真实分布是 p,但编码时用的是错误分布 q 设计出的最优码长,那么平均码长会比用 p 设计时多付出 D(p‖q) 那么多比特(这一"错误建模的额外代价"解释常见于信源编码的相关课程讲义)。换句话说,KL divergence 量化的是"信念错了,要付多少信息论意义上的利息"——这句话留着,信息经济学那一章讲 signaling 和 screening 时还会用到,概念是相通的。
0x6 AEP:大数定律在信息论里的化身
概率论里的大数定律说,独立同分布变量的样本均值会收敛到期望。信息论里的对应版本叫 asymptotic equipartition property(AEP):
-(1/n) log p(X₁, X₂, …, Xₙ) → H(X)(依概率收敛)
翻译成人话:当 n 足够大,一段长度为 n 的独立同分布序列,其对数概率的均值会稳稳地贴近熵。由此可以把所有可能的序列一分为二——typical set 和其余部分。typical set 里的序列数量大约是 2^{nH(X)} 个,每个的出现概率大致相等;typical set 之外的序列,理论上存在,但加总概率趋近于零(Cover 与 Thomas 所著《Elements of Information Theory》把 AEP 明确定位为大数定律在信息论里的类比,这也是 MIT 信息论课程大纲把 AEP 放在主干位置的原因)。
这个结论看着抽象,落地却极其具体:既然几乎所有的概率质量都挤在 typical set 里,只要能给这 2^{nH(X)} 个序列编码,压缩问题基本就解决了——这就是下一节的伏笔。
0x7 信源编码定理与 Huffman coding:熵是压缩的地板价
Shannon 的 source coding theorem 说得很直白:任何无损压缩方案,平均码长都不可能低于熵,即 H(X) ≤ E[l(X)],而一种具体的、可构造的最优前缀码——Huffman coding——能把平均码长压到 H(X) 与 H(X)+1 之间。
Huffman coding 的身世也值得一提:David Huffman 在 MIT 读博期间,导师 Robert Fano 布置了一道关于最优二进制编码的课程作业,Huffman 想出的自底向上构造前缀码的办法,效率反而超过了 Fano 自己此前提出的 Shannon–Fano coding,论文发表于 1952 年。这大概是学术史上少数"学生作业反超导师方案"的例子,读来有点解气。
Huffman coding 的构造思路简单:把出现概率最小的两个符号合并成一个节点,重复这个过程直到只剩一个根节点,再从根节点回溯赋予每个符号一段二进制前缀码——概率越低的符号,分配的码长越长。这套贪心算法之所以最优,根子还是在熵——熵划定了压缩的地板价,Huffman coding 只是把这块地板价用一种具体、可执行的方式铺了出来。
0x8 信道容量:噪声存在时,信息还能跑多快
前面几节讲的是压缩——同一个信源,能不能用更少的比特表示。信道容量讲的是传输——信息经过一条带噪声的信道,还能保真地跑多快。Shannon 给出的定义是
C = max_{p(x)} I(X;Y)
在所有可能的输入分布 p(x) 里,找一个让互信息最大化的分布,这个最大值就是信道容量。noisy-channel coding theorem 进一步给出一个近乎反直觉的结论:只要传输速率 R 低于 C,总存在一种编码方式,让误码概率随着码长增加趋近于零——噪声不是拦路虎,只要留足冗余,就能把误差压到任意小(这也是 Shannon separation theorem 的由来:先把信源压缩到熵率,再用信道编码把压缩后的比特送过带噪声的信道,两步分开做互不影响最优性)。
这条定理最反直觉的地方在于:它只保证"存在"这样的编码,却不告诉你具体怎么构造——这也是为什么从 1948 年到后来的 turbo code、LDPC code,足足花了半个多世纪,人类才把逼近信道容量的实用编码方案造出来。