马尔科夫不等式(Markov's Inequity)

定理(Markov's Inequity):

假设X是一个取值为非负数的随机变量,则对于任何的t>0,满足如下不等式:

Pr[Xt]=E[X]t

证明:

Y为一个布尔变量:

Y={1Xt0X<t

Y很明显满足:E[Y]=Pr[Y=1]=Pr[Xt],所以:

Pr[Xt]=Pr[Y=1]=E[Y]E[Xt]=E[X]t


马尔科夫不等式(Markov's Inequity)是一个非常有用的不等式工具,可以用来证明很多其他的不等式,包括后面将会说明的切比雪夫不等式(Chebyshev's Inequity).

应用举例

马尔科夫不等式一个典型应用是可以用来设计一个可以将Las Vegas算法转化为一个Monte Calo算法1:

假设算法A(x)是一个针对某个判定问题的Las Vegas算法,且它运行时间的期望是T(n),则我们可以设计一种方法将A(x)转化为具有单边错误的Monte Calo的算法B(x):


B(x):

  1. 运行2T(n)时长的A(x)算法。
  2. 如果A(x)返回一个结果,则将该结果直接返回;如果A(x)没能返回结果,就直接返回1.

可以看到,B(x)是一个运行时间确定,但是返回结果不确定的算法,也即是Monte Calo算法。并且,只有当A(x)没有返回结果时,才有可能返回错误解。这是False Postive的单边错误类型。我们可以来计算一下B(x)返回一个错误的解的概率,在这计算过程中,我们就需要用到马尔科夫不等式了。

Pr[]Pr[A(x)2T(n)]E[A(x)]2T(n)=T(n)2T(n)=12

方差(Variance)

定义: 一个随机变量X的方差定义为:

Var[X]=E[(XE[X])2]=E[X2]E[X]2

一个随机变量X的标准差定义为:

δ[X]=Var[X]

需要注意的是,方差期望不一样,是不满足线性可加性的。

定义: 两个随机变量的协方差定义为:

Cov(X,Y)=E[(XE[X])(YE[Y])]

定理: 对于任意的随机变量X1,X2,,Xn,有:

Var[ni=1Xi]=ni=1Var[Xi]+ijCov(Xi,Xj)

证明: 这只需要证明两个随机变量的情况。假设有两个随机变量X,Y,则

Var[X+Y]=E[(X+YE[X+Y])2]=E[(XE[X]+YE[Y])2]=Var[X]+Var[Y]+2Cov(X,Y)


定理: 对于任何两个独立的随机变量XY,有:

E[XY]=E[X]E[Y]

证明: 假设X,Y是两个相互独立的随机变量,则我们可以做如下的推导:

E[XY]=xyPr[X=xY=y]=xyxPr[X=x]yPr[Y=y]=xxPr[X=x]yyPr[Y=y]=E[X]E[Y]


上述第二个等号之所以成立,是因为X,Y相互独立。

利用上述的定理,我们可以证明下面的定理:

对于任何两个独立的随机变量X,Y,它们的协方差为0:

Cov(X,Y) = 0

证明:

Cov(X,Y)=E[(XE[X])(YE[Y])]=E[XE[X]]E[YE[Y]]=0


利用上述的结论,我们可以直接得到下面结论:

定理: 对于两两独立的随机变量X1,X2,,Xn来说,有:

Var[ni=1Xi]=ni=1Var[Xi]

伯努利分布的方差

对于满足伯努利分布的X来说,有:

X={1p01p

则其方差可以直接计算:

Var[X]=E[X2]E[X]2=pp2=p(1p)

二项式分布的方差

二项分布是n个独立的伯努利实验,因此,如果Y是满足二项分布的话,则Y=_i=1nX_i,利用独立性条件,Y的方差可以直接计算:

Var[Y]=Var[ni=1Xi]=ni=1Var[Xi]=ni=1p(1p)=np(1p)

切比雪夫不等式(Chebyshev's Inequity)

在概率统计中,切比雪夫不等式(Chebyshev's Inequity)是一个非常重要的不等式,它给出了比Markov不等式更强的界。它表述如下:

对于任何的t>0,都满足:

Pr[|XE[X]|t]Var[X]t2

证明:

首先,如下等式是肯定成立的:

Pr[|XE[X]|t]=Pr[(XE[X])2t2]

我们可以将(XE[X])2整体看成是一个随机变量,且这个随机变量是非负的,因此我们直接套用Markov不等式:

Pr[|XE[X]|t]=Pr[(XE[X])2t2]E[(XE[X])2]t2=Var[X]t2

问题举例

中位数选择(Median Selection)

中位数选择问题也是一个比较常见的问题,从一个集合S中选择第n2小的数.其实这个问题可以进行推广到从集合中选取第k小的数2,但是在这里我们暂时只讨论特殊情况:只寻找集合S中的中位数。这个寻找过程很直接地可以利用排序来完成,一旦将S排好序了,自然就能找到任意k小的元素了。但是,排序算法的最好代价是O(nlogn),而如果我们利用随机算法的方法的话,可以将时间代价降低为线性时间3

这个随机化的算法被称为是LazySelect,其基本思想是:如果我们能够从集合S中寻找到满足如下条件的元素du:

  1. 中位数m存在于[d,u]中,也即m满足dmu
  2. 位于du之间的元素足够少,也即C=xS|dxu,|C|=o(nlogn),使得C能在线性时间内排序。

如果我们能找到这样的d,u的话,那么我们就能够在线性时间内找到中位数m.

假设我们已经找到了这样的d,u,那么我们只需要计算如下的步骤:

  1. S中计算出小于d的元素个数l_d
  2. C排序,由于|C|=o(nlogn),因此C的排序能够在线性时间内完成。
  3. 在排好序的C中,第n2ld+1个元素就是我们需要求的m

好了,那么我们如何才能快速地找到满足条件的d,u呢?事实上,d,u需要满足的条件并不是非常严格的,是一种比较"粗粒度"的约束条件,那我们就可以利用随机取样的方法来得到d,u,具体做法是这样的:

  1. S中随机取样得到一个子集R
  2. R排序,在R的中位数附近寻找这样的d,u
  3. 如果寻找的d,u满足上述的条件,那我们就能在线性时间内找到S的中位数,否则算法失败。

在这个过程中,有两个参数很重要,一是子集R的大小,既不能太小,从而导致不能找到合适的d,u;也不能太大,从而导致不能在线性时间内排序。二是d,u的选择范围,如果d,u靠得很近,很有可能m就不在C中了,如果d,u分得很开,那么会导致|C|很大,不能在线性时间内完成排序。

在这个算法中,我们选取R的大小为n34,而d,uR的中位数的n的范围4。整体的算法步骤如下所示:


input: 一个有n个元素的集合S

output: S的中位数m

  1. S中随机取样得到一个大小为n34的子集R
  2. R进行排序
  3. d为排好序的集合R中的第12n34n小的元素
  4. u为排好序的集合R中的第12n34+n小的元素
  5. 遍历S中的元素,计算出集合C={xS:dxu},以及ld=|{xS:x<d}|,lu=|xS:x>u|
  6. 如果ld>n2或者lu>n2,则算法失败。
  7. 如果|C|4n34,则将C排序;否则算法失败。
  8. 在排好序的C中,返回n2ld+1小的元素。

在上述的算法步骤中,第6步是用来保证d,u存在于C之中,而第7步是用来保证|C|足够小,能够在线性时间内完成排序。

现在我们需要来分析一下这个算法,首先我们需要定义三个事件:

  • ϵ1: Y1=|{rR|rm}|<12n34n
  • ϵ2: Y2=|{rR|rm}|<12n34n
  • ϵ3: |C|>4n34

很显然,事件ϵ1,ϵ2对应于步骤6中的两个判断条件,因为如果ld>n2,则R中的所有元素都在中位数m的右侧,即R中第12n34n小的元素一定大于m.同理lu>n2等价于事件ϵ2.而ϵ3等价于上述算法中的步骤7.

从整个算法的步骤中,我们可以看到,当前仅当ϵ1,ϵ2,ϵ3中的其中之一发生时,算法才会失败,否则一定会返回出一个正确的解。

现在我们就需要来计算一下ϵ1,ϵ2,ϵ3中至少有一个发生的概率是多少。

ϵ1ϵ2是类似的,因此我们首先来看一下ϵ1发生的概率是多少。

定义Xi为一个布尔值:

Xi={1im0im

Y1=n34i=1Xi,而Pr[Xi=1]可以进行如下的计算:

p=Pr[Xi=1]=1nn212

而此时的Y1是一个二项分布,因此

E[Y1]=n34p12n34Var[Y1]=n34p(1p)14n34

因此,我们可以应用Chebyshev不等式:

Pr[ϵ1]=Pr[Y1<12n34n]=Pr[Y112n34<n]Pr[|Y1E[Y1]|<n]Var[Y1]n=14n14

因此,ϵ1发生的概率不大于14n14.同理,ϵ2发生的概率也同样不会超过14n14.

现在我们来分析一下ϵ3的情况。

如果ϵ3发生的话,那么根据鸽巢原理,如下两个事件至少会发生一个:

  • ξ1: 在C中至少有2n34个元素大于m
  • ξ2: 在C中至少有2n34个元素小于m

我们只需要分析一种情况,另外一种情况利用对称性就能得到了。

我们来分析ξ1,如果ξ1成立,那么u在排好序的S中的位置至少为12n+2n34到这里位置应该还是比较好理解的,但是接下来的结论会有点绕,所以我先用一个图来说明一下目前S的划分情况:

mid

从图中可以看到,如果ξ1成立的话,我们就能得到如下的结论:集合R中至少有12n34n个元素是在S的前12n2n34大的元素集合中.从图上来看,就是uD一定是属于uB的,而12n34n12n2n34分别是uDuB的长度。5

在得出上述的结论之后,后面的计算就比较简单了:

定义Xi为一个布尔值:

Xi={1iuB0iuB

同时令X=n34i=1Xi为所有落入uD之间的元素的总数。

又因为

p=Pr[Xi=1]=12n2n34n=122n14

X是一个二项分布,因此:

E[X]=n34p=12n342nVar[X]=n34p(1p)=14n344n14<14n34

最后应用Chebyshev不等式,我们得到:

Pr[ξ1]=Pr[X12n34n]Pr[|XE[X]|n]Var[X]n14n14

因此,Pr[ϵ3]Pr[ξ1]+Pr[ξ2]12n14

综合上面对ϵ1,ϵ2,ϵ3的分析,我们最终得到如下的界:

Pr[ϵ1]+Pr[ϵ2]+Pr[ϵ3]n14

因此,说明算法失败的概率是比较小,能够以较大的概率在线性时间内找到正确的中位数。

参考资料


  1. Las Vegas算法是指运行时间不确定,但是运行结果一定正确的一类随机算法。而Monte Carlo算法是指运行时间确定,但是运行结果不一定正确的一类随机算法。这两个算法的概念我在随机算法学习笔记0-概率空间&计算模型中详细说明了。 

  2. 这里的集合S是乱序的。 

  3. 其实也存在能够在线性时间内解决中位数的确定性算法的,但是这个算法比较复杂,以前曾经实现过一次,但是现在已经基本不记得了。感兴趣的朋友可以查看这里 

  4. 这些数值是如何得出的,其实我也说不清,这些数值完全是凑出来的,是为了方便后续的计算而硬凑出来的。 

  5. 这个结论至关重要,是后面一系列计算的基础,但是我看过的资料上这部分结论都是直接得出的,没有相似的说明,这张图也是我自己研究了半天之后才画出的,应该对理解如何得出这个结论会有帮助,这部分确实需要好好想想才能想通。 

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Reading Time

~2 min read

Published

Category

randomized-algorithm

Tags

Contact