信息熵与称球问题

——浅议一些简单的信息论概念

2020年的新高考I卷(山东卷)12题中提到了一个很有意思的概念“信息熵”,那到底什么是信息熵呢?我们今天就来探究一下这个问题。

生活中我们经常提到信息量这个概念。举个例子,假设我能预知明年的高考卷,如果我跟你透露:明年的高考语文有作文。你肯定会想这不废话吗,那这句话信息量就非常小。但是如果我说明年数学导数大题是17题,那这个信息量就很大了。很明显,前面我说的高考语文有作文是一件发生概率很大的事情,而17题考导数则是一件概率很小的事情,所以直观来说,概率小的事件包含的信息量大。

那么如何量化这种信息量呢,现在我们只知道信息量I与概率P有关,即I=f(p)。因此我们不妨这样考虑,首先如果我告诉你两个相互独立的事件都会发生,那你得到的信息量肯定是我单独告诉你其中一个会发生的总和,用I(AB)代表事件A、B同时发生的信息量,我们有

I(AB)=I(A)+I(B)

同时根据相互独立事件的概率公式

P(AB)=P(A)P(B)

既然信息量I是概率P的函数,我们不难发现,符合上述表达式的就是对数函数(f(x)=ln(x) 就满足f(x1x2)=f(x1)+f(x2)),所以我们定义,一个随机事件发生所包含的信息量

I(A)=-log2P(A)

理论上这个底数可以取任意大于1的数,定义中取2就可以保证像抛硬币得到正面这种事情的信息量为1,这个信息量的单位我们叫做比特(Bit),计算机里面说的1比特的信息就是一个0或1能表达的信息量,也就和抛硬币等价。公式里的负号是为了让概率越小信息量越大。

    但这还没有结束,一个事情可以有多种结果,比如抛硬币有正面和反面,高考导数可能在六道大题的任意位置,这可以抽象为一个随机变量X的不同取值。显然X取不同值的概率不一定相同,所含的信息量也不一定相同,那么我们更关心这样一件事,当我们把X的值确定下来的时候,平均而言我们获得了多少信息量,或者说信息量的期望是多少?我们把这个期望叫做信息熵H,用H(X)表示随机变量X(取值{1,2,3,…,n})的信息熵,显然期望为[1]

手头有高考卷的同学可以看一下2020年的新高考I卷12题,就在刚刚我们已经推导出了题目中信息给出的表达式[2],并解释了它的含义。下面我们来看一个很经典的题目。

27个小球,编号1至27,其中有一个小球略轻,用一个天平称量,最少称量多少次才能找出这个小球?

我们考虑一下怎样的方案才是最合理的,从27个小球中确定一个,相当于确定取值为1到27的整数,概率均等的随机变量X的值,按照上面的信息熵公式,H(X)=-log2(1/27)≈4.8,而一次称量有3种结果:左边重、右边重、一样重,可以抽象为一个取值为1、2、3的随机变量Y,可以推算出H(Y)的最大值在三种取值概率相等时取得,为-log2(1/3)≈1.6(这个推导可参考那道12题的B选项,并可进一步推广到一般的n个取值的情况),所以根据信息论的知识,我们知道最少需要3次称量才有足够的信息量,不可能更少。

现在我们回顾一下这个问题的标准答案:第一次左右各放9个球,还剩9个,把轻的一边(若平衡则轻的是剩下的一堆)9个等分3份,重复上述操作则最终确定轻球的编号。我们不难发现,按照这种方案,每一次称量时出现三种结果的可能性都是1/3,每一次都获得了最多的信息。从信息论的角度,我们可以说每次称量可以获得1.6Bit的信息,而确定是哪个球轻需要4.8Bit的信息,所以3次称量就确定了轻球的编号。

感兴趣的同学可以继续考虑:如果只知道这个球与其他球不等重,需要几次称量才能找出这个球?又需要几次称量来找出这个球并确定是轻是重?先从信息熵的角度分析可行性,还可以尝试实际设计方案。同时也可以注意以下问题:信息熵只是获取信息量的期望,在我们上面的例子中随机变量每种取值的概率相等,但如果做不到相等,为了保证每次都能完成目标,那我们可能就要考虑最差情况而不是期望。

有关信息熵的更多应用,推荐B站UP主(油管博主)3Blue1Brown的一个视频:《用信息论解Wordle谜题[3]》(Solving Wordle using information theory)。3Blue1Brown是一个很不错的数学博主,他的视频主要是用可视化的方法帮助大家理解一些数学概念,在此安利一下。

文:夏韵

参考文献

[1]《通俗理解信息熵》,忆臻,https://zhuanlan.zhihu.com/p/26486223

[2] 2020年新高考全国Ⅰ卷数学试题,教育部国家考试中心

[3]《用信息论解Wordle谜题》,3Blue1Brown,哔哩哔哩弹幕视频网https://www.bilibili.com/video/BV1zZ4y1k7Jw


评论

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

Captcha Code