Entropy Method

信息熵

不同的话语包含的信息量是不一样的。一句短小的话可能包含着很大的信息量，而一句冗长的话可能只含有一点点信息量。因此我们想知道一句话所包含的信息量，但看它的长度肯定是不对的，而是应该看它以最好的方式被压缩以后长度是多少。

我们把一句话看作一个二进制串，更一般地，一句话应当是一个随机生成的二进制串，也就是说，一个“随机变量”。一句话所包含的信息量与生成这句话的随即方式有关：假如我们就生成长度为$n$的二进制串，如果一种方式是始终输出全0串，那么这句话包含的信息量是很小的，因为我们只得到了“全0”以及“长度”这两个信息，我们很容易把这个串压缩成一个很短的串；而另一种方式是每一位都均匀随机的生成0或1，在这种情况下不同随机状态下我们会得到完全不一样的串，我们几乎无法对它进行任何的压缩，因此这句话的信息量是很大的。

香农提出了一个定量描述信息量的方法，称为“信息熵”。假设我们关注的随机变量$X$是从一个$1,\cdots,n$上的概率分布，$\Pr[X=i]=p_i$，那么$X$的信息熵定义为

$$H(X)=\sum\limits_{i=1}^{n}p_i \log_2\dfrac{1}{ p_i}$$

