这学期选修了一门"随机算法"的课程，感觉其中的思想非常有趣和好玩，但是其中的分析过程也是比较复杂和不太好理解的。为了督促自己好好学习这一门课，打算开始记笔记，将自己理解的内容记录下来。
概率空间
由于在随机算法的分析过程中，大量使用了概率论中的知识，随机算法很大程度上就是在计算概率，所以首先要给出概率空间的定义，下面是概率空间形式化的定义.
概率空间是对一个随机过程的建模，可以用一个三元组(Ω,Σ,Pr)来表示，其中:
- Ω: 样本空间，表示随机过程中所有可能的输出结果(基本事件)。
- Σ: 事件集合，表示所有可能的事件的集合，一个事件由0个或多个基本事件组成。
- Pr: 概率测度，表示一个从Σ到实数域的函数,Pr:Σ↦R.每一个事件都被此函数赋予一个0和1之间的概率值。
一个概率空间有如下的五个约束条件:
- Ω∈Σ且∅∈Σ(分别表示确定事件和不可能事件都属于Σ)
- 如果A,B∈Σ，则A∩B,A∪B,A−B∈Σ,(事件的交、并、差运算之后仍然是事件).
- Pr(Ω)=1(所有基本事件的概率和为1)
- 如果A∩B=∅,则Pr(A∪B)=Pr(A)+Pr(B)
- 对于一个事件序列:A1⊃A2⊃⋯An⋯，如果∩nAn=∅，则limn→∞Pr(An)=0
几个结论
- 令ˉA=Ω−A.则Pr(ˉA)=1−Pr(A)
- 如果A⊆B，则Pr(A)≤Pr(B)
定义:
两个事件ξ1和ξ1独立当且仅当Pr(ξ1∧ξ2)=Pr(ξ1)⋅Pr(ξ2)
条件概率
在给定ξ2的情况下发生ξ1的概率是:Pr[ξ1|ξ2]=Pr[ξ1∧ξ2]Pr[ξ2]
全概率法则
令ξ1,ξ2,⋯,ξn是互不相交的事件，且∨ni=1ξn=Ω(完备事件组),那么，对于任意一个事件ξ,有Pr[ξ]=n∑i=1Pr[ξ|ξi]⋅Pr[ξi]
链式法则
令ξ1,ξ2,⋯,ξn是任意的n个事件，则Pr[∧ni=1]=n∏k=1Pr[ξk|∧i<kξi]
上述这些定义和结论，出了概率空间的定义比较新以外，其他内容都是概率统计中的基本内容，此处不再深入说明了。
随机算法举例
简单介绍完有关概率的内容之后，我们就要来看看神奇的随机算法的例子，下面是两个比较简单的随机算法的例子，刚看完这两个例子的时候，我就觉得随机算法真是神奇。
矩阵乘法(Checking Matrix Multiplication)
首先来看一下一个矩阵乘法的例子，对于三个n×n的矩阵A,B,C，我们想要验证AB是否等于C，这个问题可以表述成:
input: 3个n×n的矩阵A,B,C
output: 如果AB==C则返回Yes，否则返回No
面对这样的问题，最朴素的方法就是直接计算两个n×n的矩阵乘法，得到AB的具体结果,但是事实上，要计算两个n×n的矩阵时间代价是O(n3)，这样的代价是无法忍受的，所以有必要寻找更好的算法。
一种可行的随机化的算法如下所示:
Freivalds Algorithm
-
从{0,1}n中以等概率的分布随机选取一个向量v1
-
计算A(Bv)与Cv,如果A(Bv)==Cv，则返回
Yes，否则返回No
需要注意的是，在上面的计算过程中，首先需要计算Bv，然后再计算A(Bv)，这样做的好处是，将以本来需要计算n×n矩阵相乘问题变成n×1的矩阵乘向量的问题，计算代价明显下降了。
但是，很明显这个算法是不能保证每次都能得到正确的结果，我们可以来分析一下:
情况1: AB确实和C是相等的，则不管我随机得到的v是什么，A(Bv)与Cv也总是相等的，所以在这种情况下，Freivalds Algorithm确实能得到正确的解。
情况2: AB和C并不相等，则如果我们得到的v满足A(Bv)==Cv,那么该算法将会返回一个错误的解。反之，则可以返回一个正确的解。那么，我们不妨可以分析一下，该算法返回一个错误解的概率是多少。
该算法返回出一个错误的解，只有一种情况:原来的AB≠C，但是我们随机得到的一个v，使得A(Bv)==Cv.
令事件ϵ="AB≠C,而A(Bv)=Cv"
假设D=AB−C≠0，则A(Bv)=Cv可以表示为Dv=0，也就是说，D≠0∧Dv=0.
因为D≠0，所以，必存在一个Di:Di≠0(注意，这里的Di是一个1×n的向量。);而又因为Dv=0，所以必定有Di×v=0.
因为Di≠0，则在Di中至少有一个Dij≠0,将Di×v=0展开:
因为Dij≠0,所以vj可以被表示成
这说明当事件ϵ发生时，v中的1个元素是由其他n−1个元素决定的，也就是说，在这种情况下，v只有2n−1种可能性。
而v本身却有2n种可能性，所以我们可以说事件ϵ发生的可能性Pr[ϵ]≤2n−12n=12.
综上，也就说，Freivalds Algorithm返回错误解的可能性最多为12
然后这个结果似乎并不太好，一个返回正确解的概率在12左右的算法没有实用价值。
但是，如果我们把这个算法独立的运行k次呢？只有当k次运行的结果都是Yes时，才最终返回Yes;否则返回No
那么该算法返回错误解的可能性最多为12k,也即返回正确解的可能性至少为1−12k
当k取值比较大的时候，这是一个可以接受的结果，这也就说明了该算法可行性。
并且，在整个计算的过程中，全是n×1的矩阵乘向量的运算，计算代价要小很多。这个例子足以证明随机算法的神奇之处，只以一点点的不确定性，换来了很高的计算效率。
多项式判定问题(Polynomial Identity Testing,PIT)
现在再来看一个随机算法的例子，这个例子被称为是多项式判定问题(Polynomial Identity Testing,PIT),不过为了简单起见，我们这里暂时只考虑其单元的情况，多元的情况放在以后考虑。
首先这个问题可以表述成:
-
input: 定义在数域F上的度为d的两个单元多项式P1,P2.
-
output: 如果P1≡P2，则返回
Yes,否则返回No
解决这个问题的常规方法就是直接去查看P1,P2中的每一项的系数，看它们是否相等，只有当所有项的系数均相等时，P1≡P2。但是，如果P1,P2的度非常大，且给定的P1并不是标准形式的，比如:
要将上面的多项式展开成标准形式，这本身也是一个非常困难的任务。
面对这样的问题，现在就该轮到随机算法上场了。
首先，可以令Q=P1−P2，则原问题可以转化为判断Q≡0是否成立。
我们可以用如下的随机算法来进行判断
Algorithm for PIT
- 从F上随机的取出若干个值，形成集合S
- 从S中随机取出一个x，如果D(x)=0，则返回
Yes,否则返回No
同样的，这个算法也是不能保证得到正确解的，我们同样需要对它进行分析。
情况1: 如果原来的P1≡P2,则我们不管将x取何值，D总是等于0的，则该算法能够返回正确的解。
情况2: 如果原来的P1≢P2，则假如我们选取的x恰好是多项式D的其中一个根，那么该算法将会返回出错误解;否则可以返回出正确的解。
可以看到，这其实是和上一个例子中的算法是非常相似的，同样需要对算法进行分析，以确定其返回错误解的概率是多少，是否在一个可以"容忍"的范围内。
在这里，我们使用到了代数基本定理,根据代数基本定理，任何一个非零的一元n次复系数多项式,都正好有n个复数根,那也就是说在S中，最多只有d个D的根，那就是说我们从S中随机取出一个x恰好是D的根的概率是
这也就是说，该算法执行一次返回出错误解的概率最多是d|S|，那我们将其执行k次:只有当每一次都返回出Yes时，算法才最终返回Yes,否则只要出现一次No，算法就直接返回No.
此时算法发生错误的概率最多是(d|S|)k，当|S vert和k很大时，这是一个非常小的概率，在可以接受的范围内。
两种计算模型
如果仔细观察上面的这两个例子，我们其实可以发现，这两个算法是非常相似的,具有如下的特点:
- 总是能在执行完确定的步骤之后(k)之后，返回出结果，但是返回的结果的正确性却是不确定的2。
- 都是在一种情况下算法能够100%的返回出正确的解，而在另外一种情况下，至少以ϵ的概率返回出正确的解(在我们的两个例子中，ϵ恰好都是12)。
事实上，以上的特点可以用来区分不同的随机算法,随机算法一共分为两种不同的类型，分别称为蒙特卡洛算法(Monte Carlo algorithm)和拉斯维加斯算法(Las Vegas algorithm)
蒙特卡洛算法
蒙特卡洛算法是指能够在有限步内得出结果，但是却有可能以非常小的概率得出错误的结果的一类算法。根据上面我们为上面两个例子总结的特点1，这两类应该是属于蒙特卡洛算法
而将蒙特卡洛算法应用在判定问题上时，它又可以分成两种不同的类别，分别是单边错误(one-sided errors)和双边错误(two-sided erros)3
单边错误
单边错误是指，算法只在一个方向上可能出错，这又可以分为两种情况:
-
False postive: 如果真实答案是
Yes，则算法以概率1返回Yes;如果真实答案是No，则算法至少以ϵ的概率返回No. -
False negative: 如果真实答案是
Yes，则算法至少以ϵ的概率返回Yes;如果真实答案是No，则算法以概率1返回No.
对于单边错误来说，算法给出错误答案的概率是1−ϵ，而这可以通过重复执行算法来使得错误率进一步降低为(1−ϵ)k
双边错误
双边错误是指，算法在两个方向都有可能出错。
也就说，当真实答案是Yes的时候，算法至少以12+ϵ的概率返回Yes;当真实答案是No的时候，算法至少以12+ϵ的概率返回No
同样的，在这种情况，可以通过重复执行算法来使得错误率进一步下降。
拉斯维加斯算法
拉斯维加斯算法是指总是能够得到正确的解，但是算法执行时间却是不确定的一类算法。
总结
可以看到，前面举的两个例子都是非常简单的，但是证明其正确性的过程却并不简单，随机算法中的很大一部分内容就是在论证算法的正确性，分析是非常重要的一步。