概率论与数理统计 (Spring 2023)/Entropy and volume of Hamming balls: Difference between revisions
(Created page with "在求解抛掷公平硬币(fair coin)的尾概率时,我们经常会需要分析如下二项式系数求和: :<math>\sum_{1\le k\le r}{n\choose k}</math>,对于某个<math>1\le r\le n</math> 这其实等价与求一个 <math>n</math> 维汉明空间中半径为 <math>r</math> 的球的体积。 :{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;...") |
No edit summary |
||
Line 1: | Line 1: | ||
在求解抛掷公平硬币(fair coin)的尾概率时,我们经常会需要分析如下二项式系数求和: | 在求解抛掷公平硬币(fair coin)的尾概率时,我们经常会需要分析如下二项式系数求和: | ||
:<math>\sum_{ | :<math>\sum_{k=0}^r{n\choose k}</math>,对于某个<math>1\le r\le n</math> | ||
这其实等价与求一个 <math>n</math> 维汉明空间中半径为 <math>r</math> 的球的体积。 | 这其实等价与求一个 <math>n</math> 维汉明空间中半径为 <math>r</math> 的球的体积。 | ||
:{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" | :{|border="2" width="100%" cellspacing="4" cellpadding="3" rules="all" style="margin:1em 1em 1em 0; border:solid 1px #AAAAAA; border-collapse:collapse;empty-cells:show;" | ||
Line 8: | Line 8: | ||
:: <math>B_r(o)=\left\{x\in \{0,1\}^n\mid d(x,o)\le r\right\}</math> | :: <math>B_r(o)=\left\{x\in \{0,1\}^n\mid d(x,o)\le r\right\}</math> | ||
:容易验证,对于任何圆心 <math>o\in\{0,1\}^n</math>,半径为 <math>r</math> 的汉明球体的体积,均为: | :容易验证,对于任何圆心 <math>o\in\{0,1\}^n</math>,半径为 <math>r</math> 的汉明球体的体积,均为: | ||
:: <math>|B_r(o)|=\sum_{ | :: <math>|B_r(o)|=\sum_{k\le r}{n\choose k}</math> | ||
|} | |} | ||
这一对二项式系数的求和式相当常见。然而不幸地,除对于极少数特殊的 <math>r</math> 取值之外,我们对于这一求和式并没有通用的闭合形式解。但有如下的上界总是成立。 | |||
{{Theorem|Lemma| | |||
:对于任何 <math>p\in\left[0,\frac{1}{2}\right]</math>,有: | |||
::<math>\sum_{k\le pn}{n\choose k}\le 2^{n\cdot h(p)}</math> | |||
:这里 <math>h(p)</math> 为'''二进制信息熵函数''' ([https://en.wikipedia.org/wiki/Binary_entropy_function binary entropy function]),定义如下: | |||
::<math>h(p)=p\log_2\frac{1}{p}+(1-p)\log_2\frac{1}{1-p}</math> | |||
}} | |||
对此上界,有一个比较初等的计算证明。 | |||
{{Proof| | |||
<math> | |||
\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>n,p</math> 的二项分布的概率质量求和。 | |||
}} |
Revision as of 13:11, 24 May 2023
在求解抛掷公平硬币(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]
- 对于任何 [math]\displaystyle{ p\in\left[0,\frac{1}{2}\right] }[/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]