问题：一条消息最短能有多短

早期的电报按词收费，一个词一美元。于是人们编出「电码本」：把一长串常用说法换成一个短词。课程举了几个真实条目——AZKHE 表示 clean bill of health，NBET 表示 captain is insane。今天发短信写 BRB，动机完全相同：把常出现的东西换成短符号。

电报时代的做法靠人工编表，凭经验挑选常用短语。本讲要回答的是它的数学版本：

给定一个信源，任何压缩方案的平均码长下限是多少？这个下限能不能达到？

答案是 Shannon 1948 年在同一栋楼里给出的：极限就是熵。本讲完整证明这个结论的两个方向。

时间轴

一阶信源

一个一阶信源（first-order source）由两部分组成：

• 字母表 $A=\{a_1,\dots,a_k\}$，共 $k$ 个符号；
• 分布 $p=(p_1,\dots,p_k)$，满足 $p_i\ge 0$、$\sum_i p_i=1$。

课程把它比作一颗不均匀的 $k$ 面骰子：每掷一次得到一个符号，掷 $n$ 次并保持顺序，就得到一条长度 $n$ 的消息 $x_1x_2\cdots x_n$。每次抽样独立且分布相同，所以

$$\Pr(x_1\cdots x_n)=\prod_{j=1}^{n}p_{x_j}.$$

字母可以是字母表的字母，也可以是词；课程强调这是最简单的模型，真实语言需要马尔可夫链等更复杂的结构，但本讲的理论会原样推广过去。

编码函数与可解码

编码函数 $\varphi:A^n\to\{0,1\}^*$ 把每条长度 $n$ 的消息映射成一个变长二进制串。

为什么允许变长？因为直观上高频消息应该配短码字。例子中 $a_1a_1$ 的概率高达 $49/64$，如果它能用 1 位表示，平均长度立刻下降。

变长带来一个必须写清的约束：映射必须单射。若两条不同消息编成同一个串，就无法解码。这里暂时不要求前缀无关：本讲的模型是一次性块编码，整条消息发完再发一个 END，解码器知道边界在哪里。等下讲的 Huffman 码才需要前缀无关，因为那里要逐符号流式解码。

用 $L(\varphi,x)=|\varphi(x)|$ 表示消息 $x$ 的码长，期望码长是

$$\mathbb E[L]=\sum_{x\in A^n}\Pr(x)\,|\varphi(x)|.$$

这正是要最小化的成本。

例子：$k=2$，$p=(7/8,1/8)$，$n=2$

长度为 2 的消息有四条，概率分别是

朴素编码逐符号替换，每条消息都是 2 位，期望长度恰好是 $2$。

改进编码把最可能的 $a_1a_1$ 压到 1 位，代价是让两条较罕见的消息变成 3 位。期望长度：

$$\mathbb E[L]=\frac{49}{64}\cdot1+\frac{7}{64}\cdot2+\frac{7}{64}\cdot3+\frac{1}{64}\cdot3 =\frac{49+14+21+3}{64}=\frac{87}{64}\approx1.359 .$$

确实小于 $2$。注意改进码的四个码字互不相同，且没有一个是另一个的前缀——这不是巧合，后面会看到前缀结构正是可达性的来源。

那么极限是多少？对 $k=2$、$p=(7/8,1/8)$，熵为

$$H\!\left(\tfrac78,\tfrac18\right) =-\tfrac78\log_2\tfrac78-\tfrac18\log_2\tfrac18 \approx 0.169+0.375=0.544\ \text{比特}.$$

每符号 0.544 比特，远低于 1 比特。$n=2$ 时只能做到 1.359/2≈0.68，差距来自 $o(n)$ 修正项；$n$ 越大越接近熵。

熵

对分布 $p=(p_1,\dots,p_k)$，二元熵定义为

$$H(p)=-\sum_{i=1}^{k}p_i\log_2 p_i .$$

因为 $0<p_i\le1$，每个 $\log p_i\le0$，负号使 $H(p)\ge0$。约定 $0\log 0=0$。

几个基本事实（后文会用到）：

• 均匀分布 $p_i=1/k$ 使熵最大，$H=\log_2 k$；
• 若某个 $p_i=1$，则 $H=0$——信源没有不确定性，不需要传信息；
• $H$ 只依赖概率，不依赖符号的名字。

Shannon 无噪声编码定理

设一阶信源的熵为 $H$。定理包含两个方向。

下界（converse）。 对任意可解码的编码函数 $\varphi$，

$$\mathbb E[L]\ \ge\ Hn-o(n).$$

上界（achievability）。 存在可解码的编码函数 $\varphi$，使得

$$\mathbb E[L]\ \le\ Hn+o(n).$$

