这学期选修了一门"随机算法"的课程，感觉其中的思想非常有趣和好玩，但是其中的分析过程也是比较复杂和不太好理解的。为了督促自己好好学习这一门课，打算开始记笔记，将自己理解的内容记录下来。

概率空间

由于在随机算法的分析过程中，大量使用了概率论中的知识，随机算法很大程度上就是在计算概率，所以首先要给出概率空间的定义，下面是概率空间形式化的定义.

概率空间是对一个随机过程的建模，可以用一个三元组$(\Omega,\Sigma,Pr)$来表示，其中:

$\Omega$: 样本空间，表示随机过程中所有可能的输出结果(基本事件)。
$\Sigma$: 事件集合，表示所有可能的事件的集合，一个事件由0个或多个基本事件组成。
Pr: 概率测度，表示一个从$\Sigma$到实数域的函数,$Pr: \Sigma \mapsto R$.每一个事件都被此函数赋予一个0和1之间的概率值。

一个概率空间有如下的五个约束条件:

$\Omega\in\Sigma$且$\emptyset\in\Sigma$(分别表示确定事件和不可能事件都属于$\Sigma$)
如果$A,B\in \Sigma$，则$A\cap B,A\cup B,A-B\in\Sigma$,(事件的交、并、差运算之后仍然是事件).
$Pr(\Omega) = 1$(所有基本事件的概率和为1)
如果$A\cap B = \emptyset$,则$Pr(A\cup B)=Pr(A) + Pr(B)$
对于一个事件序列:$A_1\supset A_2\supset\cdots A_n\cdots$，如果$\cap_n A_n = \emptyset$，则$\lim\limits_{n\rightarrow \infty}Pr(A_n) = 0$

几个结论

令$\bar{A} = \Omega - A$.则$Pr(\bar{A}) = 1 - Pr(A)$
如果$A \subseteq B$，则$Pr(A) \leq Pr(B)$

定义:

两个事件$\xi_1$和$\xi_1$独立当且仅当$Pr(\xi_1\land \xi_2) =Pr(\xi_1)\cdot Pr(\xi_2)$

条件概率

在给定$\xi_2$的情况下发生$\xi_1$的概率是:$Pr[\xi_1\vert\xi_2] = \frac{Pr[\xi_1\wedge\xi_2]}{Pr[\xi_2]}$

全概率法则

令$\xi_1,\xi_2,\cdots,\xi_n$是互不相交的事件，且$\mathop{\vee}_{i=1}^n\xi_n = \Omega$(完备事件组),那么，对于任意一个事件$\xi$,有$Pr[\xi]=\sum\limits_{i=1}^nPr[\xi\vert\xi_i]\cdot Pr[\xi_i]$

链式法则

令$\xi_1,\xi_2,\cdots,\xi_n$是任意的n个事件，则$Pr[\mathop{\wedge}_{i=1}^n] = \prod\limits_{k=1}^nPr[\xi_k\vert \mathop{\wedge}_{i<k}\xi_i]$

上述这些定义和结论，出了概率空间的定义比较新以外，其他内容都是概率统计中的基本内容，此处不再深入说明了。

随机算法举例

简单介绍完有关概率的内容之后，我们就要来看看神奇的随机算法的例子，下面是两个比较简单的随机算法的例子，刚看完这两个例子的时候，我就觉得随机算法真是神奇。

矩阵乘法(Checking Matrix Multiplication)

首先来看一下一个矩阵乘法的例子，对于三个$n\times n$的矩阵$A,B,C$，我们想要验证$AB$是否等于$C$，这个问题可以表述成:

input: 3个$n\times n$的矩阵$A,B,C$

output: 如果$AB==C$则返回Yes，否则返回No

面对这样的问题，最朴素的方法就是直接计算两个$n\times n$的矩阵乘法，得到$AB$的具体结果,但是事实上，要计算两个$n\times n$的矩阵时间代价是$O(n^3)$，这样的代价是无法忍受的，所以有必要寻找更好的算法。

一种可行的随机化的算法如下所示:

Freivalds Algorithm

从$\{0,1\}^n$中以等概率的分布随机选取一个向量$v$¹
计算$A(Bv)$与$Cv$,如果$A(Bv)==Cv$，则返回Yes，否则返回No

需要注意的是，在上面的计算过程中，首先需要计算$Bv$，然后再计算$A(Bv)$，这样做的好处是，将以本来需要计算$n\times n$矩阵相乘问题变成$n\times 1$的矩阵乘向量的问题，计算代价明显下降了。

