2.3　问题3

例2-3　假定在M个位置（0，1，…，M-1）上放置了外形完全一样的铜球，其中只有一个球的重量比较轻，其余每个球的重量都相同；而轻球在这M个位置上出现的概率依次为。试问，若用天平称量，称多少次就一定能够找出这个轻球？

解：

为了特定的目的，我们把此问题做如下重要扩充：同时处理n个同样的问题，假定有n个轻球相互独立地处在M个位置上，它们在这M个位置上的概率分布都相同，如题中所设。现在需要判定n个轻球各自出现的位置，同样用天平称量的方法，称多少次就一定能够找出n个轻球各自的位置？

（注：实质上，天平称量的方法等同于把要判断的位置分成两组，对“轻球是否在其中一组中？”的问题给出回答：“yes”或“no”。）

用数学的语言描述：如果随机变量X表示轻球所在的位置，在M个位置上出现的概率分别为。现在，有n个独立且同分布的随机变量，各自都表示一个轻球出现的位置。

n个轻球的位置在n维乘积空间中代表一个点，其中每个Xi取值范围在（0，1，…，M-1）中，且所有Xi有独立和相同的概分布。

我们发现，n个轻球的位置在这个n维乘积空间中竟然近似于均匀分布（当n趋于无穷大时）！

为什么呢？有下面的论证：

考虑n个随机变量在M个不同位置上出现的事件，引进一系列随机变量（它们也被称为事件的特征函数）如下：

显然，对所有可能的j，也是n个独立同分布的随机变量，且有

根据独立同分布随机变量之和的贝努利大数定理（或柯尔莫哥洛夫强大数定理），当n趋于无穷大时，有（依概率收敛或几乎处处收敛）

记n个轻球在位置j出现（即Yij取值1）的总次数为nj，则nj/n趋近于pj，即

因此，有

也就是说，可近似认为，n个轻球的位置概率为1地都处于那样的集合中，其中n0个在位置0，…，nM-1个在位置M-1。对于每一个这样的样本点，其出现的概率为各个独立事件出现概率之乘积，它们都是相同的值！这些样本点的全体组成的集合概率为1，这些样本点在整个n维离散乘积空间X*…*X中呈均匀分布（当n趋于无穷大时）！

我们又可以回到均匀分布的条件了！

假定彼此独立地给出n个轻球的位置，它们都有同样的概率分布：在0位置出现的概率为p0，…，在M-1位置出现的概率为pM-1，要求以二分法的方式（相当于用天平称重），用最少的次数判定这n个轻球所在的位置。

涉及的因数多了，事情就复杂。把握住关键的概念，上面已经把问题转化为：在n维离散乘积空间X*…*X中，每个样本点出现的概率等于，而且，所有样本点在样本空间中呈均匀分布，若给定一个样本点的位置，要用二分法找出这个样本点，前面已经证明，共需要的次数为

采用这样的方法，实际上判定了n个轻球的位置。那么，对于判定一个轻球的位置而言，只用了

次判别步骤。

上式恰好就是概率分布，其中的熵。一般记为

这就是香农定义的信息熵的公式！我们从上面3个问题的求解看到，对于在M个位置上分别以概率出现的一个球，要确定其具体位置时存在的不确定性，熵是一种非常有效的度量！

综合上面所有的表述（从问题提出到求解），我们对信息熵的概念获得初步的感性理解。

在1948年，香农（C. E. Shannon）发表了奠基性的论文A Mathematical Theory of Communication，首次对于信息的产生与传输从量的方面给出定义，并提出和证明了一些非常基本的结果，彰显了这些定义的重要和有效，标志了一个新的信息时代的开端。只有从这种应用背景去了解，才能对信息熵的概念和重要性有更深刻的认识。

在香农工作的基础上，一大批后续的研究工作接踵而至。信息论不仅在通信领域，而且在计算机、物理、化学、生物，以及认知心理学等许多不同的分支中应用。仅从数学的角度看，数学家们（包括香农本人）对香农原始论文的论述作了简化和进一步的推广，建立了各种数学模型，并获得许多复杂和深入的结果。

对于一个有限离散分布，信息熵的定义为：。数学家们用严格的推理证明了，只要熵这个量满足少数几个从直观上接受的条件（性质），它就必然具有这样的函数形式。（仅有一个常数因子没有确定，这个因子确定单位信息量的大小，依赖于对数函数的底。）

我们后面将回到这个主题进行讨论。