关于熵的一些随笔——从物理学到信息理论

在微观的角度，熵是描述一个系统混乱程度的量度，满足玻尔兹曼关系： \[ S=kln\Omega \] 其中Ω是一个系统的可能状态数目。从公式上看，熵只是微观状态可能数量的对数，和混乱程度不是很搭边。但在物理学的语境中，根据热力学第二定律，孤立系统的熵永不减少，也就意味着一个孤立系统在演化的过程中最终会达到一个平衡态，并且这个平衡态的熵是极大值。对应到微观下，就是在总能量与粒子数保持不变的情况下，处于平衡态时这个系统的粒子会处于这样的一个分布：这个分布会让系统中总的可能微观状态数目达到极大值： \[ δS=kδlnΩ=0 \] 当粒子总能量和数目保持不变，但在往平衡态进行演化的时候，可能的微观状态数却越来越多，那么这个系统“看起来”确实就越来越混乱了。

在认识到“混乱程度”和可能粒子数目的关系等价是基于孤立的热力学系统这一基础上，我们注意到了熵的玻尔兹曼关系只表示了系统的可能微观状态数，这里面并没有对系统本身进行任何假设，因此尽管熵最初来自于平衡态或者非平衡态到平衡态之间的准静态过程，但不管系统本身处于什么状况，我们总可以定义这个量度来表示它可能的微观状态数目。

至于为什么取对数，最直接的原因就是熵要满足广延量的需求。对于一个系统1，它可能的微观状态数目是\(Ω_1\)，对于系统2，它可能的微观状态数目是\(Ω_2\)，那么将系统1和系统2看作一个整体\(Ω\)，并且系统1和系统2的成员是互不相交的，我们很容易得出，合系统的可能微观状态数目为： \[ Ω=Ω1⋅Ω2 \] 当一个系统熵的定义和其可能的微观状态数是对数关系时，那么自然满足广延量需求了： \[ lnΩ=lnΩ1+lnΩ2⇒S=S1+S2 \] 并且，注意到对数的底取任意值是不影响到广延量性质时，我们便可以将熵和信息的表示关联起来了。对于一个长度为N的二进制数，其可能的状态数目为2N，假设我们定义它的熵为取2的对数，那么这个二进制数的熵正好就是N。也就是说，在信息理论中，熵又可以表示表示一条可能状态为\(Ω\)的信息需要的最小比特数。

现在我们利用熵来解答leetcode 458. 可怜的小猪：

有buckets桶液体，其中正好有一桶含有毒药，其余装的都是水。它们从外观看起来都一样。为了弄清楚哪只水桶含有毒药，你可以喂一些猪喝，通过观察猪是否会死进行判断。不幸的是，你只有minutesToTest分钟时间来确定哪桶液体是有毒的。

喂猪的规则如下：

选择若干活猪进行喂养可以允许小猪同时饮用任意数量的桶中的水，并且该过程不需要时间。小猪喝完水后，必须有minutesToDie分钟的冷却时间。在这段时间里，你只能观察，而不允许继续喂猪。过了minutesToDie分钟后，所有喝到毒药的猪都会死去，其他所有猪都会活下来。重复这一过程，直到时间用完。给你桶的数目buckets,minutesToDie 和minutesToTest，返回在规定时间内判断哪个桶有毒所需的最小猪数。

buckets桶液体，只有1桶有毒，那么总共有buckets种可能，表示这条信息需要的熵为

log(buckets)

一头小猪死亡后，死亡的原因只能是它所喝的n次水中有一次有毒，一共n种可能。根据题设，小猪最多能喝\([\frac{minutesToDie}{minutesToTest}]+1\)次水，那么小猪能提供的信息熵就是 \[ log([\frac{minutesToDie}{minutesToTest}]+1) \]

我们要用n头猪来得到哪个桶有毒，根据熵的广延性，这n头猪能得到的信息熵为 \[ S=nlog([\frac{minutesToDie}{minutesToTest}]+1) \]

既然熵的意义是表示一条信息所需要的最小比特数，那么要用这几头猪的信息得到有毒桶的信息，猪的熵必须大于等于桶的，因此： \[ n=ceil(\frac{log(buckets)}{log([\frac{minutesToDie}{minutesToTest}]+1)}) \]

code如下：

class Solution {
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
        if(buckets == 1) return 0; 
        return ceil((entropy(buckets)/entropy((int)(minutesToTest/minutesToDie)+1)));
    }

    float entropy(int info){
        if(info == 1){
            return 1;
        }
        return log(info);
    }
};