一些概率论中比较有用的不等式及证明

数学学得太差……
学到现在感觉到现在具体数学的概率期望那一章都没看懂。
作一下笔记。
(其实本篇博文就是cmu 15-859(M)的randomized algorithms的Avrim Blum的01/24/11的notes的翻译。。)
反正就是翻译notes+wiki之类的。。。

马尔科夫不等式

对于一个随机变量X,我们一般都需要衡量一下X”非常”偏离它的期望的概率有多大。
一个比较显然的不等式是 马尔科夫不等式 (Markov’s inequality)
定义$X$为一个非负随机变量,那么对于任意正数k我们都有$Pr[X\geq kE[X]]\leq 1/k$
举个例子就是,随机变量$X$的期望$E[X]$是$10$,那么$X>100$的概率不会超过$1/10$。
否则的话就与$E[X]=10$矛盾。
证明很简单。$E[X]\geq Pr[X\geq t]\times t+Pr[X<t]\times 0=t\times Pr[X\geq t]$

切比雪夫不等式

然后众所周知,为了衡量随机变量随机得有多不均匀,我们定义了随机变量的方差$var[X]=E[(X-E[x])^2]$。
引申一下,我们定义的实际上就是二阶矩。如果扩展一下还可以定义随机变量的高阶矩。。但是我数学太差。。
所以也没弄懂,以后再做笔记吧。
随便推推就知道$var[X]=E[X^2-2XE[x]+E[X]^2]=E[X^2]-E[X]^2$
回归原题,既然定义了方差,那么我们就能够弄出有名的切比雪夫不等式(Chebyshev’s inequality)
如果$X$是一个随机变量,$\mu$是它的期望,$\sigma$是它的标准差(即$\sigma=\sqrt{var[X]}$),那么对于任意正数t,我们都有$Pr[|X-\mu|>t\sigma]\leq 1/t^2$。
证明同样很简单。
$Pr[|X-\mu|>t\sigma]=Pr[(x-\mu)^2>t^2var[X]]$显然。
然后我们估计$Pr[(x-\mu)^2>t^2E[(x-\mu)^2]]$时可以直接套马尔科夫不等式。证明完毕。

切尔诺夫 - 霍夫丁 界

吐槽一下我经常看到的缩写就是Chernoff bounds。。省略掉了Hoeffding。。
而且好像这个玩意是Herman Rubin搞出来的。。但是以Herman Chernoff冠名。
下面说明期望的一些简单性质。
如果随机变量$X=X_1+X_2+\dots+X_n$,其中随机变量$X_i$不一定两两互不相关,那么我们有$E[X]=\Sigma_i E[X_i]$。
如果$X_i$两两互不相关,我们就有$var[X]=\Sigma_i var[X_i]$
证明也很简单。
$$E[X^2]-E[X]^2=\sum_i \sum_j E[X_iX_j]-\sum_i \sum_j E[X_i]E[X_j]=\sum_iE[X_i^2]-\sum_iE[X_i]^2$$
因为如果$X,Y$独立,那么我们有$E[XY]=E[X]E[Y]$,所以$i\not =j$的项都被消去了。
证明完毕。

考虑现在我们抛$n$次硬币,如果正面,得分加1,反面,得分减1,考虑最后得分,这是一个随机变量,我们记作$X$.
然后$X_i$满足$Pr[X_i=-1]=Pr[X_i=+1]=1/2$并且$X_i$互相独立。
所以我们知道$var[X_i]=1$,于是$var[X]=n,\sigma(X)=\sqrt n$,然后切比雪夫不等式告诉我们:
$$Pr[|X|>t\sqrt n]\leq 1/t^2$$
值得注意的是切比雪夫不等式并不关心X能不能被分解成若干个互不相关的随机变量的和,它只关心期望与方差。
但是我们知道$X_i$互相独立,所以我们还能得到更强的结论,$Chernoff\ and\ Hoeffding$ bounds就是说这个情况下,
我们有
$$Pr[|X|>t\sqrt n]\leq e^{-t^2/2}$$
这个估计让概率随着偏移量指数衰减,好过我们通过切比雪夫不等式或者马尔科夫不等式得到的估计。
还有一下几种类似的形式:
$X_i$由n个互相独立的${0,1}$随机变量组成,其中$Pr[X_i=1]=p_i$,($p_i$不一定都相同),然后我们令$S=\sum X_i$,令$\mu=E[S]$,那么$\forall 0\leq \delta \leq 1$,
我们有
$$Pr[S>(1+\delta)\mu]\leq e^{-\delta^2\mu/3}$$
$$Pr[S< (1-\delta)\mu]\leq e^{-\delta^2\mu/2}$$
虽然看起来很不对称,但是这是对的。
还有
$$Pr[S\geq \mu+\delta n]\leq e^{-2n\delta^2}$$
$$ Pr[S\leq \mu-\delta n]\leq e^{-2n\delta^2}$$