事实上，这个表达式是可以被公理化的。通过四条公理我们就能唯一确定信息熵的表达式必须呈现这样的形式。分别是：①对称性， 对$X$的概率分布做一个permutation不影响信息熵的大小；②连续性，当某个$p_i$发生微小变化时$H(X)$的变化也是微小的；③单调性，如果分布是均匀随机的，那么$n$越大信息熵越大；④链式法则，$H(X,Y)=H(X)+H(Y\mid 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$一定成立，这样证明就结束了。

所以我们看到，一个随机变量的熵真的能够代表对它进行二进制编码的最少位数。

联合随机变量的熵

现在我们来解释$(X,Y)$是什么含义。通常我们定义$Z=(X,Y)$，表示随机变量$Z$是某两个随机变量$X,Y$的二元组，是一个由随机变量联合起来形成的对象，称为“联合随机变量”。

例如，假设现在我们生成两次$0..7$的随机数，那么样本空间$\Omega=\{0..7\} \times \{0..7\}$，同时我们采用的随机方法规定两次生成的数之和为奇数的概率为0，其余情况均匀分布。那么我们定义随机变量$X$返回第一次生成的随机数（这的确是个随机变量，因为它是样本空间到实数的映射），$Y$返回第二次生成的随机数，那么我们就可以用$(X,Y)$这样一个联合随机变量来表示样本空间中的一个事件了，这样的事件总共有$8\times 8 /2=32$个。

下面来计算这个联合变量的熵。我们来计算联合随机变量的熵。首先，$H(X)=H(Y)=\sum\limits_{i=1}^{n}p_i \log_2\dfrac{1}{ p_i}=8 \times \dfrac{1}{8} \times \log_2 \dfrac{1}{\frac{1}{8}}=\log_2 8 = 3$。对于联合随机变量$(X,Y)$，我们也可以求它的熵，因为只要是由一个概率分布的东西都可以求熵。我们把$(X,Y)$当作普通的随机变量一样来看待的话，它有32种取值，每种取值的概率都是$\dfrac{1}{32}$。于是求得$H(X,Y)=32 \times \dfrac{1}{32} \times \log_2 32=5$。于是我们发现$H(X)+H(Y)>H(X,Y)$。这说明了什么呢？熵代表的是信息量，或者更精确地，压缩成最优的二进制串需要的位数。如果我们先单独压缩$X$再单独压缩$Y$来得到$(X,Y)$的编码，我们发现这样做不是最优的，也就是我们浪费了一些无用的位数。这其实是容易发现的，因为我们已经提前知道了不可能出现两个奇偶性不同的$X,Y$，所以一旦$X$确定了以后，我们其实已经知道了一部分$Y$的信息，所以再单独给$Y$编码就一定造成浪费了。

这就证实了我们在给出熵的公理时为什么没有写$H(X,Y)=H(X)+H(Y)$而是给出了$H(X,Y)=H(X)+H(Y \mid X)$。从韦恩图的角度来理解的话，我们把$H(X,Y)$看作集合$X \cup Y$，表示$(X,Y)$包含的信息，那么$H(Y \mid X)$必须表示的是$Y \setminus X$，表示$Y$上剔除所有$X$的信息以后单独留下的信息。换言之，我们需要用第一个变量的信息已知的眼光去看第二个变量，这就是我们为什么采用了和条件概率一样的符号，它用来提醒我们$X$是“作为条件的”已知量。严格地，$H(Y \mid X):=\sum\limits_{x}\Pr[X=x] \cdot H(Y \mid X=x)$，其中$Y \mid X=x$与我们在“条件概率”中讨论的是同一个东西，可以把它展开写成$H(Y \mid X=x)=\sum\limits_{y}\Pr[Y=y \mid X=x]\log_2 \dfrac{1}{\Pr[Y=y \mid X=x]}$。于是就有$H(Y \mid X)=\sum\limits_{x}\Pr[X=x]\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2\dfrac{1}{\Pr[Y=y \mid X=x]}$，它可以看作$E_x[\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2\dfrac{1}{\Pr[Y=y \mid X=x]}]=E_x[H(Y \mid X=x)]$。

从熵的表达式出发，我们来验证$H(X,Y)=H(X)+H(Y \mid X)$的正确性：$H(X,Y)=\sum\limits_{x,y}\Pr[X=x \land Y=y] \log_2 \dfrac{1}{\Pr[X=x \land Y=y]}$ $=-\sum\limits_{x,y}\Pr[X=x \land Y=y] \log_2 \Pr[X=x \land Y=y]$，根据条件期望的定义$\Pr[A \land B] = \Pr[A \mid B] \cdot \Pr[B]$，因此$H(X,Y)=-\sum\limits_{x,y}\Pr[Y=y\mid X=x]\Pr[X=x]\log_2(\Pr[Y=y \mid X=x]\Pr[X=x])$。先枚举$x$，得到$-\sum\limits_{x}\Pr[X=x]\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2(\Pr[Y=y\mid X=x]\Pr[X=x])$ $=-\sum\limits_{x}\Pr[X=x]\left(\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2(\Pr[X=x])+\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2(\Pr[Y=y\mid X=x])\right)$ $=-\sum\limits_{x}\Pr[X=x]\left(\log_2(\Pr[X=x])\sum\limits_{y}\Pr[Y=y\mid X=x]+\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2(\Pr[Y=y\mid X=x])\right)$，其中$\sum\limits_{y}\Pr[Y=y\mid X=x]=1$，于是$H(X,Y)=-\sum\limits_{x}\Pr[X=x]\log_2(\Pr[X=x])-\sum\limits_{x}\Pr[X=x]\sum\limits_{y}\Pr[Y=y\mid X=x]\log_2(\Pr[Y=y\mid X=x])$ $=H(X)+\sum\limits_{x}\Pr[X=x]H(Y \mid X=x)=H(X)+H(Y \mid X)$。

我们也可以根据定义证得我们通过例子给出的不等式$H(X,Y) \leq H(X)+H(Y)$，当随机变量$X,Y$独立时等号成立，因为它们之间互相不能给出对方的任何信息。

联合随机变量可以推广到超过2个变量的情形，这时我们得到的是“链式法则”：$H(X_1,\cdots,X_n)=H(X_1)+H(X_2 \mid X_1)+H(X_3 \mid X_1,X_2) +\cdots+H(X_n \mid X_1,\cdots,X_{n-1})$。同样也有不等式$H(X_1,\cdots,X_n) \leq H(X_1)+\cdots+H(X_n)$，当所有变量互相独立时取到等号。

熵方法

下面我们就用熵来解决计数问题。其核心用到了熵与数量之间的对数关系（压缩编码时我们已经证明了这一点），如果我们证明了熵有某个下界$w$，那么对应着它的数量一定$\geq 2^w$。

坐标投影计数

随机给出$n^3$个$\R^3$中互不相同的整数点$(x,y,z)$，构成集合$S$。设$S_x$为所有这些点的横坐标构成的集合，$S_y,S_z$同理。我们容易发现$|S_x|,|S_y|,|S_z|$中至少有一个$\geq n$，因为如果三者都$<n$就不可能形成$n^3$个点。

从熵的角度看它是怎么样的？考虑这$n^3$个点是随机均匀生成的，那么$H(X,Y,Z)=\sum \dfrac{1}{n^3}\log_2 n^3=3\log_2 n$。而根据我们的不等式，$H(X,Y,Z) \leq H(X)+H(Y)+H(Z)$，因此$H(X),H(Y),H(Z)$中至少有一个$\geq \log_2 n$，不妨设就是$H(X) \geq \log_2 n$。也就意味着，如果以最好的方式压缩也需要至少$\log_2 n$位，那么$X$在十进制下至少是一个大于等于$n$的数。从这个过程我们也再次看到，熵确实可以被理解成一种加权平均，一种期望，根据期望的界来证明不等式我们是熟悉的，因此我们同样也可以用熵的界来证明不等式。

如果把条件修改为$S$往三个坐标平面上投影$S_{xy},S_{xz},S_{yz}$，那么怎么证明$S_{xy} \geq n^2$。平凡的证法似乎不再有效了，但是熵方法依然可行。我们采用相似的方法，希望能够证明$H(X,Y) \geq \log_2 n^2$，这可以通过$H(X,Y)+H(X,Z)+H(Y,Z) \geq 6 \log_2n$来得到。右侧也就是$2H(X,Y,Z)$。根据链式法则，$H(X,Y,Z)=H(X,Y)+H(Z \mid X,Y)$。同时也有$H(X,Y,Z)=H(Y,Z)+H(X \mid Y,Z)$。因此$2H(X,Y,Z) \leq H(X,Y)+H(Y,Z)+H(Z \mid X,Y)+H(X \mid Y,Z)$。因此只需证明$H(Z \mid X,Y)+H(X\mid Y,Z) \leq H(X,Z)$。而根据条件概率的不等式$H(Z \mid X,Y) \leq H(Z\mid X)$，$H(X \mid Y,Z) \leq H(X)$。而$H(X,Z)$就等于$H(X)+H(Z \mid X)$，证毕。

2-path

设图$G$有$n$个点$m$条边，并且每个点的度数都为$d$。（可以求出$d=\dfrac{2m}{n}$）我们要统计图中有多少条不同的长度为$2$的路径（2-path)。那我们枚举第一条边，有$m$种可能。第二条边有$d-1$种选择。因此总数就是$m(d-1)$。

