熵的形象来源与熵的妙用
By 苏剑林 | 2016-02-20 | 29993位读者 |在拙作《“熵”不起:从熵、最大熵原理到最大熵模型(一)》中,笔者从比较“专业”的角度引出了熵,并对熵做了诠释。当然,熵作为不确定性的度量,应该具有更通俗、更形象的来源,本文就是试图补充这一部分,并由此给出一些妙用。
熵的形象来源 #
我们考虑由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》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Feb. 20, 2016). 《熵的形象来源与熵的妙用 》[Blog post]. Retrieved from https://kexue.fm/archives/3638
@online{kexuefm-3638,
title={熵的形象来源与熵的妙用},
author={苏剑林},
year={2016},
month={Feb},
url={\url{https://kexue.fm/archives/3638}},
}
April 30th, 2016
看了你的文章,我觉得你的物理直觉非常差。让我有点失望。
嘻嘻。我是搞数学的,物理直觉确实不好~我也试过提高,无果
April 30th, 2016
很久没上来了,和你开个玩笑的啦, 写的挺好的。