以及$\forall k>1$我们有$Pr[S>k\mu]<(\frac{e^{k-1}}{k^k})^{\mu}$.
一般情况的bound与推导:
$Pr(X\geq a)=Pr(e^{t\cdot X}\geq e^{t\cdot a})\leq \frac{E[e^{t\cdot X}]}{e^{t\cdot a}}$由马尔科夫不等式显然。
然后如果$X$是$n$个随机变量$X_i$之和,对于任意正数$t$我们有$Pr(X\geq a)\leq e^{-ta}E[\prod_i e^{t\cdot X_i}]$.
我们知道$Pr(X\geq a)\leq \inf_{t>0} e^{-ta}E[\prod_i e^{t\cdot X_i}]$.
如果$X_i$是互相独立的,那么我们有
$Pr(X\geq a)\leq \inf_{t>0} e^{-ta}\prod_i E[e^{t\cdot X_i}]$.
类似的我们有$Pr(X\leq a)\leq \inf_{t>0} e^{ta}\prod_i E[e^{-t\cdot X_i}]$.
然后我们可以对于具体的分布来最小化$e^{ta}\prod_i E[e^{-t\cdot X_i}]$.

而如我们刚才讨论的,我们可以设$Z=e^{\lambda S}$,那么$Pr[S\geq \mu+\delta n]=Pr[Z\geq e^{\lambda(\mu+\delta n)}]\leq E[Z]/e^{\lambda (\mu+\delta n)}$
既然$X_i$独立,那么对于右式我们知道$E[Z]=E[e^{\lambda X_1}]E[e^{\lambda X_2}]\dots E[e^{\lambda X_n}]$
如果我们有$E[e^{\lambda X_i}]=e^{\lambda E[X_i]}$,那么我们就能得到$E[Z]=e^{\lambda E[S]}=e^{\lambda \mu}$,这样我们就能得到一个估计:
$Pr[S\geq \mu +\delta n]\leq E[Z]/e^{\lambda (\mu+\delta n)}= e^{-\lambda\delta n}$,因为$\lambda$是一个未设定的参数,所以我们可以让它任意大,这么好的情况显然是不切实际的。
令$\mu^*$是使得$Z$取其期望值时的$S$的值,即$S=\mu^*$时,我们有$Z=e^{\lambda S}=E[Z]$,
一个很显然的想法是,在$S$ “不大可能”比$\mu^*$大很多,因为这样会导致$Z$比$E[Z]$大很多(因为$Z$是随着$S$增大而指数增长的),而且在$\lambda$比较大的时候更是如此,另一方面,我们注意到$\lambda$越大,$\mu^*$比起$\mu$就越大(离得越远),我们可以靠这个想法来最优化不等式右边的取值,来得到一个比价好的估计,只要我们能平衡这个矛盾。
具体来说,令$R_i=E[e^{\lambda X_i]}/e^{\lambda p_i}$,因为$X_i$有$p_i$的概率取1,有$1-p_i$的概率取$0$,那么$R_i$很好计算。
$$R_i=\frac{p_ie^{\lambda}+(1-p_i)}{e^{\lambda p_i}}$$.
可以断言,对于任意的$p_i$和$\lambda$我们都有$R_i\leq e^{\lambda^2/8}$,用简单的偏导数的知识就可以证明。左右取对数,就变成了证明$-\lambda p_i+\log (p_ie^{\lambda}+1-p_i) \leq \lambda^2/8$,取一个$p_i$使得$-\lambda p_i+\log (p_ie^{\lambda}+1-p_i)-\lambda^2/8$最大。
先对$p_i$求一下偏导,然后令偏导数为0,就能搞出这个值,然后代入再对$\lambda$求导,我们就会发现$-\lambda p_i+\log (p_ie^{\lambda}+1-p_i)-\lambda^2/8$最大值点为$\lambda=0$时取到,于是我们就证明出来了$R_i\leq e^{\lambda^2/8}$。(为什么是$\lambda^2/8$而不是$\lambda^2/4$或者其它的?讲义的说明是泰勒展开。。然而蠢如我并不知道怎么泰勒展开来证不等式。只会用偏导来验证这是对的。)
这样我们就得到了一个上界:
$$Pr[S\geq \mu +\delta n]\leq E[Z]/e^{\lambda (\mu+\delta n)}\leq e^{n\lambda^2/8-\lambda \delta n}$$
我们取$\lambda=4\delta$,这样我们就得到了一个上界$e^{-2\delta^2n}$于是我们证明了上面情况的一种(一般叫做Additive bounds,由Hoeffding证明)。其它的也是类似的。
(感觉主要是那段放缩我想不到……)