现在如果我们并不保证每个点的度数都是$d$，而是保证点的平均度数恰好为$d$。此时依然有$nd=2m$。这时2-path的个数如何呢？我们用熵方法能够给出一个下界，基于我们能给出一个熵的下界。一条2-path的熵可以用三个顶点的随机变量来刻画：$H(X,Y,Z)$代表由边$(X,Y)$和$(Y,Z)$形成的2-path。$H(X,Y,Z)=H(X,Y)+H(Z \mid X,Y)$，也就是我们可以把随机的过程看作先随机地选取一条边，再以这条边的第二个端点为起点再选一条边。前者是等概率地，因此容易求出$H(X,Y)=m \cdot \dfrac{1}{m} \cdot \log_2 m = \log_2 m$。为了讨论起来方便，我们暂时认为$Z$与$X$可以相等，之后再把这一部分影响去掉。这时，$H(Z \mid X,Y)$就可以等价于$H(Z \mid Y)$了，因为$Z$的取值丝毫不受$X$影响。于是$H(Z \mid Y)=\sum\limits_{y}\Pr[Y=y]H(Z \mid Y=y)$，其中$H(Z \mid Y=y)=$ $\deg(y) \cdot\dfrac{1}{\deg(y)}\log_2 \deg(y)=\log_2 \deg(y)$。而要选到$Y$点，第一条边必须把$Y$当作第二个端点，每条边有两种顺序，因此$\Pr[Y=y]=\dfrac{\deg(y)}{2m}$。所以$H(Z \mid Y=y)=\dfrac{1}{2m}\sum\limits_{y}\deg(y)\log_2 \deg(y)$。基于$x\log_2x$是下凸函数，我们可以根据Jensen不等式放缩，为此我们配凑一列系数$\dfrac{1}{n}$，得到$\dfrac{n}{2m}\sum\limits_{y}\dfrac{1}{n}\deg(y)\log_2 \deg(y)=\dfrac{n}{2m}\sum\limits_{y}\dfrac{1}{n}f(\deg(y)) \geq \dfrac{n}{2m}f\left(\sum\limits_{y}\dfrac{1}{n}\deg(y)\right)$ $=\dfrac{n}{2m}f\left(\dfrac{2m}{n}\right)=\dfrac{n}{2m}\cdot\dfrac{2m}{n}\log_2 \dfrac{2m}{n}=\log_2 \dfrac{2m}{n}$。综上$H(X,Y,Z) \geq \log_2 m+\log_2 \dfrac{2m}{n}=\log_2 \dfrac{2m^2}{n}$。于是我们证明了$(X,Y,Z)$的个数至少有$\dfrac{2m^2}{n}$个，也就是$md$个。由于我们假设了$X$和$Z$可能相等，我们还得减掉$(X,Y,X)$这样的三元组的个数，这个数量用手就能输出来，因为它就是边的数量的两倍（因为要考虑顺序）。所以互不相同的三元组$(X,Y,Z)$数量至少为$m(d-2)$。由于枚举顺序的影响，这个三元组的个数恰好是2-path的两倍，因为每条路径都从不同方向被数了两边。因此我们证明了2-path的个数至少为$m\left(\dfrac{d}{2}-1\right)$。

用类似的方法还可以数出图上的大小为4的环，因为排除了一些重叠的情况以后，大小为4的环就是两段2-path。