这里 $o(n)$ 指随 $n$ 增长远慢于 $n$ 的量，例如 $O(\log n)$ 或 $O(\sqrt n)$。两个方向合起来：每符号的渐近最优码长就是 $H$，误差只占 $o(n)/n\to0$。

注意这是渐近结论。$n$ 很小时 $o(n)$ 项可能比 $Hn$ 还大，定理不提供有用信息；它的力量在于 $n\to\infty$。

直觉：均匀分布最难压缩

哪个分布最难压缩？从熵的角度，是使 $H$ 最大的分布；从直观角度，是没有高频符号可占便宜的分布。两者给出同一个答案：均匀分布。

均匀分布时 $p_i=1/k$，故 $H=\log_2 k$。而朴素编码给每个符号 $\lceil\log_2 k\rceil$ 位，所以每符号码长已经是 $\log_2 k$ 附近，无法再改进。

反过来，只要分布不均匀，就有「把高频事件压短」的空间。例子中 $49/64$ 的概率让我们把 $a_1a_1$ 压到 1 位，这就是收益来源。

下界的证明

第一步：均匀分布的引理

引理。 设 $m$ 个等概率消息，任何单射编码的期望码长至少是 $\log_2 m-O(1)$。

证明思路。 把所有码字看成二叉树的节点：根是空串，左孩子添 0，右孩子添 1。单射就是给 $m$ 个消息分配 $m$ 个互不相同的节点。要最小化平均深度，应当按层填满：第 0 层 1 个节点、第 1 层 2 个、第 2 层 4 个……直到装满 $m$ 个。数一下就知道，绝大多数消息的深度是 $\lfloor\log_2 m\rfloor$ 或 $\lceil\log_2 m\rceil$，平均值与 $\log_2 m$ 只差一个常数。

也可以在编码层面理解：深度为 $d$ 的节点最多 $2^d$ 个，若所有码字深度都小于 $\log_2 m-c$，能容纳的码字总数不足 $m$，矛盾。

第二步：固定每种符号的出现次数

设一条消息中符号 $a_i$ 出现 $n_i$ 次，$\sum_i n_i=n$。把这组 $(n_1,\dots,n_k)$ 称为消息的签名（signature）。

给定签名后，可能的字符串数目是多项式系数

$$M=\binom{n}{n_1,\dots,n_k}=\frac{n!}{n_1!\,n_2!\cdots n_k!}.$$

每个这样的字符串概率相同，都是 $p_1^{n_1}\cdots p_k^{n_k}$。换句话说，在固定签名的条件下，消息在 $M$ 个等概率字符串上均匀分布。于是引理给出

$$\mathbb E[L\mid \text{签名为 }(n_1,\dots,n_k)]\ \ge\ \log_2 M-O(1).$$

第三步：用 Stirling 公式把 $\log M$ 变成熵

对 $\log M$ 展开：

$$\log M=\log n!-\sum_{i=1}^{k}\log n_i! .$$

用 Stirling 公式 $\log n!=n\log n-n\log e+O(\log n)$，得到

$$\begin{aligned} \log M &=\Big(n\log n-n\log e+O(\log n)\Big) -\sum_{i=1}^{k}\Big(n_i\log n_i-n_i\log e+O(\log n)\Big)\\ &=n\log n-\sum_{i=1}^{k}n_i\log n_i+O(\log n), \end{aligned}$$

最后一步用了 $\sum_i n_i=n$，所以两个 $n\log e$ 项正好抵消。再把 $n=\sum_i n_i$ 拆开：

$$\log M=\sum_{i=1}^{k}n_i\log\frac{n}{n_i}+O(\log n) =n\left(-\sum_{i=1}^{k}\frac{n_i}{n}\log\frac{n_i}{n}\right)+O(\log n).$$

括号里正是经验分布 $\big(n_1/n,\dots,n_k/n\big)$ 的熵：

$$\log M=n\,H\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n).$$

这就是熵出现的位置：它不是被假设出来的，而是多项式系数在 Stirling 近似下的自然产物。

第四步：典型序列

第三步只处理了「签名已知」的情形。问题是：某个签名可能极少出现，那样得到的下界就用不上。

解决方法是典型性。称字符串是 $\varepsilon$-典型的，若对所有 $i$

$$\left|\frac{n_i}{n}-p_i\right|\le\varepsilon .$$

也就是说，经验频率落在真实概率的 $\varepsilon$ 邻域内。

由 Chebyshev 不等式（对每个坐标算方差，再用并集界合并 $k$ 个事件），

$$\Pr(\text{非典型})\ \le\ \frac{k}{\varepsilon^2 n}.$$