但是，很明显这个算法是不能保证每次都能得到正确的结果，我们可以来分析一下:

情况1: $AB$确实和$C$是相等的，则不管我随机得到的$v$是什么，$A(Bv)$与$Cv$也总是相等的，所以在这种情况下，Freivalds Algorithm确实能得到正确的解。

情况2: $AB$和$C$并不相等，则如果我们得到的$v$满足$A(Bv)==Cv$,那么该算法将会返回一个错误的解。反之，则可以返回一个正确的解。那么，我们不妨可以分析一下，该算法返回一个错误解的概率是多少。

该算法返回出一个错误的解，只有一种情况:原来的$AB\neq C$，但是我们随机得到的一个$v$，使得$A(Bv)==Cv$.

令事件$\epsilon=$"$AB\neq C$,而$A(Bv)=Cv$"

假设$D=AB-C\neq 0$，则$A(Bv)=Cv$可以表示为$Dv=0$，也就是说，$D\neq 0\wedge Dv=0$.

因为$D\neq 0$，所以，必存在一个$D_i:D_i\neq 0$(注意，这里的$D_i$是一个$1\times n$的向量。);而又因为$Dv=0$，所以必定有$D_i\times v=0$.

因为$D_i\neq 0$，则在$D_i$中至少有一个$D_{ij}\neq 0$,将$D_i\times v =0$展开:

$$ \begin{equation} D_i\times v = D_{i1}\times v_1 + D_{i2}\times v_2 + \dots + D_{ij}\times v_j + \dots + D_{in}\times v_n = 0 \end{equation} $$

因为$D_{ij}\neq 0$,所以$v_j$可以被表示成

$$ \begin{equation} v_j = \frac{\sum\limits_{k=1\wedge k\neq j}^n D_{ik}v_k}{D_{ij}} \end{equation} $$

这说明当事件$\epsilon$发生时，$v$中的$1$个元素是由其他$n-1$个元素决定的，也就是说，在这种情况下，$v$只有$2^{n-1}$种可能性。

而$v$本身却有$2^n$种可能性，所以我们可以说事件$\epsilon$发生的可能性$Pr[\epsilon]\leq\frac{2^{n-1}}{2^n}=\frac{1}{2}$.

综上，也就说，Freivalds Algorithm返回错误解的可能性最多为$\frac{1}{2}$

然后这个结果似乎并不太好，一个返回正确解的概率在$\frac{1}{2}$左右的算法没有实用价值。

但是，如果我们把这个算法独立的运行k次呢？只有当$k$次运行的结果都是Yes时，才最终返回Yes;否则返回No

那么该算法返回错误解的可能性最多为$\frac{1}{2^k}$,也即返回正确解的可能性至少为$1-\frac{1}{2^k}$

当$k$取值比较大的时候，这是一个可以接受的结果，这也就说明了该算法可行性。

并且，在整个计算的过程中，全是$n\times 1$的矩阵乘向量的运算，计算代价要小很多。这个例子足以证明随机算法的神奇之处，只以一点点的不确定性，换来了很高的计算效率。

多项式判定问题(Polynomial Identity Testing,PIT)

现在再来看一个随机算法的例子，这个例子被称为是多项式判定问题(Polynomial Identity Testing,PIT),不过为了简单起见，我们这里暂时只考虑其单元的情况，多元的情况放在以后考虑。

首先这个问题可以表述成:

input: 定义在数域$F$上的度为$d$的两个单元多项式$P_1,P_2$.
output: 如果$P_1\equiv P_2$，则返回Yes,否则返回No

解决这个问题的常规方法就是直接去查看$P_1,P_2$中的每一项的系数，看它们是否相等，只有当所有项的系数均相等时，$P_1\equiv P_2$。但是，如果$P_1,P_2$的度非常大，且给定的$P_1$并不是标准形式的，比如:

$$ \begin{equation} P_1 = (x+1)(x-2)(x+3)(x-4)(x+5)\mathop{\equiv}^{?} x^6-7^3+25 = P_2 \end{equation} $$

要将上面的多项式展开成标准形式，这本身也是一个非常困难的任务。

面对这样的问题，现在就该轮到随机算法上场了。

首先，可以令$Q = P_1 - P_2$，则原问题可以转化为判断$Q\equiv 0$是否成立。

我们可以用如下的随机算法来进行判断

Algorithm for PIT

从$F$上随机的取出若干个值，形成集合$S$
从$S$中随机取出一个$x$，如果$D(x)=0$，则返回Yes,否则返回No

