数据科学基础 (Fall 2024)/Volume of Hamming balls: Difference between revisions

From TCS Wiki
Jump to navigation Jump to search
VisualWikitext
Created page with "在求解抛掷公平硬币（fair coin）的尾概率时，我们经常会需要分析如下二项式系数求和： :<math>\sum_{k=0}^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 49: Line 49:
:<math>\sum_{k\le pn}{n\choose k}\ge 2^{n\cdot (h(p)-o(1))}</math>
:<math>\sum_{k\le pn}{n\choose k}\ge 2^{n\cdot (h(p)-o(1))}</math>
因此，上述汉明球体积上界在此渐近意义下是紧的。
因此，上述汉明球体积上界在此渐近意义下是紧的。
----
在上述的初等证明之外，我们也可以对这一汉明球体积上界给出一个利用香农信息熵的非初等证明，这一证明也可为该上界提供一些在信息论意义下的直观解释。
离散随机变量 <math>X</math> 的'''香农信息熵''' ([https://en.wikipedia.org/wiki/Entropy_(information_theory) Shannon entropy]) 定义如下：
:<math>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>p_X(x)</math> 为正的 <math>x</math> 值。
之前所述的二进制熵函数 <math>h(p)</math> 实为参数 <math>p</math> 的伯努利变量 <math>X\sim\mathrm{Bernoulli}(p)</math> 的香农信息熵：
:<math>h(p)=H(X)=p\log_2\frac{1}{p}+(1-p)\log_2\frac{1}{1-p}</math>
容易验证：对于任意<math>q\le p\le 1/2</math>，都有 <math>h(q)\le h(p)=h(1-p)\le h(1/2)=1</math>；即：正面概率为 <math>p=1/2</math> 的时候，一个硬币有最大的熵（随机性、不确定性），为1'''比特'''。
同时，对于独立的离散随机变量 <math>X_1,X_2,\ldots,X_n</math>，容易验证其'''联合信息熵'''有：
:<math>H(X_1,X_2,\ldots,X_n)=\mathbb{E}\left[\log_2\frac{1}{p_{X_1,\ldots,X_n}(X_1,\ldots,X_n)}\right]=\sum_{i=1}^n\mathbb{E}\left[\log_2\frac{1}{p_{X_i}(X_i)}\right]=\sum_{i=1}^nH(X_i)</math>
对于一般的随机向量 <math>(X_1,X_2,\ldots,X_n)</math>，信息熵总是具有如下的'''次可加性''' (subadditivity)：
:<math>H(X_1,X_2,\ldots,X_n)\le \sum_{i=1}^nH(X_i)</math>
次可加性是香农信息熵的一个相当普世也是非常基本的性质，这一性质由熵的定义保证。直观上这代表了：对于任何一组边缘分布确定的随机变量而言，总体的熵（随机性、不确定性）在变量之间独立时达到最大。
关于信息熵的另一个非常直接的性质是：在任意非空有穷集合 <math>U</math> 上均匀分布的随机变量 <math>X</math>，它的信息熵都是：
:<math>H(X)=\mathbb{E}\left[\log_2\frac{1}{p_X(X)}\right]=\mathbb{E}\left[\log_2|U|\right]=\log_2|U|</math>
有了上述这些工具之后，我们可以对汉明球的体积上界给出另外一个基于信息熵的证明。
{{Proof|
（信息论证明）
令 <math>B_{pn}=\left\{x\in \{0,1\}^n\mid \sum_{i=1}^nx_i\le pn\right\}</math> 表示以 <math>\boldsymbol{0}=0^n</math> 向量为圆心、半径 <math>pn</math> 的汉明球，则显然：
: <math>|B_{pn}|=\sum_{k\le pn}{n\choose k}</math>
令随机变量 <math>X\in B_{pn}</math> 在集合 <math>B_{pn}</math> 上均匀分布，于是：
:<math>H(X)=\log_2|B_{pn}|=\log_2\left(\sum_{k\le pn}{n\choose k}\right)</math>
另一方面，该 <math>X\in B_{pn}\subseteq\{0,1\}^n</math> 其实是一个 <math>n</math>维随机向量 <math>X=(X_1,X_2,\ldots,X_n)\in\{0,1\}^n</math>，且根据 <math>B_{pn}</math> 的定义总是有：
:<math>\sum_{i=1}^nX_i\le pn</math>
于是 <math>\mathbb{E}\left[\sum_{i=1}^nX_i\right]\le pn</math>。另外根据对称性，易见各 <math>X_i</math> 具有相同边缘分布，于是：
:<math>\mathbb{E}\left[X_1\right] = \mathbb{E}\left[X_2\right] =\cdots = \mathbb{E}\left[X_n\right] \le p</math>
考虑到我们假设 <math>p\le 1/2</math>，这意味着：
:<math>H(X_i)\le h(p)=p\log_2\frac{1}{p}+(1-p)\log_2\frac{1}{1-p}</math>
根据 <math>X=(X_1,X_2,\ldots,X_n)</math> 的熵的次可加性：
:<math>\log_2\left(\sum_{k\le pn}{n\choose k}\right)=H(X)=H(X_1,X_2,\ldots,X_n)\le \sum_{i=1}^nH(X_i)\le nh(p)</math>
证毕
}}
该证明的直观解释是：在 <math>n</math> 维汉明球内一个随机点的联合熵，不会超过将这个点拆分成 <math>n</math> 个独立硬币的熵。前者与汉明球的体积有关，后者通过二进制熵函数容易计算。

Latest revision as of 07:39, 22 September 2024

在求解抛掷公平硬币（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]

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

Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=数据科学基础_(Fall_2024)/Volume_of_Hamming_balls&oldid=12593"