第三百四十二章 香农的信息熵 (9 / 10)
        正是如此！

        那咱们看看典型序列一共有多少个。把这个要算的数记作T。

        首先注意一下每个典型序列有多大的概率被老千掷出来。因为每个典型序列“差不多”由n/3个1和2n/3个0组成，而这个序列中的所有随机变量又是相互独立的，那么，每个典型序列被掷出来的概率“差不多”就是(1/3)^(n/3)*(2/3)^(2n/3)。不知道同学们注意到没有，每个典型序列被掷出来的概率“差不多”都是这个数。同时注意到只有典型序列才可能被掷出来，也就是说，所有典型序列出现的概率之和“差不多”就是1。这样俺们就可以得出，典型序列的数目T“差不多”就是1除以每个典型序列出现的概率，也就是

        1/((1/3)^(n/3)*(2/3)^(2n/3))=(1/3)^(-n/3)*(2/3)(-2n/3).

        针对这T个序列问问题，就“差不多”等同于俺跟你玩一次这样的“二十个问题”游戏：俺从{1，2，…，T}里取一个数，而且这个数服从均匀分布；然后你问俺“是不是”问题来猜这个数。那么你最少需要多少问题呢？现在回头找到之前让你们用红笔圈出的结论：最优解是二分法；你最少需要的问题总数是logT！而且不管俺取的是哪个数，你都需要这么多问题！

        认真的同学可能会叫板说，哎，这个T也未必是2的整数次方啊，二分法能用吗？！嗯，这个问题不错。但可以这样想，只要把n弄得足够大，总可以让T非常接近2的某个整数次方。而且，即使T真的不是2的整数次方，还可以换一个角度得到我们后面要得到的结论，比如，一定存在一个整数K使得T是在2^K和2^(K+1)之间......总之，当n无穷大的时候，凌乱的世界都变整齐了，这个问题不再是问题了。

        这个最少问题数logT是用来问这个长度为n的硬币序列的。平均到每次掷硬币，平均需要的最少问题数就是（logT）/n。稍微整理一下这个表达式就应该可以看到，这个数字正好等于-(1/3)log(1/3)-(2/3)log(2/3)。

        这也就是压缩这个“老千掷硬币”信息源所需要的最少比特数。

        把这种推演用到任意信息源。如果一个信息源往外蹦的随机变量都独立而且服从同一个定义在S={1，2，…，M}上的分布P(x)，那么以下结论依次成立。

        信息源里蹦出的随机序列几乎可以肯定是典型的！

        每个典型序列出现的概率差不多就是P(1)^(nP(1))*P(2)^(nP(2))*…*P(M)^(nP(M))!

        典型序列的个数T差不多就是P(1)^(-nP(1))*P(2)^(-nP(2))*…*P(M)^(-nP(M))!

        压缩这个信息源蹦出的每个随机变量平均所需要的最少比特数就是(logT)/n！

        内容未完，下一页继续阅读

更多完整内容阅读登陆

《墨缘文学网，https://wap.mywenxue.org》