这里 $k$ 与 $\varepsilon$ 在定理中都是固定的，只有 $n\to\infty$，所以非典型概率 $\to0$。这正是前面几讲尾界工具的用处：经验频率以 $1/n$ 的速度收敛到真实概率。

第五步：拼出下界

用全期望公式把期望拆成典型与非典型两部分：

$$\mathbb E[L] =\Pr(\text{典型})\,\mathbb E[L\mid\text{典型}] +\Pr(\text{非典型})\,\mathbb E[L\mid\text{非典型}] \ \ge\ \Pr(\text{典型})\,\mathbb E[L\mid\text{典型}].$$

典型时，每个 $n_i/n$ 与 $p_i$ 只差 $\varepsilon$。熵在概率向量上是连续的，所以

$$\log M=nH\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n) =nH(p)\pm O(\varepsilon n)+O(\log n).$$

因此

$$\mathbb E[L]\ \ge\ \left(1-\frac{k}{\varepsilon^2 n}\right)\Big(nH(p)-O(\varepsilon n)-O(\log n)\Big).$$

先令 $n\to\infty$（消掉 $k/(\varepsilon^2n)$），再令 $\varepsilon\to0$，得到

$$\mathbb E[L]\ \ge\ nH(p)-o(n).$$

下界证完。

上界的证明：显式构造

下界说明谁都不能更快；上界要造出一个真正达到它的编码。构造按分支进行，只需要三块信息。

第 1 位：消息是否 $\varepsilon$-典型。

若典型：

• 用 $k\log_2 n$ 位写出签名 $(n_1,\dots,n_k)$——每个 $n_i$ 有至多 $n$ 种取值，需要 $\log_2 n$ 位，共 $k$ 个；
• 再用 $\log_2 M'$ 位写出「在给定签名下是第几个字符串」，其中 $M'$ 是签名落在 $\varepsilon$ 邻域内时多项式系数的最大值。

若非典型：直接输出朴素编码，每符号 $\log_2 k$ 位，共 $n\log_2 k$ 位。

按分支计算期望：

