概率论与数理统计 (Spring 2023)/Entropy and volume of Hamming balls

在求解抛掷公平硬币（fair coin）的尾概率时，我们经常会需要分析如下二项式系数求和：

[math]\displaystyle{ \sum_{k=0}^r{n\choose k} }[/math]，对于某个[math]\displaystyle{ 1\le r\le n }[/math]

这其实等价与求一个 [math]\displaystyle{ n }[/math] 维汉明空间中半径为 [math]\displaystyle{ r }[/math] 的球的体积。

[math]\displaystyle{ n }[/math] 维汉明空间（[math]\displaystyle{ n }[/math]-dimensional Hamming space）是如下的度量空间 [math]\displaystyle{ \left(M,d\right) }[/math]：该度量空间点集为 [math]\displaystyle{ M=\{0,1\}^n }[/math]；距离 [math]\displaystyle{ d(\cdot,\cdot) }[/math] 为该点集上的汉明距离 (Hamming distance)，即——对于任意 [math]\displaystyle{ x,y\in\{0,1\}^n }[/math]，[math]\displaystyle{ d(x,y)=\sum_{i=1}^n|x_i-y_i| }[/math]。 以某点 [math]\displaystyle{ o\in\{0,1\}^n }[/math] 圆心、半径为 [math]\displaystyle{ r }[/math] 的汉明球体 (Hamming ball) 为如下的点集： [math]\displaystyle{ B_r(o)=\left\{x\in \{0,1\}^n\mid d(x,o)\le r\right\} }[/math] 容易验证，对于任何圆心 [math]\displaystyle{ o\in\{0,1\}^n }[/math]，半径为 [math]\displaystyle{ r }[/math] 的汉明球体的体积，均为： [math]\displaystyle{ |B_r(o)|=\sum_{k\le r}{n\choose k} }[/math]

该二项式系数的求和式相当常见。然而不幸地，除对于极少数特殊的 [math]\displaystyle{ r }[/math] 取值之外，我们对于这一求和式并没有通用的闭合形式解。

对于占整个空间不超过一半的汉明球体，其体积有如下的上界总是成立。

Lemma

对于任何 [math]\displaystyle{ p\in\left[0,\frac{1}{2}\right] }[/math]，有： [math]\displaystyle{ \sum_{k\le pn}{n\choose k}\le 2^{n\cdot h(p)} }[/math] 这里 [math]\displaystyle{ h(p) }[/math] 为二进制信息熵函数 (binary entropy function)，定义如下： [math]\displaystyle{ h(p)=p\log_2\frac{1}{p}+(1-p)\log_2\frac{1}{1-p} }[/math]

对此上界，有一个比较初等的计算式证明。

Proof. [math]\displaystyle{ \begin{align} \sum_{k\le pn}{n\choose k}/2^{n\cdot h(p)} &= \sum_{k\le pn}{n\choose k}p^{pn}(1-p)^{(1-p)n}\\ &= \sum_{k\le pn}{n\choose k}(1-p)^n\left(\frac{p}{1-p}\right)^{pn}\\ &\le \sum_{k\le pn}{n\choose k}(1-p)^n\left(\frac{p}{1-p}\right)^{k} &&(\text{因为 } p\le 1/2\le 1-p \text{ 以及 } k\le pn)\\ &= \sum_{k\le pn}{n\choose k}(1-p)^{n-k}p^k\\ &\le \sum_{k=0}^n{n\choose k}(1-p)^{n-k}p^k\\ &=1 \end{align} }[/math] 最后一个等式是因为这是在对参数为 [math]\displaystyle{ n,p }[/math] 的二项分布的概率质量求和。 [math]\displaystyle{ \square }[/math]

与此同时，利用 Stirling公式，可以验算得到形式如下的下界：

[math]\displaystyle{ \sum_{k\le pn}{n\choose k}\ge 2^{n\cdot (h(p)-o(1))} }[/math]

因此，上述汉明球体积上界在此渐近意义下是紧的。

另外，我们也可以对这一汉明球体积上界给出一个利用香农信息熵的非初等证明，这一证明也可为该上界提供一些在信息论意义下的直观解释。

令 [math]\displaystyle{ X }[/math] 为一离散随机变量。[math]\displaystyle{ X }[/math] 的香农信息熵 (Shannon entropy) 定义如下：

[math]\displaystyle{ H(X)=\mathbb{E}\left[\log_2\frac{1}{p_X(x)}\right]=\sum_{x}p_X(x)\log_2\frac{1}{p_X(x)} }[/math]

此处的求和是穷举所有概率质量 [math]\displaystyle{ p_X(x) }[/math] 为正的 [math]\displaystyle{ x }[/math] 值。

之前所述的二进制熵函数 [math]\displaystyle{ h(p) }[/math] 实为参数 [math]\displaystyle{ p }[/math] 的伯努利变量 [math]\displaystyle{ X\sim\mathrm{Bernoulli}(p) }[/math] 的香农信息熵：

[math]\displaystyle{ h(p)=H(X)=p\log_2\frac{1}{p}+(1-p)\log_2\frac{1}{1-p} }[/math]