概率论与数理统计 (Spring 2023)/Entropy and volume of Hamming balls
在求解抛掷公平硬币(fair coin)的尾概率时,我们经常会需要分析如下二项式系数求和:
- [math]\displaystyle{ \sum_{1\le k\le 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_{1\le k\le r}{n\choose k} }[/math]