$$\mathbb E[L]\ \le\ \underbrace{1+k\log_2 n+\log_2 M'}_{\text{典型分支}} +\underbrace{\frac{k}{\varepsilon^2 n}\cdot n\log_2 k}_{\text{非典型分支的贡献}}.$$

逐项估计：

• $\log_2 M'=nH(p)+O(\varepsilon n)+O(\log n)$，由第三步与熵的连续性；
• $1+k\log_2 n=o(n)$；
• 非典型项等于 $\dfrac{k\log_2 k}{\varepsilon^2}$，是常数，也是 $o(n)$。

于是

$$\mathbb E[L]\ \le\ nH(p)+o(n).$$

两个方向合起来，定理证完。

值得强调的是：这个构造不需要知道消息内容，只需要在解码时先看「是否典型」这一位。典型时，问题退化成在 $M'$ 个等概率字符串中报出序号，而报序号的最优代价正是 $\log_2 M'$——这又回到第一讲的均匀分布引理。

这个编码为什么不实用

定理证明里的编码函数是一本码表：对每条可能的消息预先指定一个二进制串。消息总数是 $k^n$，指数级增长；实际使用时要存下整本码表，解码时还要在表里查找。这在理论上最优，在工程上完全不可行。

下一讲的 Huffman 码换一个思路：不预先固定 $n$ 再一次性编码，而是逐符号设计前缀码，用一棵树同时完成编码与解码，复杂度只与字母表大小有关。

本节结论

• 一阶信源 = 字母表 + 分布 + 独立同分布抽样。
• 编码函数把长度 $n$ 的消息映成变长二进制串，必须单射才能解码。
• 熵 $H(p)=-\sum_i p_i\log_2 p_i$ 是每符号码长的渐近下界。
• 下界证明的三件工具：均匀分布的二叉树引理、多项式系数 + Stirling、Chebyshev 典型性。
• 上界用「典型 / 非典型」两支构造：典型时付 $k\log n+\log M'$，非典型时付朴素编码，后者的概率只有 $O(k/\varepsilon^2n)$。
• 结果：$\mathbb E[L]=nH(p)\pm o(n)$，即每符号 $H(p)$ 比特。
• 该构造理论最优但码表指数大，工程上要用 Huffman 之类的逐符号方案。

理解检验

1. 本讲的编码函数只要求单射，为什么不需要前缀无关？下讲的 Huffman 码为什么必须要？

参考答案：本讲的模型是一次性块编码：固定 $n$，把整条长度 $n$ 的消息映射成一个二进制串，发完后发送 END，解码器先看到结束标记，再在码表中反查整条串。因为边界由外部标记给出，码字之间是否互为前缀不影响解码。

Huffman 码处理的是逐符号流式编码：消息长度事先未知，接收方必须从左到右即时切分。若某个码字是另一个的前缀，读到一半就无法判断当前码字是否结束，会产生歧义。前缀无关（等价于码字对应二叉树的叶子）保证任何比特流都有唯一解析。

2. 在 $k=2$、$p=(7/8,1/8)$、$n=2$ 的例子中，验证改进码的期望长度是 $87/64$，并说明它为什么仍需 $n$ 很大才能逼近熵。

参考答案：四条消息的概率为 $49/64,7/64,7/64,1/64$，码长为 $1,2,3,3$，故

$$\mathbb E[L]=\frac{49\cdot1+7\cdot2+7\cdot3+1\cdot3}{64}=\frac{87}{64}\approx1.359.$$

每符号约 $0.680$ 比特，而熵约 $0.544$ 比特。差距来自 $o(n)$ 项：编码必须用整数位，且在 $n=2$ 这种小块上，签名、边界等信息本身的开销占比很大。随 $n$ 增大，这部分摊薄到每条消息，平均值才收敛到 $H$。

3. 为什么均匀分布是最难压缩的分布？请同时给出直观理由和熵的理由。

参考答案：直观上，压缩的收益来自「高频事件配短码」。均匀分布下没有高频事件，所有符号等价，任何把某个符号压短的尝试都会让另一个符号变长，期望长度不受益。

熵的角度：$H(p)=-\sum p_i\log p_i$ 在单纯形上的最大值在 $p_i=1/k$ 处取得，值为 $\log_2 k$。由 Shannon 定理，最优每符号码长趋近 $H$，所以熵最大即码长最大。而朴素编码给每符号约 $\log_2 k$ 位，正好达到这个界，无法改进。

4. 下界证明为什么必须先固定签名 $(n_1,\dots,n_k)$？直接对整个消息空间用均匀分布引理不行吗？

参考答案：整个消息空间上的分布不是均匀的：不同字符串的概率差别极大（例子中 $49/64$ 与 $1/64$ 相差 49 倍），均匀分布引理不适用。

固定签名后，所有具有该签名的字符串概率相同，都是 $p_1^{n_1}\cdots p_k^{n_k}$，于是可以把它们看成 $M$ 个等概率对象，套用引理得到 $\log M-O(1)$。剩下的问题只是「哪个签名会出现」——用典型性说明存在一族高概率的签名，其 $n_i/n\approx p_i$，从而 $\log M\approx nH(p)$。

5. 用 Stirling 公式推导 $\log M=nH(n_1/n,\dots,n_k/n)+O(\log n)$，并指出哪一步用到了 $\sum_i n_i=n$。

参考答案：

$$\log M=\log n!-\sum_i\log n_i! =n\log n-n\log e-\sum_i\big(n_i\log n_i-n_i\log e\big)+O(\log n).$$

两个 $e$ 项分别是 $-n\log e$ 与 $+\big(\sum_i n_i\big)\log e$。只有在这里用到 $\sum_i n_i=n$，它们相消，留下

$$\log M=n\log n-\sum_i n_i\log n_i+O(\log n).$$

再把 $n$ 写成 $\sum_i n_i$：

$$\log M=\sum_i n_i\log\frac{n}{n_i}+O(\log n) =n\left(-\sum_i\frac{n_i}{n}\log\frac{n_i}{n}\right)+O(\log n)=nH\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n).$$

$O(\log n)$ 来自 Stirling 的误差项；$\sqrt{2\pi n}$ 那部分取对数后是 $O(\log n)$，被 $o(n)$ 吸收。

6. 上界构造里，$k\log_2 n$ 位用来写签名，为什么它可以被忽略？非典型分支的朴素编码要 $n\log_2 k$ 位，为什么也可以忽略？

参考答案：前者是 $o(n)$：$k$ 固定，$\log_2 n$ 增长远慢于 $n$，所以 $k\log_2 n=o(n)$，在 $nH\pm o(n)$ 的误差范围内。

后者看似线性，但只在非典型时使用，其概率由 Chebyshev 界为 $O(k/(\varepsilon^2n))$。乘起来：

$$\frac{k}{\varepsilon^2 n}\cdot n\log_2 k=\frac{k\log_2 k}{\varepsilon^2},$$

与 $n$ 无关，是常数，因而也是 $o(n)$。关键在于非典型是小概率事件，即使分支内部很浪费，摊到期望上也可忽略。

7. 定理说最优码长是 $nH$，为什么这个编码不能直接用于压缩文件？

参考答案：编码函数是一张码表，需要为 $A^n$ 中每条消息预先指定码字。消息总数 $k^n$ 随 $n$ 指数增长，存表和查表都不可行，而且发送方必须先知道整条消息才能查表。

