Continoal Expectation

条件期望是指，在给定条件的情况下，随机变量的期望值.条件期望可以表示成:

我们可以将条件期望看成是关于X的随即变量f(X)

假设X,Y,Z是三个任意的随机变量，f,g是任意的函数，则对于条件期望有如下的结论:

1. E[X]=E[E[X|Y]].
2. E[X|Z]=E[E[X|Y,Z]|Z]
3. E[E[f(X)g(X,Y)|X]]=E[f(X)⋅E[g(X,Y)|X]](条件于X,因此可以将f(X)看成是一个常数，根据期望的线性可加性，就能够把f(X)提出来了)

Martingales

Martingales描述的是一系列的随机变量，该序列的当前的随机变量依赖之前所有的历史随机变量¹，如果当前的随机变量的期望不发生变化，则这整个随机过程就被称为是Martingales.

定义: Martingale

一个随机变量序列X0,⋯,Xi−1是一个Martingale当且仅当对于所有的i>0，都有:

E[Xi|X0,⋯,Xi−1]=Xi−1

举例

假设我们投掷一个均匀的硬币，令Zj∈{−1,1}表示第j次投掷的结果，令X0=0和Xi=∑j≤iZj，则随机变量X0,X1,⋯定义了一个Martingale.

证明:

Generalizations

Martingale还有更加一般化的定义，它不再只是一个只关于自己的随机序列，而是关于另外一个随机序列。

定义 Generalized Martingale

一个随机变量序列Z0,Z1,⋯是一个关于X0,X1,⋯的Martingale，当且仅当对于任意的i>0，满足下述三个条件:

1. Zi是X0,X1,⋯,Xi的函数
2. E[|Zi|]=∞
3. E[Zi+1|X0,X1,⋯,Xi]=Zi

因此，如果一个随机变量序列X0,X1,⋯是关于自己的Martingale，那么它自身就是一个Martingale.

Azuma's Inequality

关于Martingale有一个比较重要的不等式，称为Azuma's inequality,描述如下:

Azuma's inequality

假设X0,X1,⋯是一个Martingale，且对于所有的k>1，都有:

|Xk−Xk−1|≤ck

则

Pr[|Xn−X0|≥t]≤2exp(−t22n∑k=1c2k).

需要注意的是，在这个不等式中，是没有独立性要求的。

其中|Xk−Xk−1|≤ck的条件是整个不等式的核心，称为bounded difference condition.

该不等式描述的是，如果将X0,X1,⋯看成是随时间变换的状态的话，那么如果每一步的状态转换都没有出现大的跳跃，那么该不等式就保证整个过程一直处于其初始点附近。

其中有一种特殊情况，当ck=c的时候，不等式可以写成:

假设X0,X1,⋯是一个Martingale，且对于所有的k>1，都有:

|Xk−Xk−1|≤c

则

Pr[|Xn−X0|≥ct√n]≤2e−t22

还有一般化的Azuma's Inequality:

Azuma's inequality(general version)

假设Y0,Y1,⋯是关于X0,X1,⋯的一个Martingale，且对于所有的k>1，都有:

|Yk−Yk−1|≤ck

则

Pr[|Yn−Y0|≥t]≤2exp(−t22n∑k=1c2k).

证明

Azuma's Inequality的证明过程和笔记5中证明Chernoff Bound的方法类似，先在Moment Generating Function 上使用Markov不等式,然后确定这个Moment Generating Function的上界，最终选取合适的参数。

在正式开始证明之前，我们先要证明一个引理:

引理

令X为一个随机变量满足E[X]=0且|X|≤c,则对于任何的λ>0,有:

E[eλX]≤eλ2c22

证明:

通过观察，我们可以看到函数eλX在定义域[c,c]上是一个凸函数，所以如果我们在点(−c,e−λc)和(c,eλc)画一条直线，则eλX的曲线必然在直线的下方。也即:

因为E[X]=0，因此:

上式中的最后一个不等式是根据泰勒展开式得到的。

◻

现在开始正式证明Azuma's Inequality²:

偏移之和

令Yi=Xi−Xi−1,则:

令Zn=n∑i=1Yi,则

现在我们就需要找出Zn的上界。

应用Markov不等式

接下去就要寻找E[eλZn]的上界。

又因为

且

，所以直接套用之前证明的引理:

将其代回到E[eλZn]中:

将其递归展开:

代回到Markov不等式中:

选取合适的λ

令λ=tn∑k=1c2k,则

