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

概率空间

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

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

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

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

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

几个结论

  1. \(\bar{A} = \Omega - A\).则\(Pr(\bar{A}) = 1 - Pr(A)\)
  2. 如果\(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

  1. \(\{0,1\}^n\)中以等概率的分布随机选取一个向量\(v\)1

  2. 计算\(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

  1. \(F\)上随机的取出若干个值,形成集合\(S\)
  2. \(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\)很大时,这是一个非常小的概率,在可以接受的范围内。

两种计算模型

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

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

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

蒙特卡洛算法

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

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

单边错误

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

  • 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

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

拉斯维加斯算法

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

总结

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

参考资料


  1. 这里的等概率是指,每次等概率地从\(\{0,1\}\)中取出一个元素(\(0\)\(1\)),然后重复\(n\)次,形成一个\(n\times 1\)\(n\)维向量\(v\)。 

  2. 在上面的例子中,我们有\(1-\frac{1}{2^k}\)的概率能够得出正确的解,虽然这是一个很接近于1的概率,但是毕竟不能说成\(100\%\) 

  3. 这里的单边和双边是我自己翻译的,我没有找到比较正统的翻译,于是只能自己来了。 

Share on: TwitterFacebookEmail


Flyaway is the owner of this blog.

Published

Category

randomized-algorithm

Tags

Contact