工程上需要的是可增量、可即时解码的方案：Huffman 码用一棵与字母表同规模的树，对每个符号独立编码，编解码都是树上的行走，存储与时间只与 $k$ 有关，与 $n$ 无关。代价是它只能达到 $H$ 与 $H+1$ 之间，而不是渐近最优的 $H+o(1)$——但对实际数据，这个差距通常可以接受。

与前后课的关系

本讲把压缩的理论极限钉死在熵上，但证明里的构造不可实现。下一讲 Huffman 码给出可实现的最优前缀码：用交换论证证明「最不常用的两个符号必须是兄弟」，再递归合并，得到一棵最优二叉树；同时用 Kraft 不等式把前缀码与码长联系起来。

再下一讲转向噪声信道：消息在传输中会被翻转，问题从「压得更短」变成「错得起」。Shannon 第二定理会说明，只要码率低于信道容量，就可以用足够长的码把错误概率压到任意小——证明同样依赖典型性与随机编码。

The question: how short can a message be?

Telegrams used to be billed by the word, about a dollar each. People therefore printed code books that replaced long stock phrases with short tokens: AZKHE meant clean bill of health, NBET meant captain is insane. Texting BRB today is the same move: give the frequent thing a short symbol.

The telegraph era did this by hand, choosing phrases by experience. This lecture asks the mathematical version:

For a given source, what is the lower limit on the average code length of any compression scheme, and can that limit be attained?

Shannon answered in 1948, in the same building: the limit is entropy. The lecture proves both directions in full.

Timeline

First-order sources

A first-order source has two parts:

• an alphabet $A=\{a_1,\dots,a_k\}$ of $k$ symbols;
• a distribution $p=(p_1,\dots,p_k)$ with $p_i\ge0$ and $\sum_i p_i=1$.

The lecture pictures a biased $k$-sided die: roll it once to get a symbol, roll $n$ times keeping order, and obtain a message $x_1x_2\cdots x_n$ of length $n$. Draws are independent and identically distributed, so

$$\Pr(x_1\cdots x_n)=\prod_{j=1}^{n}p_{x_j}.$$

Symbols may be letters or whole words. The lecture stresses that this is the simplest model; real language needs Markov chains, but the theory carries over.

Coding functions and decodability

A coding function $\varphi:A^n\to\{0,1\}^*$ maps every length-$n$ message to a variable-length binary string.

Why variable length? Because frequent messages should get short codewords. In the example below, $a_1a_1$ has probability $49/64$; giving it one bit instead of two immediately lowers the average.

Variable length forces one requirement: the map must be injective. Two distinct messages encoded identically cannot be decoded. Prefix-freeness is not required here, because this is a one-shot block code: the whole message is sent, then END, so the decoder knows where the message stops. Prefix-freeness becomes necessary in the next lecture, where Huffman codes must be decoded symbol by symbol on a stream.

Writing $L(\varphi,x)=|\varphi(x)|$, the expected length is

$$\mathbb E[L]=\sum_{x\in A^n}\Pr(x)\,|\varphi(x)|,$$

and this is the cost to minimize.

Example: $k=2$, $p=(7/8,1/8)$, $n=2$

There are four messages of length two:

The naive code replaces each symbol by one bit, so every message costs two bits and the expected length is exactly $2$.

The improved code gives the most likely message one bit, at the price of three bits for the two rarer messages. Its expected length is

$$\mathbb E[L]=\frac{49}{64}\cdot1+\frac{7}{64}\cdot2+\frac{7}{64}\cdot3+\frac{1}{64}\cdot3 =\frac{49+14+21+3}{64}=\frac{87}{64}\approx1.359 .$$

This is below $2$. The four codewords are distinct and none is a prefix of another — not an accident, since prefix structure is what makes the construction work in general.

What is the limit? For this source,

$$H\!\left(\tfrac78,\tfrac18\right) =-\tfrac78\log_2\tfrac78-\tfrac18\log_2\tfrac18 \approx0.169+0.375=0.544\ \text{bits per symbol}.$$

That is far below one bit. At $n=2$ the best we do is $1.359/2\approx0.68$; the gap is the $o(n)$ correction, which shrinks as $n$ grows.

Entropy

For a distribution $p=(p_1,\dots,p_k)$, the binary entropy is

$$H(p)=-\sum_{i=1}^{k}p_i\log_2 p_i .$$

Since $0<p_i\le1$, each $\log p_i\le0$ and the minus sign makes $H(p)\ge0$. The convention is $0\log 0=0$.

Three facts used later:

• the uniform distribution $p_i=1/k$ maximizes entropy, giving $H=\log_2 k$;
• if some $p_i=1$, then $H=0$ — the source carries no uncertainty;
• $H$ depends only on the probabilities, not on the symbol names.

