Computer Science Theory for the Information Age-2: 高维空间中的正方体和Chernoff Bounds

高维空间中的正方体和Chernoff Bounds

    本文将介绍高维空间中正方体的一些性质，以及一个非常常见也是非常有用的概率不等式——Chernoff Bounds。

    考虑 $d$ 维单位正方体 $C=\{x|0\leq x_i\leq 1,i=1,\cdots,d\}$ ，其中心点为 $(\frac{1}{2},\cdots,\frac{1}{2})$ ，体积为1。现在我们将其半径收缩到 $1-\frac{c}{d}$ ，其体积为 $(1-\frac{c}{d})^d\leq e^{-c}$ ，所以当 $d$ 很大时，高维正方体的体积总是分布在其边缘地带。

    定义超平面 $H=\{x|\sum_{i=1}^dx_i=\frac{d}{2}\}$ ，即过中心点但不过原点的对角面。现在我们从正方体 $C$ 中均匀随机的产生观察点 $x$ （相当与从 $[0,1]$ 独立均匀的选取 $x_1,\cdots,x_d$ ）， $x=(x_1,x_2,\cdots,x_d)$ 到 $H$ 的距离为：

$$\begin{equation} L=\frac{1}{\sqrt{d}}|(\sum_{i=1}^dx_i-\frac{d}{2}|\end{equation}$$

这个距离平方的期望为:

$$\begin{equation}\mathbb{E}(L^2)=\frac{1}{d}\mathbb{E}[(\sum_{i=1}^dx_i-\frac{d}{2})^2]=\frac{1}{d}\mathop{Var}[\sum_{i=1}^dx_i]=\frac{1}{d}\frac{d}{12}=\frac{1}{12}\end{equation}$$

其中 $\mathbb{E}(\sum_{i=1}^dx_i)=\frac{d}{2}, \mathop{Var}(\sum_{i=1}^dx_i)=\frac{d}{4}$ 。所以根据Markov不等式 $\mathbb{P}(|x|\geq a)\leq\frac{\mathbb{E}(|x|)}{a}$ 可得：

$$\mathbb{P}(L\geq t)=\mathbb{P}(L^2\geq t^2)\leq\frac{\mathbb{E}(L^2)}{t^2}=\frac{1}{12t^2}$$

因此我们可以得到如下引理：

引理一 在 $C$ 内随机均匀的选一点，则该点到超平面的距离在 $t$ 以内的概率至少为 $1-\frac{1}{12t^2}$ ，即 $\mathbb{P}(L\leq t)\geq1-\frac{1}{12t^2}$ 。

 接下去，我们将证明一个比引理一更一般的引理，这个引理在证明Chernoff Bounds时会用到。

引理二 令 $x_1,x_2,\cdots,x_d$ 为独立的随机变量，且 $0\leq x_i \leq 1$ ， $\mathbb{E}(x_i)=p_i$ 。令 $y_i=x_i-p_i$ ，且记 $\mu=\sum_{i=1}^dp_i$ 。那么对任意的正整数 $n$ 有：

$$\begin{equation}\mathbb{E}[(\sum_{i=1}^dy_i)^n]\leq \mathop{Max}\{(2n\mu)^\frac{n}{2},n^n\}\end{equation}$$

 证明：首先，我们将 $(y_1+y_2+\cdots+y_d)^n$ 写成单项式的求和形式，即 $(y_1+y_2+\cdots+y_d)^n=\sum_{I\in S}\prod_{i\in I}y_i^{r_i}$ ，其中 $r_i$ 表示在每一个单项式中 $y_i$ 出现的次数， $I$ 表示非零 $r_i$ 对应的下标集合， $S=\{I|\sum_{i\in I}r_i=n\}$ 。所以 $\mathbb{E}[(y_1+y_2+\cdots+y_d)^n]=\mathbb{E}[\sum_{I\in S}\prod_{i\in I}y_i^{r_i}]$ 。

    现在我们先计算其中单个单项式的期望。由于随机变量之间的相互独立性，所以 $\mathbb{E}(\prod_{i\in I}y_i^{r_i})=\prod_{i\in I}\mathbb{E}(y_i^{r_i})$ ，另外又因为 $\mathbb{E}(y_i)=0$ ，所以这里我们可以只考虑 $r_i\geq 2$ ，所以每个集合 $I$ 的大小将小于等于 $\frac{n}{2}$ ，即 $|I|\leq\frac{d}{2}$ 。由于 $y_i\in [-p_i,1-p_i]$ ，所以：

$$\begin{align*}\mathbb{E}[|y_i^{r_i}|]&\leq\mathbb{E}(y_i^2)=\mathbb{E}[(x_i-p_i)^2]\\&=\mathbb{E}(x_i^2)-p_i^2\leq \mathbb{E}(x_i^2)\leq\mathbb{E}(x_i)=p_i\end{align*}$$

因此，

$$\prod_{i\in I}\mathbb{E}(y_i^{r_i})\leq \prod_{i\in I}\mathbb{E}(|y_i^{r_i}|)\leq\prod_{i\in I}p_i\triangleq p(I)$$

也就是每个单项式的期望不会超过 $p(I)$ ，所以 $\mathbb{E}[(\sum_{i=1}^dy_i)^r]\leq\sum_{I,|I|\leq\frac{n}{2}}p(I)N(I)$ ，其中 $N(I)$ 表示此单项式出现的次数。且 $I$ 对应的单项式数量不会超过按如下方式产生的单项式数量，即每次从 $|I|$ （因为该单项式只有 $|I|$ 个因子可供选择）中选择一个因子，然后选择 $n$ 次，故 $n(I)\leq |I|^n$ 。

    同时，

$$\begin{align}\sum_{I:|I|=t}p(I)&=\sum_{I:|I|=t}(\prod_{i\in I}p_i)\leq (\sum_{i=1}^dp_i)^t\frac{1}{t!}\label{equ:exp1}\\&=\frac{\mu^t}{t!}\approx\frac{\mu^t}{\sqrt{2\pi t}(\frac{t}{e})^t}\label{equ:exp2}\end{align}$$

其中等式 $\ref{equ:exp1}$ 成立的原因：所有 $t$ 个不同的 $p_i$ 相乘的和必定小于从全部的 $d$ 个 $p_i$ 中选 $t$ 次，并且把重复的 $t!$ 个排列当成相同的单项式。等式 $\ref{equ:exp2}$ 成立是因为 $t!\approx \sqrt{2\pi t}(\frac{t}{e})^t$ 。所以：

$$\begin{equation}\mathbb{E}[(\sum_{i=1}^d)^r]\leq\sum_{t=1}^\frac{r}{2}\frac{\mu^tt^n}{\sqrt{2\pi}t^te^{-t}}\leq\frac{\mathop{Max}_{t=1}^\frac{n}{2}f(t)}{\sqrt{2\pi}}\sum_{t=1}^\frac{r}{2}t^n\end{equation}$$

这里 $f(t)=\frac{(e\mu)^t}{t^t}$ 。对 $f(t)$ 求导可知，在 $t<\mu$ 时， $f(t)$ 为增函数；在 $t>\mu$ 时， $f(t)$ 为减函数。故我们可以分两种情况讨论：1）当 $\mu<\frac{n}{2}$ 时， $\mathop{Max}_{t=1}^\frac{n}{2}f(t)=f(\mu)=e^\mu\leq e^\frac{n}{2}$ ；2）当 $\mu>\frac{n}{2}$ 时， $\mathop{Max}_{t=1}^\frac{n}{2}f(t)=f(\frac{n}{2})\leq\frac{(2e\mu)^\frac{n}{2}}{n^\frac{n}{2}}$ 。所以：

$$\begin{align}\mathbb{E}[(\sum_{i=1}^dy_i)^r]&\leq\frac{2}{\sqrt{2\pi}}\mathop{Max}[(\frac{2e\mu}{n})^\frac{n}{2},e^\frac{n}{2}](\frac{n}{2})^n\label{equ:exp3}\\&\leq\mathop{Max}[(\frac{en\mu}{2})^\frac{n}{2},(\frac{en^2}{4})^\frac{n}{2}]\nonumber\\&\leq\mathop{Max}[(2n\mu)^\frac{n}{2},n^n]\nonumber\end{align}$$

其中利用了不等式 $\sum_{t=1}^\frac{n}{2}t^n\leq\int_{0}^{\frac{n}{2}}x^ndx\leq\frac{n}{2(n+1)}(\frac{n}{2})^n\leq\frac{1}{2}(\frac{n}{2})^n$ 。

    好了，有了上面的这个引理后，我们就可以证明这个有用的Chernoff Bounds。

定理一 Chernoff Bounds

假设 $x_i,y_i,\mu$ 与引理二中的一样，那么：

$$\begin{equation}\mathbb{P}(|\sum_{i=1}^d|\geq t)\leq 3e^{-\frac{t^2}{12\mu}},\quad\text{for } 0<t\leq 3\mu\label{equ:cher1}\end{equation}$$

$$\begin{equation}\mathbb{P}(|\sum_{i=1}^d|\geq t)\leq 2\times 2^{-\frac{t}{3}},\quad\text{for } t>3\mu\label{equ:cher2}\end{equation}$$

证明：令 $r$ 为正偶数， $y=\sum_{i=1}^dy_i$ ，所以 $y^r$ 是非负的。根据Markov不等式有： $\mathbb{P}(|y|\geq t)=\mathbb{P}(y^r\geq t^r)\leq\frac{\mathbb{E}(y^r)}{t^r}$ 。根据引理二，有 $\mathbb{P}(|y|\geq t)\leq\mathop{Max}[\frac{(2r\mu)^\frac{r}{2}}{t^r},\frac{r^r}{t^r}]$ ，对所有 $r$ 为偶数均成立。

    经过简单的计算（求导），我们可以知道 $\frac{(2r\mu)^\frac{r}{2}}{t^r}$ 的最小值在点 $r_{min}=\frac{r^2}{2e\mu}$ 处取得。由于 $r_{min}$ 不一定会是偶数，所以我们取不超过 $r_{min}$ 的最大偶数 $r$ ，且：

1）对所有的 $t$ :

$$\begin{align} (\frac{2r\mu}{t^2})^{-\frac{r}{2}}&\leq e^{-\frac{r}{2}}\label{equ:exp4}\\&\leq e^{1-\frac{t^2}{4e\mu}}\label{equ:exp5}\\&\leq 3e^{-\frac{t^2}{12\mu}}\label{equ:1}\end{align}$$

其中不等式 $\ref{equ:exp4}$ 是由于 $r\leq\frac{t^2}{2e\mu}$ ，不等式 $\ref{equ:exp5}$ 是由于 $\frac{r_{min}-r}{2}\leq 1\Longrightarrow -\frac{r}{2}\leq 1-\frac{r_{min}}{2}$ .

2）当 $0<t\leq 3\mu$ 时，

$$\begin{align}\frac{r^r}{t^r}&\leq(\frac{t}{3e\mu})^r\leq(\frac{3\mu}{2e\mu})^r=(\frac{2e}{3})^{-r}\nonumber\\&\leq(\sqrt{e})^{-r}=e^{-\frac{r}{2}}<3e^{-\frac{t^2}{12\mu}}\label{equ:2}\end{align}$$

综合不等式 $\ref{equ:1}$ 和 $\ref{equ:2}$ 可知，不等式 $\ref{equ:cher1}$ 成立。

    对于第二个不等式，选择 $r$ 为不超过 $\frac{2}{3}t$ 的最大偶数，即 $r\leq\frac{2}{3}t$ 。又 $t>3\mu$ ，故有：

$$\begin{equation}\frac{r^r}{t^r}\leq(\frac{4}{9})^\frac{r}{2}\leq(\frac{1}{2})^\frac{r}{2}=2^{-\frac{r}{2}}\end{equation}$$

$$\begin{equation}(\frac{2\mu r}{t^2})^\frac{r}{2}\leq(\frac{2tr}{3t^2})^\frac{r}{2}=(\frac{2}{3}\frac{r}{t})^\frac{r}{2}\leq\frac{1}{2}^\frac{r}{2}=2^{-\frac{r}{2}}\end{equation}$$

所以 $\mathop{Max}[\frac{(2r\mu)^\frac{r}{2}}{t^r},\frac{r^r}{t^r}]\leq 2^{-\frac{r}{2}}$ 。由于 $\frac{\frac{2}{3}t-r}{2}\leq 1\Longrightarrow -\frac{r}{2}\leq 1-\frac{t}{3}$ ，所以 $2^{-\frac{r}{2}}\leq 2^{1-\frac{t}{3}}=2\times 2^{-\frac{t}{3}}$ ，所以不等式 $\ref{equ:cher2}$ 成立

Computer Science Theory for the Information Age-2: 高维空间中的正方体和Chernoff Bounds,布布扣,bubuko.com

Computer Science Theory for the Information Age-2: 高维空间中的正方体和Chernoff Bounds

原文：http://www.cnblogs.com/boostable/p/iage_high_space_cube_chernoff.html