3. 吃惊的度量
坦白地说，12球问题是有一定难度的，但如果我们对信息论有一定的了解，问题就相对容易了。信息论中一个重要的概念是熵，它给出了概率分布的信息的度量。为此我们先介绍一下什么是熵。
话说你和朋友一块去打靶，各自对着靶子打了一枪。你朋友是职业神枪手而你是新手。报靶员说，你朋友正中靶心，你们笑笑，不以为然。报靶员接着说，你也正中靶心，你们大吃一惊。
为什么同样正中靶心，反应会不一样？
你朋友正中靶心，大家不吃惊，因为他是神枪手，打中的概率高，中了有何奇怪？反之，你初次摸枪，能挨上靶边就不错了，居然能正中靶心，自然出乎意料。也就是说，你打中靶心的概率很小，居然发生了，吃惊度很高。这就牵涉到吃惊的度量，也就是信息量。直观地说，越让人吃惊的事件信息量也越大。如何去度量一个事件的吃惊度或者信息量呢？我们希望有一个数学表达式 $S(p)$ 来度量一个随机事件A的吃惊度，这里$p$是$A$发生的概率。
吃惊度 $S(p)$ 在数学上到底该长成什么样子呢？
我们先看看，吃惊度 $S(p)$ 都应该满足哪些条件？
一个事件如果肯定发生，吃惊度应该为零，所以有
条件1： $S(1)=0$。
如果事件$A$发生的概率为$p$，事件$B$发生的概率为$q$，并且$p>q$，事件$A$和$B$，哪个吃惊度大些？应该是$B$吧？所以有
条件2：$S(p)$是$p$的递减函数。
如果$p$和$q$相差很小，$S(p)$和$S(q)$也应相差很小，所以又有
条件3：$S(p)$是$p$的连续函数。
最后，如果$A$和$B$相互独立，那么$A$和$B$同时发生的概率就是$pq$，其吃惊度为$S(pq)$。$S(pq)-S(p)$是什么意思？$S(pq)$是$A$和$B$同时发生带来的吃惊度，$S(p)$是$A$发生的带来的吃惊度，因为$A$和$B$相互独立，$S(pq)-S(p)$应该是$B$的吃惊度，所以又有$S(pq)-S(p)=S(q)$，也即是
条件4：$S(pq)=S(p)+S(q)$}。
好了，根据这四个条件，通过简单的数学推导，我们可以得出$S(p)$的数学表达式为：$S(p)=-Clog(p)$，其中$C$为常数，通常取之为1，对数的底通常取做2，这时的单位叫作BITS；当然也可根据需要取其它数为底。所以有$S(p)=-log(p)$。换句话说，如果随机事件$A$发生的概率为$p$，它的吃惊度就是$-log(p)=log(1/p)$。如果$P=(p_1,p_2,…,p_n)$是一个概率分布，则$H(P)=-p_1log(p_1)-p_2(log(p_2)-…-p_nlog(p_n)=p_1log(1/p_1)+p_2log(1/p_2)+…+p_nlog(1/p_n)$是整个分布的平均吃惊度，称之为分布$P=(p_1,p_2,…,p_n)$的熵，用$H(P)=H(p_1,p_2,…,p_n)$表示。
熵是信息论中最基本的概念，它刻画了一个概率分布的平均吃惊度。在一个有$n$种可能结果的概率分布中，什么情况下熵最大？经过数学推导，可以得知，当所有结果等可能时，其熵最大。
先看一个简单的猜数游戏：你随便从1到$2^n$个整数中间想好一个数，我来猜你想的是哪个数。如何猜？我可以想法问你一些问题，你只需如实回答是或者否。我们应该如何设计问题，使得尽可能少的提问就猜中答案？
比方说，$n=5$，也就是你随便从 $1,2,\cdots,32$中想好一个数，我需要问几个问题，就把你想的那个数猜到呢？这个问题，实际上是$n$ 球问题的简化情况：在那里问题有三种答案：左重，右重，或左右平衡。因此那里的问题略显复杂一些了。
为什么要提问题？就是想获得信息，而熵正可用来衡量信息的多少。我们每问一个问题，无非有两种可能的答案，是与否。什么情况下熵最大？如果两种答案等可能。如何设计这种问题使得是否两种答案等可能？可用等分法。比如第一次可问：你想的数小于或等于16。如答案是是，你可继续等分$1,2,\cdots,16$然后同法炮制下一个问题。如答案是否，你可继续等分$17,18,\cdots,32$继续问：你想的数小与或等于24。依此类推，只需提问五次，你就可以猜中答案了。当然，你提的问题只需等分两种可能，比如也可问，你想的是偶数。等等。
为什么需要五次？那是因为你想的那个数是在$1,2,\cdots,32$之中的一个，因此其概率分布为$P=(1/32,1/32,\cdots,1/32)$，其熵为$H(P)=5$。概率分布的熵给出了提问次数的下界。如果每次问题两种答案等可能，分布就是$Q=(1/2,1/2)$，其熵就是$H(Q)=1$了；也就是每次提问，获得熵为1的信息量。提问五次，就可获得总共熵为5的信息量了。
有人会问，假如我直接问：你想的数是5，而你回答是，不是一次就够了吗？是的，如果运气好。但要运气不好呢？你平均问的次数应该要远远超过五次。
