高维空间中的正方体和Chernoff Bounds
本文将介绍高维空间中正方体的一些性质,以及一个非常常见也是非常有用的概率不等式——Chernoff Bounds。
考虑di
≤1,i=1,?,d}
2
,?,1
2
)
d
d
)
d
≤e
?c
定义超平面H=\{x|\sum_{i=1}^dx_i=\frac{d}{2}\}d
i=1
x
i
=d
2
}
1
,?,x
d
1
,x
2
,?,x
d
)
\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