lower bound定理

Lower bound定理，也称下界定理，是信息论中一个非常重要的定理。它描述了一个离散源产生符号序列的最小平均编码长度下界的存在性。

下界定理的表述如下：

对于一个离散源产生的符号序列，假设其符号集大小为M，每个符号出现的概率为p1, p2, ..., pM。如果存在一种编码方案，使得其平均编码长度L小于H(p1, p2, ..., pM)，则必定存在另一种编码方案，使得其平均编码长度L'不小于H(p1, p2, ..., pM)，其中H(p1, p2, ..., pM)为该符号集的熵。

也就是说，对于任何一种编码方案，其平均编码长度都不可能小于该离散源的熵。在信息编码中，这个下界被称为Shannon下界，它是一种理论上的极限，反映了离散源的信息量的最小值。

需要注意的是，下界定理并不是说任何一种编码方案都可以达到Shannon下界，而是存在一种编码方案可以达到Shannon下界。因此，在实际编码中，我们需要通过选择合适的编码方案来尽可能地接近这个下界。