马尔科夫不等式(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算法¹:

假设算法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)返回一个错误的解的概率，在这计算过程中，我们就需要用到马尔科夫不等式了。

方差(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小的数²,但是在这里我们暂时只讨论特殊情况:只寻找集合S中的中位数。这个寻找过程很直接地可以利用排序来完成，一旦将S排好序了，自然就能找到任意k小的元素了。但是，排序算法的最好代价是O(nlogn)，而如果我们利用随机算法的方法的话，可以将时间代价降低为线性时间³。

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

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

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

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

1. 从S中计算出小于d的元素个数l_d
2. 将C排序，由于|C|=o(nlogn),因此C的排序能够在线性时间内完成。
3. 在排好序的C中，第⌊n2⌋−ld+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,u是R的中位数的√n的范围⁴。整体的算法步骤如下所示:

---

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

output: S的中位数m

1. 从S中随机取样得到一个大小为⌈n34⌉的子集R
2. 将R进行排序
3. 令d为排好序的集合R中的第⌊12n34−√n⌋小的元素
4. 令u为排好序的集合R中的第⌈12n34+√n⌉小的元素
5. 遍历S中的元素，计算出集合C={x∈S:d≤x≤u}，以及ld=|{x∈S:x<d}|,lu=|x∈S:x>u|
6. 如果ld>n2或者lu>n2，则算法失败。
7. 如果|C|≤4n34,则将C排序;否则算法失败。
8. 在排好序的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的长度。⁵

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

定义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

Share on: Twitter ❄ Facebook ❄ Email

---

---