所以:

◻

The Doob martingales

在Martingale中，有一类的Martingale比较重要，称为Doob Martingale.

首先，我们先定义Doob Sequence,其定义如下:

定义: Doob Sequence

函数f关于随机变量X1,X2,⋯的Doob Sequence定义如下:

Yi=E[f(X1,⋯,Xn)|X1,⋯,Xi],0≤i≤n

特别地，Y0=E[f(X1,⋯,Xn)]且Yn=f(X1,⋯,Xn)

一个函数的Doob Sequence定义了一个Martingale,也就是说:

证明:

◻

Doob Martingale是一个估计函数值的随机过程，对于关于随机变量X1,⋯,Xn的函数f(X1,⋯,Xn)，Y0,Y1,⋯,Yn表示对函数值的一个估计，Yi表示，当已知X1,⋯,Xi时，函数值f(X1,⋯,Xn)的期望, 即Yi=E[f(X1,⋯,Xn)|X1,⋯,Xi].因此，Y0表示在X1,⋯,Xn全都未知的情况下，f(X1,⋯,Xn)的期望,即Y0=E[f(X1,⋯,Xn)];而Yn表示在X1,⋯,Xn全部已知的情况下，f(X1,⋯,Xn)的期望，也就是其在自身的函数值，也即Yn=f(X1,⋯,Xn).

举例

Edge Exposure Martingale

令G表示一个有n个点的随机图，f为一个这个随机图的一个函数，这个函数可以是随机图的任意的性质，比如染色数、包含三角的数目等等。令e1,e2,⋯,em,m=(n2)表示图中所有可能出现的边，令:

定义Yi=E[f(G)|X1,X2,⋯,Xi]，则Y0,Y1,⋯,Yn形成了一个Doob Martingale，通常称为edge exposure martingale.

Vertex Exposure Martingale

在edge exposure martingale中我们是不断暴露出边，其实我们也可以不断暴露点，假设随机图的点集为[n]，则令Xi表示由点集[i]组成的子图.令Yi=E[f(G)|X1,⋯,Xi].则Y0,Y1,⋯,Yn也定义了一个Doob Martingale,通常称为vertex exposure martingale.

Chromatic number

定理

令G∼G(n,p)，且χ(G)表示图G的染色数，则

Pr[|χ(G)−E[χ(G)]|≥t√n]≤2e−t22

证明:

考虑图G的vertex exposure martingale,Yi=E[χ(G)|X1,⋯,Xi].

可以想像，每当我们暴露出一个点的时候，我们总可以用一种新的颜色去染色，也就是说它满足bounded difference condition：

因此，我们对Y0,⋯,Yn直接套用Azuma's Inequality，就得到了上述的结论。

◻

Hoeffding's Inequality

Hoeffding's Inequality

令X=n∑i=1Xi,其中X1,⋯,Xn是独立的随机变量，且ai≤Xi≤bi,对于所有的1≤i≤n，令μ=E[X]，则:

{% math %}Pr[\vert X-\mu \vert\ge t]\le 2exp\bigg( -\frac{2}{2\sum\limits_{i=1}^n(b_i-a_i)^2} \bigg){% endmath %}

证明:

定义Doob Sequence:Yi=E[n∑j=1Xj|X1,⋯,Xi]，很明显我们有Y0=μ且Yn=X.

同时，|Yi−Yi−1|≤bi−ai，所以，使用一般化的Azuma's Inequality，就能得到上述结论。

◻

Stoppinng Times

在Martingale中，还有另外一种问题，称为Stoppinng Times，比如在赌博的时候，令Zi表示玩家在第i局之后的赢钱数，很显然Z1,Z2,⋯形成了一个Martingale，如果玩家决定在第k³局之后就退出赌局，那么这个玩家期望的赢钱数是多少？

首先介绍一个引理:

引理

假设Z0,Z1,⋯,Zn是关于X0,X1,⋯,Xn的一个Martingale,则

E[Zn]=E[Z0]

证明:

根据Martingale的定义，我们有:

两边同时取期望，得到:

不断重复上述过程，就能够得到:

◻

有了上述的引理，我们就能说，如果在赌局开始之前就确定玩的轮数的话，那么期望的盈利就是0.

当然，一般在真实的场景中，情况要复杂得多，比如停止轮数是由当前的盈利状况来决定的。为了分析这种情况，我们需要引入Stoppinng Time的定义:

Stoppinng Time