同样的，这个算法也是不能保证得到正确解的，我们同样需要对它进行分析。

情况1: 如果原来的$P_1\equiv P_2$,则我们不管将$x$取何值，$D$总是等于0的，则该算法能够返回正确的解。

情况2: 如果原来的$P_1\not\equiv P_2$，则假如我们选取的$x$恰好是多项式$D$的其中一个根，那么该算法将会返回出错误解;否则可以返回出正确的解。

可以看到，这其实是和上一个例子中的算法是非常相似的，同样需要对算法进行分析，以确定其返回错误解的概率是多少，是否在一个可以"容忍"的范围内。

在这里，我们使用到了代数基本定理,根据代数基本定理，任何一个非零的一元n次复系数多项式,都正好有n个复数根,那也就是说在$S$中，最多只有$d$个$D$的根，那就是说我们从$S$中随机取出一个$x$恰好是$D$的根的概率是

$$ \begin{equation} Pr \leq \frac{d}{\vert S\vert} \end{equation} $$

这也就是说，该算法执行一次返回出错误解的概率最多是$\frac{d}{\vert S\vert}$，那我们将其执行$k$次:只有当每一次都返回出Yes时，算法才最终返回Yes,否则只要出现一次No，算法就直接返回No.

此时算法发生错误的概率最多是$(\frac{d}{\vert S \vert})^k$，当$\vert S\ vert$和$k$很大时，这是一个非常小的概率，在可以接受的范围内。

两种计算模型

如果仔细观察上面的这两个例子，我们其实可以发现，这两个算法是非常相似的,具有如下的特点:

总是能在执行完确定的步骤之后($k$)之后，返回出结果，但是返回的结果的正确性却是不确定的²。
都是在一种情况下算法能够$100\%$的返回出正确的解，而在另外一种情况下，至少以$\epsilon$的概率返回出正确的解(在我们的两个例子中，$\epsilon$恰好都是$\frac{1}{2}$)。

事实上，以上的特点可以用来区分不同的随机算法,随机算法一共分为两种不同的类型，分别称为蒙特卡洛算法(Monte Carlo algorithm)和拉斯维加斯算法(Las Vegas algorithm)

蒙特卡洛算法

蒙特卡洛算法是指能够在有限步内得出结果，但是却有可能以非常小的概率得出错误的结果的一类算法。根据上面我们为上面两个例子总结的特点1，这两类应该是属于蒙特卡洛算法

而将蒙特卡洛算法应用在判定问题上时，它又可以分成两种不同的类别，分别是单边错误(one-sided errors)和双边错误(two-sided erros)³

单边错误

单边错误是指，算法只在一个方向上可能出错，这又可以分为两种情况:

False postive: 如果真实答案是Yes，则算法以概率1返回Yes;如果真实答案是No，则算法至少以$\epsilon$的概率返回No.
False negative: 如果真实答案是Yes，则算法至少以$\epsilon$的概率返回Yes;如果真实答案是No，则算法以概率1返回No.

对于单边错误来说，算法给出错误答案的概率是$1-\epsilon$，而这可以通过重复执行算法来使得错误率进一步降低为$(1-\epsilon)^k$

双边错误

双边错误是指，算法在两个方向都有可能出错。

也就说，当真实答案是Yes的时候，算法至少以$\frac{1}{2} + \epsilon$的概率返回Yes;当真实答案是No的时候，算法至少以$\frac{1}{2} + \epsilon$的概率返回No

同样的，在这种情况，可以通过重复执行算法来使得错误率进一步下降。

拉斯维加斯算法

拉斯维加斯算法是指总是能够得到正确的解，但是算法执行时间却是不确定的一类算法。

总结

可以看到，前面举的两个例子都是非常简单的，但是证明其正确性的过程却并不简单，随机算法中的很大一部分内容就是在论证算法的正确性，分析是非常重要的一步。

参考资料

这里的等概率是指，每次等概率地从$\{0,1\}$中取出一个元素($0$或$1$)，然后重复$n$次，形成一个$n\times 1$的$n$维向量$v$。 ↩
在上面的例子中，我们有$1-\frac{1}{2^k}$的概率能够得出正确的解，虽然这是一个很接近于1的概率，但是毕竟不能说成$100\%$ ↩
这里的单边和双边是我自己翻译的，我没有找到比较正统的翻译，于是只能自己来了。 ↩

Flyaway is the owner of this blog.

So what do you think? Did I miss something? Is any part unclear? Leave your comments below

Comments

随机算法学习笔记0-概率空间and计算模型