Shannon's noiseless coding theorem

Let the source have entropy $H$. The theorem has two directions.

Converse. For every decodable coding function $\varphi$,

$$\mathbb E[L]\ \ge\ Hn-o(n).$$

Achievability. There exists a decodable coding function $\varphi$ with

$$\mathbb E[L]\ \le\ Hn+o(n).$$

Here $o(n)$ means a quantity growing strictly slower than $n$, such as $O(\log n)$ or $O(\sqrt n)$. Together: the asymptotic optimum per symbol is $H$, with relative error $o(n)/n\to0$.

The statement is asymptotic. For small $n$ the $o(n)$ term may exceed $Hn$ and the theorem says nothing useful; its force is in the limit.

Intuition: the uniform distribution is hardest

Which distribution is hardest to compress? From entropy, the one maximizing $H$; from intuition, the one with no frequent symbol to exploit. Both give the same answer: uniform.

For uniform $p_i=1/k$, $H=\log_2 k$, and the naive code already uses about $\log_2 k$ bits per symbol, so nothing can improve. Conversely, any non-uniformity creates room: a frequent event can be given a short codeword.

The lower bound

Step 1: a lemma for uniform distributions

Lemma. For $m$ equally likely messages, every injective code has expected length at least $\log_2 m-O(1)$.

Proof idea. View codewords as nodes of a binary tree: the root is the empty string, appending 0 or 1 goes left or right. Injectivity means assigning $m$ distinct nodes. To minimize average depth, fill the tree level by level: 1 node at depth 0, 2 at depth 1, 4 at depth 2, and so on. Most of the $m$ messages end up at depth $\lfloor\log_2 m\rfloor$ or $\lceil\log_2 m\rceil$, so the average differs from $\log_2 m$ by a constant.

Equivalently, there are at most $2^d$ nodes at depth $d$; if every codeword had depth below $\log_2 m-c$, the total capacity would be less than $m$, a contradiction.

Step 2: fix the symbol counts

Let $a_i$ occur $n_i$ times, with $\sum_i n_i=n$. The tuple $(n_1,\dots,n_k)$ is the signature of the message.

Given a signature, the number of strings is the multinomial

$$M=\binom{n}{n_1,\dots,n_k}=\frac{n!}{n_1!\,n_2!\cdots n_k!}.$$

Every such string has the same probability $p_1^{n_1}\cdots p_k^{n_k}$. So conditioned on the signature, the message is uniform over $M$ strings, and the lemma yields

$$\mathbb E[L\mid \text{signature }(n_1,\dots,n_k)]\ \ge\ \log_2 M-O(1).$$

Step 3: Stirling turns $\log M$ into entropy

Expand

$$\log M=\log n!-\sum_{i=1}^{k}\log n_i! .$$

Using $\log n!=n\log n-n\log e+O(\log n)$,

$$\begin{aligned} \log M &=\Big(n\log n-n\log e+O(\log n)\Big) -\sum_{i=1}^{k}\Big(n_i\log n_i-n_i\log e+O(\log n)\Big)\\ &=n\log n-\sum_{i=1}^{k}n_i\log n_i+O(\log n), \end{aligned}$$

where the two $n\log e$ terms cancel because $\sum_i n_i=n$. Now split $n=\sum_i n_i$:

$$\log M=\sum_{i=1}^{k}n_i\log\frac{n}{n_i}+O(\log n) =n\left(-\sum_{i=1}^{k}\frac{n_i}{n}\log\frac{n_i}{n}\right)+O(\log n).$$

The bracket is the entropy of the empirical distribution:

$$\log M=n\,H\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n).$$

Entropy appears here not as an assumption but as the natural output of Stirling's approximation to a multinomial.

Step 4: typical strings

Step 3 handles a fixed signature, but some signatures may be so unlikely that the bound is useless. Typicality fixes this. A string is $\varepsilon$-typical if for every $i$

$$\left|\frac{n_i}{n}-p_i\right|\le\varepsilon ,$$

that is, every empirical frequency lies within $\varepsilon$ of its true probability.

By Chebyshev's inequality applied to each coordinate and a union bound over $k$ coordinates,

$$\Pr(\text{not typical})\ \le\ \frac{k}{\varepsilon^2 n}.$$

Both $k$ and $\varepsilon$ are fixed while $n\to\infty$, so this probability tends to zero. This is precisely the tail-bound machinery from earlier lectures: empirical frequencies converge at rate $1/n$.

Step 5: assemble the bound

Split the expectation with the law of total expectation:

$$\mathbb E[L] =\Pr(\text{typical})\,\mathbb E[L\mid\text{typical}] +\Pr(\text{not typical})\,\mathbb E[L\mid\text{not typical}] \ \ge\ \Pr(\text{typical})\,\mathbb E[L\mid\text{typical}].$$