令{Zn,n≥0}为一个随机变量序列，T为一个非负的整数随机变量，如果事件T=n只依赖于Z0,Z1,⋯,Zn，则T就是{Zn,n≥0}的一个Stoppinng Time.

结合上面关于Martingale的引理，如果赌局是公平的话，那么E[XT]=E[X0]=0一直成立。但是，如果Stoppinng Time T定义成第一次Zi>B,其中B是一个固定的常量，则此时期望的盈利应该是大于0的，然而此时的Stoppinng Time未必是有限的。

Martingale Stoppinng Theorem

如果Z0,Z1,⋯是关于X0,X1,⋯的Martingale，且T是X1,X2,⋯的一个Stoppinng Time，则:

当如下三个条件中的任意一个满足时:

1. Zi是有界的，即存在一个常数c，使得对任意的i，都有|Zi|≤c

2. T是有界的

3. E[T]<∞且存在一个常数c使得E[|Zi+1−Zi||X1,⋯,Xi]<c

等式

E[ZT]=E[Z0]

成立

举例

考虑一个独立且公平的赌局，在每一轮的赌局中，玩家分别以12的概率赢得1元或输掉1元.令Xi表示第i轮所赢的数目,Zi表示第i轮之后一共赢得的数目，其中Z0=0,假设玩家第一次输掉l1元或赢得l2元时退出赌局，那么请问玩家在输掉l1元之前赢得l2元的概率是多少?⁴

分析:

令T表示玩家第一次输掉l1元或赢得l2元时的轮数，则T是X1,X2,⋯的一个Stoppinng Time.而Z0,Z1,⋯则是个Martingale.因为Zi是有界的，因此满足Martingale Stoppinng Theorem的条件，因此我们有:

令q表示赢得l2元的概率，则:

我们可以得到:

Wald's Equation

我们可以看到，在上述的Martingale Stoppinng Theorem中并没有要求随机变量必须是独立的，这体现出了Martingale的强大力量，但是如果随机变量是独立的，会发生什么呢？对于独立的随机变量的序列，我们有如下的定理:

Theorem: Wald's Equation

令X1,X2,⋯是非负，独立同分布的随机变量序列，且这些随机变量都服从分布X.令T表示这个序列的一个Stoppinng Time。如果T和X的期望都是有界的，则:

E[T∑i=1X]=E[T]E[X]

证明:

对于i≥1,令Zi=i∑j=1(Xj−E[X]),则

所以，Z1,Z2,⋯形成了一个关于X1,X2,⋯的Martingale.又因为E[T]<∞且:

因此，我们可以使用Martingale Stoppinng Theorem:

因为，我们可以做如下计算:

即得到:

关于独立随机变量序列，还有另外一种Stoppinng Time的定义：

定义:

令Z0,Z1,⋯,Zn是一个独立的随机变量序列，T是一个非负的，整数随机变量，如果事件T=n独立于

Zn+1,Zn+2,⋯

,则T是当前序列的一个Stoppinng Time

举例

假设一个玩家参加一个赌局，他首先抛掷一个标准的骰子，得到的点数为X，则第二次他同时抛掷X个标准的骰子，假设这X个骰子所有点数之和为Z,问Z的期望是多少?

分析:

对于1≤i≤X，令Yi表示第i个骰子得到的点数，则E[Z]=E[X∑i=1Yi]，根据上述的定义，X是一个Stoppinng Time,因此根据Wald's Equation,我们得到:

总结

本片文章主要介绍了有关Martingale的有关内容，首先从条件期望开始，引出了Martingales的定义，Martingales是一个比较有用工具，主要用来分析一个随机变量的序列.Martingales的一个优势就是，它不要求独立性，这就比较强大了。

Martingales的定义之后，我们介绍Azuma's inequality,这里比较重要的是bounded difference condition,它保证了Martingales的序列不会离开初始状态太"远".

接着说明了一类特殊的Martingales——Doob Martingale,它描述了当序列中的随机变量逐渐被确定时，其函数值期望的变化过程。

最后介绍了Martingales中的Stoppinng Time相关的内容，描述了序列停止时的性质。

参考资料

• Condtional Expecation
• Martingales
• Azuma's inequality
• Chernoff Bound
• MarkovInequity
• Moment Generating Function
• Taylor Series
• Doob Martingale
• 《Probability and Computing:Randomized Algorithms and Probabilistic Analysis》

Share on: Twitter ❄ Facebook ❄ Email

---

---