一個割，與一個驚人地天真的構想
想像一個連通的無向圖——由邊連接節點的網路。一個割把頂點切成兩個非空的群組，它的大小是被切斷的邊數，也就是兩端分屬不同群組的那些邊。最小割是這類數字中最小的：你能刪掉的、把圖斷成兩片的最少邊數。它衡量網路有多脆弱，是你在網路流裡遇過的 s-t 割的無向表親——只是現在沒有固定的源點或匯點，你只想要把圖一分為二的、全域最便宜的方式。
你已經知道一種找法：把某個頂點釘為源點，輪流把其他每個頂點當匯點，各跑一次最大流，取最小的——正確，但要算很多次流。1993 年 David Karger 提出了一個看來粗糙到不可能行得通的東西。反覆隨機挑一條邊並收縮它：把它的兩個端點黏成單一個合併頂點，保留其他所有的邊（於是合併頂點之間可能堆起平行邊），但丟掉任何如今從合併頂點繞回自己的自環邊。一直收縮，直到只剩兩個頂點。仍跑在這最後兩個頂點之間的那些邊，就是你對最小割的猜測。
while (number of vertices > 2):
pick a remaining edge (u, v) uniformly at random
contract u and v into one vertex # keep parallel edges, drop self-loops
return the edges between the last 2 vertices為什麼隨機黏合竟會落在答案上
讓它運轉的關鍵只有一個構想。固定任何一個特定的最小割 C——一組特定的 k 條邊，移除它們就把圖切開。收縮演算法恰好回傳 C，若且唯若它一次都沒收縮過屬於 C 的邊。為什麼？收縮一條非割邊，合併的是位於 C 同一側的兩個頂點，這讓 C 在更小的圖裡仍完好地是一個割。但收縮一條 C 的邊，會把兩側熔在一起，那個割就再也回不來了。於是整個問題化簡成一個乾淨的問題：我們在每一次收縮中都避開全部 k 條割邊的機率是多少？
現在來數。關鍵事實是：每個頂點的度數至少為 k——若某個頂點的邊少於 k 條，孤立它本身就是一個小於 k 的割，與 k 是最小值矛盾。n 個頂點各自度數至少 k，邊的總數便至少是 n*k/2。所以當我們均勻隨機挑第一條邊時，它落在 C 裡的機率至多是 k / (n*k/2) = 2/n，而我們存活——挑到安全的邊——的機率至少是 1 - 2/n。每次收縮把頂點數減一，對更小的圖套用同樣的論證，存活機率至少是 1 - 2/(n-1)、接著 1 - 2/(n-2)，一路下到剩 3 個頂點。
把這些存活機率全部相乘，一個小小的伸縮奇蹟就發生了。乘積 (1 - 2/n)(1 - 2/(n-1))...(1 - 2/3) 等於 ((n-2)/n)((n-3)/(n-1))((n-4)/(n-2))...，幾乎一切都抵銷，塌縮成 2 / (n*(n-1))。所以單次執行找到任一固定最小割的機率至少是 2/(n*(n-1))，大約是 2/n^2。這聽來慘澹——n = 1000 時約是五十萬分之一——但要小心它真正說的是什麼：這機率並非在壞的意義上消失，它只是多項式地小，而多項式地小，正是隨機性能修好的東西。
把渺茫機會變成近乎確定
若故事到此為止，每次 2/n^2 的成功機率會毫無用處——但這才是開頭。獨立地把整套收縮跑很多次，每次保留你見過最小的割，最後回報最佳的那個。各次執行是獨立的擲幣實驗，所以所有執行都錯過那個固定最小割的機率，至多是 (1 - 2/n^2) 的試驗次數次方。這正是在 拉斯維加斯與蒙地卡羅那篇裡、把單次嘈雜的蒙地卡羅猜測變成可靠答案的同一套放大邏輯——獨立性，正是讓失敗機率相乘的東西。
- 用標準的擠壓：1 - x 至多是 e^(-x)，所以單次執行失敗的機率至多是 e^(-2/n^2)。獨立地把收縮跑 T 次，每次都失敗的機率至多是 e^(-2T/n^2)。
- 取 T 約為 (n^2 / 2) * ln n。那麼全部失敗的機率降到約 e^(-ln n) = 1/n，於是有至少 1 - 1/n 的機率，你已找到一個真正的最小割——一種隨問題規模增長的高信心。
- 把 T 再乘高一個常數倍，失敗機率就變成 1/n^2、1/n^3，隨你要多少。你能用更多次執行買到任何想要的信心；錯誤從不歸零，只是縮到比任何要緊的東西都更小。
對代價要誠實。一次收縮執行約花 O(n^2) 的功，而要讓失敗變罕見，你需要約 n^2 log n 次執行，所以樸素的卡格落在約 O(n^4 log n)——理論上沒問題，實務上慢，對許多圖還慢於一個用心寫的最大流方法。那個精妙的改良 Karger-Stein 注意到：早期的收縮非常安全，只有後期的（剩沒幾個頂點時）才危險；藉由遞迴、只在危險的尾端重複功夫，它達到 O(n^2 log^3 n)。重點教訓是這個設計模式，而非那個常數：一個僅僅多項式地小的單次成功機率，經獨立重複放大後，就成了一個你要多強就有多強的保證。
指紋法：用單一數字比較龐然大物
現在來看隨機性一種截然不同的用法，也是整個演算法設計裡最常被重用的構想之一：指紋法。情境到處重現——你有兩個龐大的物件，兩個百萬位元組的檔案、兩條長位元串、兩個多項式，而你想知道它們是否相等，卻不願付出逐符號比較的代價。訣竅是把每個物件雜湊成一個簡短的隨機指紋，只比較指紋。若指紋不同，物件必定不同。若指紋相符，物件幾乎必定相等——而你能把那個「幾乎」調到要多接近確定就多接近確定。
最乾淨的例子是驗證矩陣乘積的 弗賴瓦爾茲演算法。有人遞給你三個 n×n 矩陣 A、B、C，宣稱 A*B = C。靠重算 A*B 來檢查約花 O(n^3)（用最花俏的方法是 O(n^2.37...)）。弗賴瓦爾茲改為在 O(n^2) 內驗證：挑一個隨機的 0/1 向量 r，測試 A*(B*r) 是否等於 C*r——三次矩陣乘向量，每次 O(n^2)。若 A*B 確實等於 C，測試永遠通過。若 A*B 與 C 哪怕只有一個元素不同，一段簡短的計算顯示測試以至少 1/2 的機率抓到它。這看來薄弱，直到你想起獨立性：用十個全新的隨機向量跑它，一個真正錯誤的乘積溜過去的機率至多是 (1/2)^10，不到千分之一。
會滑動的指紋：從字串到拉賓-卡普
指紋法最出名地在字串比對裡立功。要測試兩條長度為 m 的字串是否相等，把每條看成某個基底下寫出的大數，再對一個隨機質數 p 取模——那個餘數就是它的指紋，一個機器字。兩條相等的字串永遠共享指紋。兩條不同的字串只在 p 恰好整除它們的差時碰撞，而由於一個 m 位的數只有少數質因數，從夠大的範圍隨機選的質數碰撞機率至多約是 m/p，你把 p 選大就讓它變得微乎其微。整個比較從 m 次符號檢查，縮成一次數字比較。
這是 拉賓-卡普比對的引擎，而它倚賴另一個美麗的構想：滾動雜湊。要在長度 n 的文字裡找一個長度 m 的樣式，你必須為文字的每一個長度為 m 的視窗算指紋。從頭重算每個指紋，每個視窗要花 O(m)，把你拖回 O(n*m)。但相鄰的視窗除了一個字元之外全部重疊，所以指紋能在 O(1) 內更新：減掉滑出的字元的貢獻、乘上基底把一切上移一位、再加上滑入的字元——全程保持在模數之下。視窗的指紋就這樣一次一個便宜的步驟，沿著文字滾動。
加總起來，拉賓-卡普以 O(n + m) 的期望時間掃完整段文字。當一個視窗的指紋與樣式相符時，那只是一個可能的相符：謹慎的版本接著直接驗證那 m 個字元，以排除罕見的碰撞，這讓它在速度上是蒙地卡羅、在正確性上卻是拉斯維加斯——從不出錯，只是偶爾較慢。若對手刻意製造一堆碰撞，最壞情況仍是 O(n*m)，正如隨機快速排序在它 O(n log n) 期望時間背後仍藏著一個 O(n^2) 的最壞情況。隨機性買到的是一個快的期望時間與一個可控的錯誤，而非一個鐵打的最壞情況保證——而綜觀卡格、弗賴瓦爾茲與拉賓-卡普，那正是整個這一階反覆出現的、誠實的交易。