On a typical string, each $n_i/n$ is within $\varepsilon$ of $p_i$. Entropy is continuous in the probability vector, so

$$\log M=nH\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n) =nH(p)\pm O(\varepsilon n)+O(\log n).$$

Therefore

$$\mathbb E[L]\ \ge\ \left(1-\frac{k}{\varepsilon^2 n}\right)\Big(nH(p)-O(\varepsilon n)-O(\log n)\Big).$$

Let $n\to\infty$ first (removing $k/(\varepsilon^2n)$), then $\varepsilon\to0$:

$$\mathbb E[L]\ \ge\ nH(p)-o(n).$$

The converse is proved.

The upper bound: an explicit code

The converse says nobody can do better; achievability must exhibit a code that does as well. The construction uses three pieces of information.

Bit 1: is the message $\varepsilon$-typical?

If typical:

• write the signature $(n_1,\dots,n_k)$ using $k\log_2 n$ bits — each $n_i$ has at most $n$ values, so $\log_2 n$ bits each;
• write the index of the string among those with this signature, using $\log_2 M'$ bits, where $M'$ is the largest multinomial over $\varepsilon$-typical signatures.

If not typical: fall back to the naive code at $\log_2 k$ bits per symbol, $n\log_2 k$ bits total.

Computing the expectation branch by branch:

$$\mathbb E[L]\ \le\ \underbrace{1+k\log_2 n+\log_2 M'}_{\text{typical branch}} +\underbrace{\frac{k}{\varepsilon^2 n}\cdot n\log_2 k}_{\text{contribution of the other branch}}.$$

Estimate each term:

• $\log_2 M'=nH(p)+O(\varepsilon n)+O(\log n)$, by Step 3 and continuity of entropy;
• $1+k\log_2 n=o(n)$;
• the atypical term equals $\dfrac{k\log_2 k}{\varepsilon^2}$, a constant, hence $o(n)$.

Thus

$$\mathbb E[L]\ \le\ nH(p)+o(n),$$

which completes the theorem.

Note what the decoder needs: one bit saying whether the message is typical. If it is, the problem reduces to reporting the index of one of $M'$ equally likely strings, whose optimal cost is $\log_2 M'$ — exactly the uniform-distribution lemma from Step 1.

Why this code is impractical

The code in the proof is a lookup table: every possible message is assigned a binary string in advance. There are $k^n$ messages, exponentially many, so storing the table and searching it are both infeasible.

The next lecture changes the approach. Instead of fixing $n$ and encoding the whole block at once, Huffman codes design a symbol-by-symbol prefix code represented by a tree, so encoding and decoding cost depend only on the alphabet size, not on $n$.

What this lecture establishes

• A first-order source is an alphabet, a distribution, and IID sampling.
• A coding function maps length-$n$ messages to variable-length binary strings and must be injective to be decodable.
• Entropy $H(p)=-\sum_i p_i\log_2 p_i$ is the asymptotic per-symbol lower bound.
• The lower bound uses three tools: the uniform-distribution tree lemma, the multinomial plus Stirling, and Chebyshev typicality.
• The upper bound branches on typicality: $k\log n+\log M'$ when typical, the naive code otherwise, and the latter has probability only $O(k/\varepsilon^2n)$.
• The result is $\mathbb E[L]=nH(p)\pm o(n)$, i.e. $H(p)$ bits per symbol.
• The code is optimal but exponentially large; practical schemes use Huffman-type constructions.

Comprehension check

1. This lecture only requires injectivity, not prefix-freeness. Why do Huffman codes require prefix-freeness?

Reference answer: This lecture studies one-shot block coding: $n$ is fixed, the entire length-$n$ message is mapped to one binary string, then END is sent, and the decoder looks the whole string up in the codebook. Boundaries come from an external marker, so prefix relations among codewords do not create ambiguity.

Huffman codes handle streaming, symbol-by-symbol encoding: the message length is unknown in advance and the receiver must split the bit stream on the fly. If one codeword were a prefix of another, the decoder could not tell where the current codeword ends. Prefix-freeness (equivalently, codewords at leaves of a binary tree) guarantees a unique parsing of every bit stream.

2. In the example $k=2$, $p=(7/8,1/8)$, $n=2$, verify that the improved code has expected length $87/64$, and explain why large $n$ is still needed to approach entropy.

Reference answer: The probabilities are $49/64,7/64,7/64,1/64$ with lengths $1,2,3,3$, so

$$\mathbb E[L]=\frac{49\cdot1+7\cdot2+7\cdot3+1\cdot3}{64}=\frac{87}{64}\approx1.359.$$

That is about $0.680$ bits per symbol against an entropy of about $0.544$. The gap is the $o(n)$ term: codewords have integer lengths, and for a block as small as $n=2$ the overhead of the signature and boundary information is large relative to the payload. As $n$ grows this overhead is amortized, and the average approaches $H$.

3. Why is the uniform distribution hardest to compress? Give both the intuitive and the entropy argument.

Reference answer: Intuitively, compression gains come from giving frequent events short codewords. Under a uniform distribution no symbol is frequent, every symbol is interchangeable, and any shortening forces another codeword to lengthen, so the expected length cannot improve.

Formally, $H(p)=-\sum_i p_i\log p_i$ is maximized on the simplex at $p_i=1/k$, with value $\log_2 k$. Shannon's theorem says the optimal per-symbol length approaches $H$, so maximal entropy means maximal length. The naive code already uses about $\log_2 k$ bits per symbol and therefore attains this bound.

4. Why must the lower-bound proof first fix the signature $(n_1,\dots,n_k)$? Why not apply the uniform lemma to the whole message space?

Reference answer: The distribution over messages is not uniform — probabilities differ enormously (in the example, $49/64$ versus $1/64$). The uniform lemma does not apply.

Conditioning on a signature makes all strings with that signature equally likely, each with probability $p_1^{n_1}\cdots p_k^{n_k}$, so they become $M$ equiprobable objects and the lemma gives $\log M-O(1)$. What remains is to argue that some signature family occurs with high probability — that is typicality, which guarantees $n_i/n\approx p_i$ and hence $\log M\approx nH(p)$.

5. Derive $\log M=nH(n_1/n,\dots,n_k/n)+O(\log n)$ with Stirling's formula, and identify where $\sum_i n_i=n$ is used.

Reference answer:

$$\log M=\log n!-\sum_i\log n_i! =n\log n-n\log e-\sum_i\big(n_i\log n_i-n_i\log e\big)+O(\log n).$$

The exponential terms are $-n\log e$ and $+\big(\sum_i n_i\big)\log e$. This is the only place where $\sum_i n_i=n$ is used; they cancel, leaving

$$\log M=n\log n-\sum_i n_i\log n_i+O(\log n).$$

Writing $n=\sum_i n_i$,

$$\log M=\sum_i n_i\log\frac{n}{n_i}+O(\log n) =n\left(-\sum_i\frac{n_i}{n}\log\frac{n_i}{n}\right)+O(\log n)=nH\!\left(\frac{n_1}{n},\dots,\frac{n_k}{n}\right)+O(\log n).$$

The $O(\log n)$ comes from the error term in Stirling; the $\sqrt{2\pi n}$ factor contributes only $O(\log n)$ after taking logs, which is absorbed by $o(n)$.

6. In the upper bound, why can the $k\log_2 n$ bits for the signature be ignored? The atypical branch costs $n\log_2 k$ bits, so why can that be ignored too?

Reference answer: The first is $o(n)$: $k$ is fixed and $\log_2 n$ grows far slower than $n$, so $k\log_2 n=o(n)$ and it fits inside the $nH\pm o(n)$ slack.

The second looks linear, but it is used only on atypical strings, an event of probability $O(k/(\varepsilon^2n))$ by Chebyshev. Multiplying,

$$\frac{k}{\varepsilon^2 n}\cdot n\log_2 k=\frac{k\log_2 k}{\varepsilon^2},$$

which is independent of $n$, hence a constant and also $o(n)$. The key is that atypicality is rare: however wasteful the fallback, its contribution to the expectation vanishes.

7. The theorem says the optimal length is $nH$. Why can this code not be used to compress a file?

Reference answer: The coding function is a codebook assigning a codeword to every message in $A^n$. There are $k^n$ messages, exponentially many, so storing and searching the table is infeasible, and the sender must know the whole message before encoding.

Practical schemes must be incremental and decodable on the fly. Huffman codes use one tree of size comparable to the alphabet, encoding each symbol independently and decoding by walking the tree, with storage and time depending only on $k$. The price is that Huffman achieves between $H$ and $H+1$ bits per symbol rather than the asymptotic $H+o(1)$ — usually an acceptable trade.

Relation to neighbouring lectures

This lecture pins the theoretical limit of compression at entropy, but its construction is unimplementable. The next lecture gives Huffman coding, an implementable optimal prefix code: an exchange argument shows the two least likely symbols must be siblings, which yields a recursive merge, and the Kraft inequality links prefix codes to their length profile.

The lecture after that turns to noisy channels, where the question changes from "make it shorter" to "make it survive errors". Shannon's second theorem shows that below channel capacity one can drive the error probability arbitrarily low with long enough codes, again via typicality and random coding.