马尔科夫不等式(Markov's Inequity)
定理(Markov's Inequity):
假设X是一个取值为非负数的随机变量,则对于任何的t>0,满足如下不等式:
Pr[X≥t]=E[X]t
证明:
令Y为一个布尔变量:
则Y很明显满足:E[Y]=Pr[Y=1]=Pr[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):
- 运行2T(n)时长的A(x)算法。
- 如果A(x)返回一个结果,则将该结果直接返回;如果A(x)没能返回结果,就直接返回1.
可以看到,B(x)是一个运行时间确定,但是返回结果不确定的算法,也即是Monte Calo算法。并且,只有当A(x)没有返回结果时,才有可能返回错误解。这是False Postive的单边错误类型。我们可以来计算一下B(x)返回一个错误的解的概率,在这计算过程中,我们就需要用到马尔科夫不等式了。
方差(Variance)
定义: 一个随机变量X的方差定义为:
Var[X]=E[(X−E[X])2]=E[X2]−E[X]2
一个随机变量X的标准差定义为:
δ[X]=√Var[X]
需要注意的是,方差和期望不一样,是不满足线性可加性的。
定义: 两个随机变量的协方差定义为:
Cov(X,Y)=E[(X−E[X])(Y−E[Y])]
定理: 对于任意的随机变量X1,X2,⋯,Xn,有:
Var[n∑i=1Xi]=n∑i=1Var[Xi]+∑i≠jCov(Xi,Xj)
证明: 这只需要证明两个随机变量的情况。假设有两个随机变量X,Y,则
◻
定理: 对于任何两个独立的随机变量X和Y,有:
E[X⋅Y]=E[X]⋅E[Y]
证明: 假设X,Y是两个相互独立的随机变量,则我们可以做如下的推导:
◻
上述第二个等号之所以成立,是因为X,Y相互独立。
利用上述的定理,我们可以证明下面的定理:
对于任何两个独立的随机变量X,Y,它们的协方差为0:
Cov(X,Y) = 0
证明:
◻
利用上述的结论,我们可以直接得到下面结论:
定理: 对于两两独立的随机变量X1,X2,⋯,Xn来说,有:
Var[n∑i=1Xi]=n∑i=1Var[Xi]
伯努利分布的方差
对于满足伯努利分布的X来说,有:
则其方差可以直接计算:
二项式分布的方差
二项分布是n个独立的伯努利实验,因此,如果Y是满足二项分布的话,则Y=∑_i=1nX_i,利用独立性条件,Y的方差可以直接计算:
切比雪夫不等式(Chebyshev's Inequity)
在概率统计中,切比雪夫不等式(Chebyshev's Inequity)是一个非常重要的不等式,它给出了比Markov不等式更强的界。它表述如下:
对于任何的t>0,都满足:
Pr[|X−E[X]|≥t]≤Var[X]t2
证明:
首先,如下等式是肯定成立的:
我们可以将(X−E[X])2整体看成是一个随机变量,且这个随机变量是非负的,因此我们直接套用Markov不等式:
◻
问题举例
中位数选择(Median Selection)
中位数选择问题也是一个比较常见的问题,从一个集合S中选择第⌈n2⌉小的数.其实这个问题可以进行推广到从集合中选取第k小的数2,但是在这里我们暂时只讨论特殊情况:只寻找集合S中的中位数。这个寻找过程很直接地可以利用排序来完成,一旦将S排好序了,自然就能找到任意k小的元素了。但是,排序算法的最好代价是O(nlogn),而如果我们利用随机算法的方法的话,可以将时间代价降低为线性时间3。
这个随机化的算法被称为是LazySelect,其基本思想是:如果我们能够从集合S中寻找到满足如下条件的元素d和u:
- 中位数m存在于[d,u]中,也即m满足d≤m≤u
- 位于d和u之间的元素足够少,也即C=x∈S|d≤x≤u,|C|=o(nlogn),使得C能在线性时间内排序。
如果我们能找到这样的d,u的话,那么我们就能够在线性时间内找到中位数m.
假设我们已经找到了这样的d,u,那么我们只需要计算如下的步骤:
- 从S中计算出小于d的元素个数l_d
- 将C排序,由于|C|=o(nlogn),因此C的排序能够在线性时间内完成。
- 在排好序的C中,第⌊n2⌋−ld+1个元素就是我们需要求的m
好了,那么我们如何才能快速地找到满足条件的d,u呢?事实上,d,u需要满足的条件并不是非常严格的,是一种比较"粗粒度"的约束条件,那我们就可以利用随机取样的方法来得到d,u,具体做法是这样的:
- 从S中随机取样得到一个子集R
- 将R排序,在R的中位数附近寻找这样的d,u
- 如果寻找的d,u满足上述的条件,那我们就能在线性时间内找到S的中位数,否则算法失败。
在这个过程中,有两个参数很重要,一是子集R的大小,既不能太小,从而导致不能找到合适的d,u;也不能太大,从而导致不能在线性时间内排序。二是d,u的选择范围,如果d,u靠得很近,很有可能m就不在C中了,如果d,u分得很开,那么会导致|C|很大,不能在线性时间内完成排序。
在这个算法中,我们选取R的大小为n34,而d,u是R的中位数的√n的范围4。整体的算法步骤如下所示:
input: 一个有n个元素的集合S
output: S的中位数m
- 从S中随机取样得到一个大小为⌈n34⌉的子集R
- 将R进行排序
- 令d为排好序的集合R中的第⌊12n34−√n⌋小的元素
- 令u为排好序的集合R中的第⌈12n34+√n⌉小的元素
- 遍历S中的元素,计算出集合C={x∈S:d≤x≤u},以及ld=|{x∈S:x<d}|,lu=|x∈S:x>u|
- 如果ld>n2或者lu>n2,则算法失败。
- 如果|C|≤4n34,则将C排序;否则算法失败。
- 在排好序的C中,返回⌊n2⌋−ld+1小的元素。
在上述的算法步骤中,第6步是用来保证d,u存在于C之中,而第7步是用来保证|C|足够小,能够在线性时间内完成排序。
现在我们需要来分析一下这个算法,首先我们需要定义三个事件:
- ϵ1: Y1=|{r∈R|r≤m}|<12n34−√n
- ϵ2: Y2=|{r∈R|r≥m}|<12n34−√n
- ϵ3: |C|>4n34
很显然,事件ϵ1,ϵ2对应于步骤6中的两个判断条件,因为如果ld>n2,则R中的所有元素都在中位数m的右侧,即R中第12n34−√n小的元素一定大于m.同理lu>n2等价于事件ϵ2.而ϵ3等价于上述算法中的步骤7.
从整个算法的步骤中,我们可以看到,当前仅当ϵ1,ϵ2,ϵ3中的其中之一发生时,算法才会失败,否则一定会返回出一个正确的解。
现在我们就需要来计算一下ϵ1,ϵ2,ϵ3中至少有一个发生的概率是多少。
ϵ1和ϵ2是类似的,因此我们首先来看一下ϵ1发生的概率是多少。
定义Xi为一个布尔值:
则Y1=n34∑i=1Xi,而Pr[Xi=1]可以进行如下的计算:
而此时的Y1是一个二项分布,因此
因此,我们可以应用Chebyshev不等式:
因此,ϵ1发生的概率不大于14n−14.同理,ϵ2发生的概率也同样不会超过14n−14.
现在我们来分析一下ϵ3的情况。
如果ϵ3发生的话,那么根据鸽巢原理,如下两个事件至少会发生一个:
- ξ1: 在C中至少有2n34个元素大于m
- ξ2: 在C中至少有2n34个元素小于m
我们只需要分析一种情况,另外一种情况利用对称性就能得到了。
我们来分析ξ1,如果ξ1成立,那么u在排好序的S中的位置至少为12n+2n34到这里位置应该还是比较好理解的,但是接下来的结论会有点绕,所以我先用一个图来说明一下目前S的划分情况:
从图中可以看到,如果ξ1成立的话,我们就能得到如下的结论:集合R中至少有12n34−√n个元素是在S的前12n−2n34大的元素集合中.从图上来看,就是uD一定是属于uB的,而12n34−√n和12n−2n34分别是uD和uB的长度。5
在得出上述的结论之后,后面的计算就比较简单了:
定义Xi为一个布尔值:
同时令X=n34∑i=1Xi为所有落入uD之间的元素的总数。
又因为
且X是一个二项分布,因此:
最后应用Chebyshev不等式,我们得到:
因此,Pr[ϵ3]≤Pr[ξ1]+Pr[ξ2]≤12n−14
综合上面对ϵ1,ϵ2,ϵ3的分析,我们最终得到如下的界:
因此,说明算法失败的概率是比较小,能够以较大的概率在线性时间内找到正确的中位数。
参考资料
- wiki:Moment
- wiki: Markov's Inequity
- wiki: Chebyshev's Inequity
- wiki:Monte Calo algorithm
- wiki:Las Vegas algorithm
- Probability and Computing:Randomized Algorithms and Probabilistic Analysis
-
Las Vegas算法是指运行时间不确定,但是运行结果一定正确的一类随机算法。而Monte Carlo算法是指运行时间确定,但是运行结果不一定正确的一类随机算法。这两个算法的概念我在随机算法学习笔记0-概率空间&计算模型中详细说明了。 ↩
-
这里的集合S是乱序的。 ↩
-
其实也存在能够在线性时间内解决中位数的确定性算法的,但是这个算法比较复杂,以前曾经实现过一次,但是现在已经基本不记得了。感兴趣的朋友可以查看这里 ↩
-
这些数值是如何得出的,其实我也说不清,这些数值完全是凑出来的,是为了方便后续的计算而硬凑出来的。 ↩
-
这个结论至关重要,是后面一系列计算的基础,但是我看过的资料上这部分结论都是直接得出的,没有相似的说明,这张图也是我自己研究了半天之后才画出的,应该对理解如何得出这个结论会有帮助,这部分确实需要好好想想才能想通。 ↩