熵的形象来源与熵的妙用

在拙作《“熵”不起：从熵、最大熵原理到最大熵模型（一）》中，笔者从比较“专业”的角度引出了熵，并对熵做了诠释。当然，熵作为不确定性的度量，应该具有更通俗、更形象的来源，本文就是试图补充这一部分，并由此给出一些妙用。

熵的形象来源 #

我们考虑由0-9这十个数字组成的自然数，如果要求小于10000的话，那么很自然有10000个，如果我们说“某个小于10000的自然数”，那么0～9999都有可能出现，那么10000便是这件事的不确定性的一个度量。类似地，考虑$n$个不同元素（可重复使用）组成的长度为$m$的序列，那么这个序列有$n^m$种情况，这时$n^m$也是这件事情的不确定性的度量。

$n^m$是指数形式的，数字可能异常地大，因此我们取了对数，得到$m\log n$，这也可以作为不确定性的度量，它跟我们原来熵的定义是一致的。因为
$$m\log n=-\sum_{i=1}^{n^m} \frac{1}{n^m}\log \frac{1}{n^m}$$

读者可能会疑惑，$n^m$和$m\log n$都算是不确定性的度量，那么究竟是什么原因决定了我们用$m\log n$而不是用$n^m$呢？答案是可加性。取对数后的度量具有可加性，方便我们运算。当然，可加性只是便利的要求，并不是必然的。如果使用$n^m$形式，那么就相应地具有可乘性。

应用1：排序算法的效率 #

高效的排序算法是编程专业必须掌握的一个算法，而我们现在要估计理论上最高效的排序算法的平均效率。假如我们要对$n$个数从小到大排序，既然是一般的算法，那么必然能够用于一般的情况，因此，我们假设$n$个数互不相同，那么它们的排列情况有$n!$种，它的熵是$\log (n!)$，用Stirling公式有
$$\log (n!)\sim \log\left[\sqrt{2\pi n}\left(\frac{n}{e}\right)^n\right]\sim \mathcal{O}(n\log n)$$
而从小到大排好序后，情况是唯一的，那时候熵为0，所以，从信息论的角度来讲，排序就是熵从$\mathcal{O}(n\log n)$到0的过程。我们每次操作，只能对调两个数的位置，改变一定量的熵，假设每次的操作都是有益的，那么所用的时间也就正比于$\mathcal{O}(n\log n)$。当然，这是平均来说的，这也解释了排序算法的平均最高效率是$\mathcal{O}(n\log n)$。

应用2：多少次才能把牌洗乱 #

对于玩扑克来说，洗牌是最普通不过的事情了。对于一副新的牌，一般都是按顺序排好的，我们要洗乱它，一般用对切法洗牌，即将排分为两堆，然后交替混合。现在要问的是，这样对切洗牌多少次，才能使得牌洗乱了？（问题来源：http://duodaa.com/blog/index.php/archives/463/）

当然，这里有很多含糊之处。第一，对切法洗牌是一个怎么样的过程还没有定义好；第二，怎么才是洗乱了也没有定义。但是，我们不需要精确，毕竟我们也不是真的用数学去洗牌。我们可以用信息熵做个简单的估计。洗牌有点像排序算法的逆过程，同样的，$n$张牌，如果是足够随机的，那么它的熵是$\mathcal{O}(n\log n)$，对切法每次基本上改变了$n$张牌的位置，因此，每次所改变的熵的量大概正比于$n$，因此，我们对切$\mathcal{O}(\log n)$次后，大概就可以使得牌混乱了。这里重要的是$\log n$，这跟http://duodaa.com/blog/index.php/archives/463/提供的结果是一致的。

感叹 #

虽然本文比较粗糙，但是很显然：熵确实是个非常神奇的东西！

转载到请包括本文地址：https://kexue.fm/archives/3638

更详细的转载事宜请参考：《科学空间FAQ》