The Bounded Difference Method
在上一篇的笔记，我们分别讲到了Martingales中的Doob sequence和Azuma's inequality,如果把这两个工具放到一起，会发生什么呢？如果把这两个工具组合起来，我们就能够得到一个称为"the method of averaged bounded differences"的定理.
Theorem:Method of averaged bounded differences
令X=(X1,⋯,Xn)表示任意的随机变量序列，令f表示关于X1,⋯,Xn的函数，并且对于所有的1≤i≤n满足:
$ \big\vert E[f(\mathbf{X})\vert X_1,\cdots,X_i] - E[f(\mathbf{X})\vert X_1,\cdots,X_{i-1}]\big\vert \le c_i $
则
Pr[|f(X)−E[f(X)]|≥t]≤2exp(−t22n∑i=1c2i)
证明:
证明过程非常简单，需要定义Yi=E[f(X)|X1,⋯,Xi]为一个Doob Martingale，然后直接套用Azuma's inequality就行了。
◻
但是，在实际情况中，上述定理的条件是很难验证的，这就大大影响了该定理的使用。因此，这里我们将会介绍另外一个比较好验证的条件，称为Lipschitz condition.其描述如下:
Lipschitz condition
一个函数f(x1,⋯,xn)对于任意的x1,⋯,xn和yi满足:
|f(x1,⋯,xi−1,xi,xi+1,⋯,xn)−f(x1,⋯,xi−1,yi,xi+1,⋯,xn)|≤ci则称其满足Lipschitz condition.
当随机变量序列满足Lipschitz condition时，有如下的定理(注意:该定理的条件中，随机变量必须是独立的!)
Theorem(Method of bounded differnces)
令X=(X1,⋯,Xn)表示n个独立的随机变量，令f表示一个满足Lipschitz condition的函数，则:
Pr[|f(X)−E[f(X)]|≥t]≤2exp(−t22n∑i=1c2i)
Method of bounded differnces可以理解成这样的组合:
独立性条件 + Lipschitz condition ⇒f(X1,X2,⋯,Xn)集中在它的期望附近。
它最大一个优势就是不需要知道具体的f函数是什么形式的，就能得出其概率集中的结论。
Applications
小球问题
假设我们现在有m个小球要以独立且均匀的分布投入到n个箱子中，我们需要考察小球投掷完成之后，还剩多少个空箱子？根据我们之前期望的线性可加性，我们能比较简单的计算其期望值:
令Xi表示第i个箱子是否为空，Xi=1表示箱子i为空;否则为Xi=0.则X=n∑i=1表示一共有多少空个箱子,则:
虽然我们求出了空箱子数目的期望，但是这还不够，我们希望能够得到更加精确的信息来描述随机变量X.此时，我们就可以使用method of bounded differnces.
method of bounded differnces有两个条件:1. 独立 2. Lipschitz condition
而此时的Xi显然是不独立的，因此我们需要重新假设我们的随机变量。令Yj表示第j个球落入到箱子的编号，则X可以看成是(Y1,⋯,Ym)的函数，即:
此时的Yi是独立的。
而一个球的投掷，最多只能让一个箱子变得非空，每一次只改变一个变量，引起的变化最多为1，即满足Lipschitz condition.因此，我们直接使用method of bounded differnces:
因此，对于小球投掷问题来说，空箱子的数目主要集中在n(1−1n)m附近。
模式匹配问题
令X=(X1,X2,⋯,Xn)均匀且独立地从字符表Σ中选取的字符序列，其中|Σ|=m。令π∈Σk是任意一个固定长度的字符串。我们想要考察π在X中出现的次数。
令Y表示π一共在X中出现的次数, Zi=1表示Xi是π的起始位置，否则Xi=0.其中，0≤i≤n−k+1.则:
且Y=n−k+1∑i=0，所以E[Y]=(n−k+1)⋅(1m)k.
同样的，我们还需要知道Y是否有概率集中现象。我们可以将Y看成是(X1,X2,⋯,Xn)的函数，且(X1,X2,⋯,Xn)是独立的.
而又因为，π的长度是k，因此(X1,X2,⋯,Xn)其中一个字符改变时，带来Y的变化最多为k，因此满足Lipschitz condition.所以，直接使用method of bounded differnces: