1 隨機(jī)算法

隨機(jī)性在計(jì)算機(jī)科學(xué)中的最初應(yīng)用之一就是隨機(jī)算法。隨機(jī)算法是能夠獲得隨機(jī)性來(lái)源（比如隨機(jī)數(shù)生成器）的算法，它允許在很小的概率內(nèi)出錯(cuò)。目前已經(jīng)有許多問(wèn)題我們知道怎樣用隨機(jī)算法高效地求解，而并不知道怎樣用確定性算法（即不使用隨機(jī)性的算法）高效求解。事實(shí)上，計(jì)算機(jī)科學(xué)中最重要的open problems之一就是詢問(wèn)每個(gè)高效的隨機(jī)算法是否都有其對(duì)應(yīng)求解相同問(wèn)題的確定性算法。

下面是個(gè)簡(jiǎn)單的隨機(jī)算法例子：

import numpy as np
def f(x):
    y = np.random.binomial(1, 0.5)
    if y == 0:
        while x > 0:
            print("What up?")
            x -= 1
    return x + y

對(duì)于一個(gè)確定的輸入（比如\(x=3\)），其輸出可能會(huì)有差異，且其運(yùn)行時(shí)間也可能有差異。那么對(duì)于一個(gè)隨機(jī)算法，我們?nèi)绾味攘科湔_性（correctness）和運(yùn)行時(shí)間（running time）呢？事實(shí)上，如果我們要求它輸出結(jié)果總是正確的，且運(yùn)行時(shí)間總是\(O(T(n))\)，則它就是時(shí)間復(fù)雜度為\(T(n)\)的確定性算法了。

因此，對(duì)于隨機(jī)算法它要么不是在所有情況下總是正確的，要么就不能保證運(yùn)行時(shí)間總為\(O(T(n))\)，它可以看做是在正確性和運(yùn)行時(shí)間之間做賭博(gamble)。

2 蒙特卡洛算法和拉斯維加斯算法

我們來(lái)看下面這個(gè)例子，給點(diǎn)\(n\)個(gè)元素（\(n\)為偶數(shù)）的序列\(A\)，一半為\(0\)一半為\(1\)，我們想在想要找到一個(gè)含\(1\)的序列下標(biāo)。那么我們可以寫出下面兩個(gè)不同的算法：

我們將左邊這種賭博時(shí)間但不賭博正確性的算法稱為拉斯維加斯（Las Vegas）算法，右邊這種賭博正確性但不賭博時(shí)間的算法為蒙特卡洛（Monte Carlo）算法。

如圖所示的拉斯維加斯算法的失敗概率\(\text{Pr}(\text{failure})=0\)，最壞運(yùn)行時(shí)間無(wú)界，期望運(yùn)行時(shí)間為\(O(1)\)(2次迭代)；而如圖所示的蒙特卡洛算法失敗概率\(\text{Pr}(\text{failure})=\frac{1}{2^{300}}\)，最壞運(yùn)行時(shí)間為\(O(1)\)。

總結(jié)一下，在我們上面這個(gè)問(wèn)題中兩個(gè)算法的區(qū)別如下表所示：

下面給出蒙特卡洛算法和拉斯維加斯算法的形式化定義。

蒙特卡洛算法 設(shè)\(f: \Sigma^* \rightarrow \Sigma^*\)為一個(gè)可計(jì)算問(wèn)題，\(0 \leqslant \epsilon<1\)為參數(shù)，\(T: \mathbb{N} \rightarrow \mathbb{N}\)為一個(gè)函數(shù)。若\(A\)為一個(gè)隨機(jī)算法，它使得

• 對(duì)任意\(x\in\Sigma^*\)，\(\operatorname{Pr}\left(A(x) \neq f(x)\right) \leqslant \epsilon\)；
• 對(duì)任意\(x\in\Sigma^*\)，\(\operatorname{Pr}\left(\text { number of steps } A(x) \text { takes is at most } T(|x|) \right)=1\)。

（注意此處的概率基于\(A\)做出的隨機(jī)選擇）
則我們聲稱\(A\)是一個(gè)能夠以\(T(n)\)時(shí)間、\(\epsilon\)的錯(cuò)誤概率計(jì)算問(wèn)題\(f\)的蒙特卡洛算法。

拉斯維加斯算法 設(shè)\(f: \Sigma^* \rightarrow \Sigma^*\)為一個(gè)可計(jì)算問(wèn)題，\(T: \mathbb{N} \rightarrow \mathbb{N}\)為一個(gè)函數(shù)。若\(A\)為一個(gè)隨機(jī)算法，它使得

• 對(duì)任意\(x\in\Sigma^*\)，\(\operatorname{Pr}\left(A(x) = f(x)\right)=1\)（這里概率基于\(A\)做出的隨機(jī)選擇）；
• 對(duì)任意\(x\in\Sigma^*\)，\(\textbf{E}\left(\text { number of steps } A(x) \text { takes }\right) \leqslant T(|x|)\)。

則我們聲稱\(A\)是一個(gè)能夠以\(T(n)\)時(shí)間計(jì)算問(wèn)題\(f\)的拉斯維加斯算法。

3 蒙特卡洛算法實(shí)例：最小割（Min Cut）隨機(jī)化算法

圖割集是一個(gè)邊的集合，當(dāng)去掉這些邊時(shí)將\(G\)分為兩個(gè)或多個(gè)連通部分。給定一個(gè)有\(n\)個(gè)頂點(diǎn)的圖\(G=(V, E)\)，最小割問(wèn)題就是在圖\(G\)中尋找一個(gè)基數(shù)最小的割集，也即找到非空子集\(S\subset V\)使得從\(S\)到\(V-S\)的邊數(shù)最小化。

接下來(lái)我們會(huì)介紹一個(gè)求解最小割算法的簡(jiǎn)單隨機(jī)算法，該算法中重要的操作為邊的縮減。

該算法包括\(n-2\)次迭代（\(n\)為頂點(diǎn)數(shù)目）。在每次迭代中，算法從圖的現(xiàn)有邊中均勻隨機(jī)地選出一條邊并將它縮減掉。在縮減邊\((u, v)\)時(shí)，將兩個(gè)頂點(diǎn)\(u\)和\(v\)合并成一個(gè)頂點(diǎn)，刪除所有連接\(u\)和\(v\)的邊，保留圖中所有其他的邊。新圖可能有重邊，但沒(méi)有自環(huán)。

每一次迭代都會(huì)使圖中的頂點(diǎn)數(shù)目減少一個(gè)，經(jīng)過(guò)\(n-2\)次迭代后，圖中只剩下兩個(gè)頂點(diǎn)。算法輸出連接這兩個(gè)保留頂點(diǎn)的邊的集合。

下面我們來(lái)看在最小割集大小為\(2\)的圖中，兩種最小割算法執(zhí)行的例子。首先是成功運(yùn)行的實(shí)例：

然后是不成功運(yùn)行的實(shí)例：

現(xiàn)在我們來(lái)建立算法輸出正確結(jié)果的概率的下界。

定理 算法至少以\(2/(n(n-1))\)的概率輸出最小割集。

證明 我們?cè)O(shè)集合\(C\)為圖的最小割集，除去集合\(C\)后將頂點(diǎn)集合分為兩個(gè)集合\(S\)和\(V-S\)，使得不存在連接\(S\)中的頂點(diǎn)到\(V-S\)中的邊。我們?cè)谒惴ㄖ锌s減的邊是\(S\)中的頂點(diǎn)或\(V-S\)中頂點(diǎn)的邊，經(jīng)\(n-2\)次迭代后，算法輸出的是由\(C\)中邊連接的兩個(gè)頂點(diǎn)的圖。所有，我們可以得到結(jié)論：如果算法在\(n-2\)次迭代中根本不選擇\(C\)中的邊，那么算法輸出的\(C\)就是最小割集。

設(shè)\(E_i\)表示第\(i\)次迭代時(shí)縮減的邊不在\(C\)中這一事件，\(F_i =\bigcap_{j=1}^i E_j\)表示在前\(i\)次迭代中沒(méi)有縮減\(C\)中邊的事件。我們需要計(jì)算的算法在\(n-2\)次迭代中不選擇\(C\)中的邊的概率，即為\(\text{Pr}(F_{n-2})\)。

我們從計(jì)算\(\text{Pr}(E_1)=\text{Pr}(F_1)\)開(kāi)始。因?yàn)樽钚「罴?span id="w0obha2h00" class="math inline">\(k\)條邊，所以圖中每個(gè)頂點(diǎn)至少連接\(k\)條邊（即度至少為\(k\)），則根據(jù)握手定理圖中至少有\(nk/2\)條邊。第一次縮減的邊是從所有邊中均勻隨機(jī)地選取的，故第一次迭代沒(méi)有選取\(C\)中邊的概率為：

接下來(lái)，假設(shè)第一次縮減沒(méi)有消去\(C\)中的邊，即給定了事件\(F_1\)成立這一條件，那么我們?cè)诮酉聛?lái)的有\(n-1\)個(gè)頂點(diǎn)的新圖中也沒(méi)有選取到\(C\)中邊的概率為：

類似地，我們有：

則

得證。

因?yàn)樗惴ň哂袉芜呭e(cuò)誤的性質(zhì)，我們可以重復(fù)運(yùn)行算法來(lái)減小出錯(cuò)率。假設(shè)運(yùn)行最小割隨機(jī)化算法\(n(n-1)\ln n\)次，并輸出再所有迭代次中找到的最小長(zhǎng)度割集。則輸出不是一個(gè)最小割集的概率界為

在第一個(gè)不等式中，我們用到了經(jīng)典不等式：\(\forall x\in \mathbb{R}: 1 + x \leqslant e^x\)。

4 拉斯維加斯算法實(shí)例：隨機(jī)快速排序算法

快速排序是一種簡(jiǎn)單且實(shí)際上非常有效的排序算法。給定輸入列表\(S=\{ x_1, x_2,\cdots x_n\}\)，隨機(jī)快速排序算法可描述如下：

• 如果\(n\leqslant 1\)，返回\(S\)；

• 均勻隨機(jī)地選擇基準(zhǔn)（pivot）\(x_m\)；

• 將\(S\)中每個(gè)其它元素與\(x_m\)做比較，以將\(S\)劃分為兩個(gè)子列表：\(S_1=\{x_i: x<x_m\}\), \(S_2=\{x_i: x_i>x_m\}\)。

• 遞歸地對(duì)\(S_1\)和\(S_2\)排序。

對(duì)于隨機(jī)快速排序算法，我們有以下定理：
定理 假設(shè)在隨機(jī)快速排序算法中，每一次都是從所有可能中獨(dú)立且隨機(jī)地選取基準(zhǔn)，那么對(duì)于任意的輸入，隨機(jī)快速排序算法所做比較的期望次數(shù)為\(2n\ln n + \Theta(n)\)（這里的期望是關(guān)于基準(zhǔn)的隨機(jī)選取）。

證明 設(shè)\(y_1, y_2, \cdots, y_n\)與輸入值\(x_1,x_2, \cdots, x_n\)有相同的值，但是按照升序排列。對(duì)\(i<j\)，記\(X_{ij}\)為一隨機(jī)變量，如果在算法執(zhí)行過(guò)程的任何時(shí)候\(y_i\)和\(y_j\)進(jìn)行了比較，則\(X_{ij}\)的值為\(1\)，否則取\(0\)。那么比較的總次數(shù)滿足

且根據(jù)期望的線性性得

由于\(X_{ij}\)只是取\(0\)和\(1\)的示性隨機(jī)變量，\(\mathbf{E}(X_{ij})\)等于\(X_{ij}\)為1的概率。因此，我們接下來(lái)只需計(jì)算兩個(gè)元素\(y_i\)和\(y_j\)相比較的概率即可。
現(xiàn)在，\(y_i\)和\(y_j\)相比較，當(dāng)且僅當(dāng)\(y_i\)或\(y_j\)是從集合\(Y^{ij}=\{y_i,y_{i+1},\cdots, y_{j-1}, y_{j}\}\)中由隨機(jī)快速排序算法選取的第一個(gè)基準(zhǔn)。這是因?yàn)槿绻?span id="w0obha2h00" class="math inline">\(y_i\)（或\(y_j\)）是從這個(gè)集合選取的第一個(gè)基準(zhǔn)，\(y_i\)和\(y_j\)必仍在同一個(gè)子列表中，因此它們將會(huì)進(jìn)行比較。反之，如果兩者都不是從這個(gè)集合中選取的第一個(gè)基準(zhǔn)，那么\(y_i\)和\(y_j\)將會(huì)被分在不同的子列表中，所以不會(huì)進(jìn)行比較。

因?yàn)槲覀兊幕鶞?zhǔn)都是從每個(gè)子列表中獨(dú)立且隨機(jī)地選取的，也就是第一次從\(Y^{ij}\)中選取的一個(gè)基準(zhǔn)等可能地是這個(gè)集合中的任一元素。因此\(y_i\)或\(y_j\)是從\(Y^{ij}\)中選取的第一個(gè)基準(zhǔn)的概率（即\(X_{ij}\)取\(1\)的概率）是\(\frac{2}{j-i+1}\)。利用替換\(k=j-i+1\)，得

注意第3個(gè)等式交換了雙重求和的次序，這樣就可以將內(nèi)層求和直接用乘法表達(dá)出來(lái)，從而得到了期望的簡(jiǎn)潔形式。交換求和順序的示意圖如下所示：

又因?yàn)檎{(diào)和級(jí)數(shù)\(H(n) = \sum_{k=1}^n\frac{1}{k}\)滿足\(H(n) = \ln n+ \Theta(1)\)，因此，\(\mathbf{E}(X) = 2n \ln (x) + \Theta(n)\)，得證。

參考

• [1] CMU 15-251: Great Ideas in Theoretical Computer Science: Lecture 19: Randomized Algorithms
• [2] Mitzenmacher M, Upfal E. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis(M). Cambridge university press, 2017.