熵为什么小于logn

化的指标（详情参考wiki）。在信息论中，熵用来表示信息的不确定性的程度。什么是不确定性程度呢？简单地说，不确定性越多，我们就需要越多的信息来了解，信息越多，不确定性也就越大，比如我们需要搞清楚一件非常不确定的事，就需要大量的信息。举个例子，我们在和同学吃饭时偶尔会玩的猜数字游戏，一个同学A确定好(0,100)的数字，然后其他同学轮流猜。B同学很可能会猜50，然后确定A同学会告诉那个数字是否为50，如果不是，是在(0,50)还是(51,100)的数字，然后C同学也很可能会再折半猜数字。这个折半猜有什么好处呢？如果大家学过计算机程序设计的二分查找算法的话，就会知道这样折半查找平均情况下是最快的，查找平均复杂度为O(log n)（底数为2，原因是我们每查找一次，就可以减少一半的搜索范围），意思是说我们最多用log n这样的查找次数就能查找到我们需要的数字了，但是前提是给我们的数据是有序的。所以猜数字游戏最多猜7次就能成功了！我们就说A同学的数字的信息量为7，用计算机二进制的编码来解释的话，用7个二进制位就能表示0-100内的所有数字啦。

假设考虑一个离散的随机变量x，对x的信息度量要考虑到x的概率分布。显然，如果x只有一个值a，P(x=a)=1，则它的信息含量为0，不确定性程度为0，这是个必然事件，比如说明天太阳从东方升起，一般情况下我们对确定性事件都没多大兴趣。假设h(x)是描述p(x)不确定性程度的量化函数，如果有两个不相关的事件x和y，则观察到它们同时发生的信息含量为h(x,y)=h(x)+h(y)，而x和y是不相关事件，我们有p(x,y)=p(x)p(y)。容易看出h(x)是p(x)的对数函数，h(x) = ?log2 p(x)。如果p(x)很小，显然h(x)很大，不确定性很大，如果p(x)为1，则不确定性为0。如果发送者要发送随机变量x给接受者的话，那么，平均的信息期望值为

这里的x有n个值，每个值出现的概率分别为p_i(x)，上面的公式就是信息熵。如果x是个连续值，按照积分公式表示平均信息期望值为

现在假设X和Y两个随机变量，X是我们需要了解的，那么X的熵的定义我们在上面已经给出来了，它的不确定性就是那样大。现在假定我们还知道Y的一些情况，包括它和X一起出现的概率（联合概率分布）以及给定