信息熵
不同的话语包含的信息量是不一样的。一句短小的话可能包含着很大的信息量，而一句冗长的话可能只含有一点点信息量。因此我们想知道一句话所包含的信息量，但看它的长度肯定是不对的，而是应该看它以最好的方式被压缩以后长度是多少。
我们把一句话看作一个二进制串，更一般地，一句话应当是一个随机生成的二进制串，也就是说，一个“随机变量”。一句话所包含的信息量与生成这句话的随即方式有关：假如我们就生成长度为\(n\)的二进制串，如果一种方式是始终输出全0串，那么这句话包含的信息量是很小的，因为我们只得到了“全0”以及“长度”这两个信息，我们很容易把这个串压缩成一个很短的串；而另一种方式是每一位都均匀随机的生成0或1，在这种情况下不同随机状态下我们会得到完全不一样的串，我们几乎无法对它进行任何的压缩，因此这句话的信息量是很大的。
香农提出了一个定量描述信息量的方法，称为“信息熵”。假设我们关注的随机变量\(X\)是从一个\(1,\cdots,n\)上的概率分布，\(\Pr[X=i]=p_i\)，那么\(X\)的信息熵定义为
事实上，这个表达式是可以被公理化的。通过四条公理我们就能唯一确定信息熵的表达式必须呈现这样的形式。分别是：①对称性， 对\(X\)的概率分布做一个permutation不影响信息熵的大小；②连续性，当某个\(p_i\)发生微小变化时\(H(X)\)的变化也是微小的；③单调性，如果分布是均匀随机的，那么\(n\)越大信息熵越大；④链式法则，设\(Z\)表示\((X,Y)\)（代表\(X,Z\)共同的信息），那么\(H(Z)=H(X)+H(Y\mid X)\)，表示两个随机变量的信息熵等于一个随机变量的信息熵加上在已知一个随机变量的前提下另一个随机变量的信息熵（其中，\(H(Y \mid X)\)定义为\(\sum\limits_{x}\Pr[X=x]H(Y\mid X=x)\)）。
我们会看到，用熵方法来解决组合问题时，本质上是在用概率方法，而我们又已经看到概率方法本质上就是计数方法。所以这一切仍然只是计数方法而已。但计数方法是通用的底层的方法，熵方法和概率方法一样，能为我们解决问题提供更高的视角和更巧妙的手段。
压缩编码
现在就来看压缩编码问题。对于一个随机变量，我们可以对它的每种可能的结果来用二进制编码，而二进制编码所需要的位数就是它最好能被压缩的长度。我们将会看到，这个长度就是随机变量的信息熵的大小。
比如我们的随机变量就是在\([n]\)均匀分布的，即恒有\(\Pr[X=i]=\dfrac{1}{n}\)，那么我们可以计算信息熵\(H(X)=\sum\limits_{i=1}^{n}\dfrac{1}{n}\log_2 \dfrac{1}{1/n}=\log_2 n\)——这很符合我们的直观，因为\(1,..,n\)的正整数直接用二进制表示就需要\(\log_2 n\)位，不可能做得比这更优了。我们严格地说明这件事。\(H(X)=\sum\limits_{i=1}^{n}p_i\log_2 \dfrac{1}{p_i}\)可以写作“期望”：\(H(X)=E[\log_2 \dfrac{1}{p_i}]\)（把\(\log_2 \dfrac{1}{p_i}\)看作一个随机变量而已），根据Jensen不等式，因为\(\log_2(x)\)是上凸函数，所以有\(E[\log_2 \dfrac{1}{p_i}] \leq \log_2 \left(E\left[\dfrac{1}{p_i}\right]\right)\)，而根据期望的定义\(E\left[\dfrac{1}{p_i}\right]=\sum\limits_{i=1}^{n}p_i\dfrac{1}{p_i}=n\)，于是我们证明了\(H(X) \leq \log_2 n\)恒成立。这印证了“随即均匀分布”是信息量最大的语句。
那么是不是所有的随机变量，我们都能构造出期望长度为\(H(X)\)的二进制串呢？我们来给出一种构造方法：首先不妨把\(p_1\)到\(p_n\)从大到小排序，为了使二进制串的期望长度为\(H(X)\)，我们就期待\(X=i\)时给出一个长度为\(\ell_i=\left\lceil\log_2\dfrac{1}{p_i}\right\rceil\)的串，概率高的串就短，概率低的串就长，很符合直观的“贪心要求”。为了证明这样真的是能够做到的，我们现在来证明当我们要构造\(X=i\)对应的串的时候，我们能使用一个长度为\(\ell_i\)的串，它不作为任何串的前缀。这意味着，假如我们想象一棵二叉树，左儿子边对应0，右儿子边对应1，那么一个串就是一条从根节点到某个节点的路径，为了保证任何以这个串为前缀的串都不再是合法的，我们需要删掉末尾节点为根节点的整个子树。我们只需要证明，当我们想构造\(X=i\)对应的串时，树上依然存在从根节点出发的长度为\(\ell_i\)的串。我们计算来说明这一点：最初树上有\(2^{\ell_i}\)条这样的路径，假如对于\(j<i\)，我们删除了以\(j\)为根节点的子树，那么会导致消灭了\(2^{\ell_i-\ell_j}\)条我们想要的路径。所以剩下的路径条数至少有\(2^{\ell_i}-\sum\limits_{j=1}^{i-1}2^{\ell_i-\ell_j}=2^{\ell_i}\left(1-\sum\limits_{j=1}^{i-1}\dfrac{1}{2^{\ell_j}}\right) \geq 2^{\log_2 \frac{1}{p_i}}\left(1-\sum\limits_{j=1}^{i-1}\dfrac{1}{2^{\log_2 \frac{1}{p_j}}}\right)=\dfrac{1}{p_i}\left(1-\sum\limits_{j=1}^{i-1}p_j\right)>0\)。所以我们总能找到这样的路径。
现在我们要说明，别的编码方法不可能更优。假设另一种编码方法，把\(X=i\)编码成\(\bar\ell_i\)。我们证明\(E[\bar \ell_i] \geq H(x)\)，也就是证明\(E[\bar\ell_i]-E[\log_2 \dfrac{1}{p_i}] \geq 0\)。即证\(\sum\limits_{i}p_i\left(\bar \ell_i-\log_2 \dfrac{1}{p_i}\right)=\sum\limits_{i}p_i\left(\log_2 \dfrac{2^{\bar\ell_i}}{1/p_i}\right)=E[\log_2(2^{\bar\ell_i}p_i)] \geq 0\)。即证\(-E[\log_2 \left(\dfrac{1}{2^{\bar\ell_i}p_i}\right)] \geq 0\)。运用Jensen不等式，\(-E[\log_2 \left(\dfrac{1}{2^{\bar\ell_i}p_i}\right)] \geq\)\(-\log_2\left(E\left[\dfrac{1}{p_i \cdot 2^{\bar\ell_i}}\right]\right)\)。其中\(E\left[\dfrac{1}{p_i \cdot 2^{\bar\ell_i}}\right]=\sum\limits_{i=1}^{n}p_i \cdot \dfrac{1}{p_i \cdot 2^{\bar\ell_i}}=\sum\limits_{i=1}^{n}2^{-\bar\ell_i}\)。因此只需证\(\sum\limits_{i=1}^{n}2^{-\bar\ell_i} \leq 1\)。这个和式有个直观意义：作为一种编码方式，每个\(\bar\ell_i\)都对应着二叉树上某个点，我们给这些节点做上标记。我们想象一个人从根节点出发在二叉树上随机游走，等概率走向左儿子和右儿子，如果碰到被标记的节点那么就停止游走。于是，它走到某个被标记的节点\(\bar\ell_i\)上的概率就恰好是\(2^{-\bar\ell_i}\)，和式\(\sum\limits_{i=1}^{n}2^{-\bar\ell_i}\)是所有可能的停下来的情况之和，因此就代表“随机游走停下来”这一事件发生的概率。有相当的可能性，如果被标记节点没有封锁所有往下的路径的话，那么随机游走有可能永远停不下来，此时这个和式的值就小于1，如果封锁了全部路径，这个概率就等于1。不管怎么样，我们通过这个随机游走的组合意义看到\(\sum\limits_{i=1}^{n}2^{-\bar\ell_i} \leq 1\)一定成立，这样证明就结束了。
所以我们看到，一个随机变量的熵真的能够代表对它进行二进制编码的最少位数。