于是我们就有了切尔诺夫 - 霍夫丁界,这个对独立随机变量偏移量估计的不错的不等式。
这个有什么用呢。。
还是挺有用的。。机器学习理论和我现在在学的通信复杂度都在扯这个……
当然应该还有别的用处吧。(说不定能用来出算法竞赛题?)

好了现在我们有了这三个概率论中重要的不等式,所以举个应用的例子。

路径分配问题

给你一个有向图$G$和一些点的二元组${(s_i,t_i)}$,给每个二元组选一条$s_i$到$t_i$的简单路径,使得最拥堵的边的拥堵度最小。
边$e$拥堵度定义为,有多少条你规划的路径经过了$e$。
这个问题是NP-hard的,但是利用刚才的不等式,我们可以得到一个多项式复杂度的近似算法来解这个。

一个非常naive的想法是,对于$s_i$到$t_i$,我们跑网络流,并且允许实数的网络流,起始流量为1。(也就是说我们允许S流1/2流量到T,再用另一条流1/4到T,再用另一条路径流1/4到T),定义$X_{ie}$表示这个情况下$s_i$到$t_i$的流在$e$上分配了多少流量。我们的限制就是流量平衡外加$\forall e,\Sigma_i X_{ie}\leq C$,在有合法解的情况下,最小化C。
具体做可以二分$C$,然后跑网络流,或者上线性规划,反正这两个都有精确的稳定多项式时间复杂度算法。
但是很明显这个问题和原问题并不等价,我们二分出来的$C$并不就是最优解。
那么接下来我们就有一个有趣的想法,既然现在对于$i$,$0\leq X_{ie}\leq 1$,我们不妨把$X_{ie}$看作选这条边的概率,那么选一条$s_i$到$t_i$的路径$L$的概率就是$L$的所有边的权值之积。
然后在这些路径中,我们按上述概率分布随机地选一条路径作为$s_i$到$t_i$的路径。(这个算法很容易实现)
最后输出这个方法。

这个方法看上去就像是在乱搞,但是我们的解能有多好呢?

分析:
$X_{ie}$不仅意味着$s_i$到$t_i$的路径中$e$的流量是多少,也意味着在我们的随机算法中,$e$这条边被选中作$s_i$到$t_i$的路径的一部分的概率(其实很显然,不妨想想为什么)。
所以,对于一条给定的边$e$,考虑随机变量$X_1,X_2,\dots,X_n$,其中$X_i$表示边$e$在$s_i,t_i$中被选中的概率,显然对于给定的边,$X_i$是互相独立的,我们知道它们的期望的和最多是$C$。(C是通过线性规划或网络流求出来的)
使用Chernoff bounds我们知道
$$Pr[total>(1+\epsilon)C]< e^{-\epsilon^2C/3}$$
如果$C>>\log(n)$,那么我们知道随着n的增大有很高的概率有$total<(1+\epsilon)C$
而如果$C$有上界,那么根据Chernoff bounds我们知道$Pr[total>kC]<(e^{k-1}/k^k)^C$,
于是我们设定k为$O(\log(n)/\log \log(n))$,我们就得到了一个$1/poly(n)$的出错概率。

以上就是对这个乱搞做法的一些分析。。为什么不分析$C=O(\log n)$的情况?因为notes里面没讲所以我也不会。。

布尔不等式(union bound或Boole’s inequality)

任一个”至多可数”的随机事件集合,至少一个事件发生的概率小于等于所有事件发生的概率之和。
说的有点绕。
简单说就是
$$Pr(\bigcup_i A_i)\leq \sum_i Pr(A_i)$$
看起来还是很显然的。。
证明归纳法就好。
注意到$Pr(A\cup B)=P(A)+P(B)-P(A\cap B)$,以及取并算子是结合(associative)的,我们就有
$$Pr(\bigcup_{i=1}^{n+1} A_i)=Pr(\bigcup_{i=1}^n A_i)+Pr(A_{n+1})-Pr(\bigcap_{i=1}^n A_i\cap A_{n+1})$$
既然我们知道任意一个事件发生的概率都是非负实数(概率第一公理)。
那么
$$Pr(\bigcap_{i=1}^n A_i\cap A_{n+1})\geq 0$$
于是就有
$$Pr(\bigcup_{i=1}^{n+1} A_i)\leq Pr(\bigcup_{i=1}^n A_i)+Pr(A_{n+1})$$
由归纳假设,我们就有
$$Pr(\bigcup_{i=1}^{n+1} A_i)\leq \sum_{i=1}^n Pr(A_i)+Pr(A_{n+1})$$
然后就归纳出来了。
同样我们并不要求这些事件互相独立。

reference:
http://www.cs.cmu.edu/afs/cs/academic/class/15859m-s11/www/lectures/lect0124.pdf
wikipedia