到底為何要把硬幣放進演算法裡
你至今遇到的每個演算法都是決定性的：同樣的輸入、同樣的步驟、每一次都給同樣的答案。一個隨機演算法故意打破這條規則——它被允許在執行時擲硬幣，於是同樣的輸入可能把它送上不同的路徑。這聽起來像是把控制權扔掉了，而自然的擔憂是：它一定也把可靠性扔掉了。整個這一階令人意外之處在於：一點點隨機性，只要花得明智，便能買到決定性難以匹敵的速度與簡潔。
這裡有個關鍵的心態轉變。回想漸進那一階我們如何談論最壞、最佳、平均情況。平均情況分析很脆弱：它對假設的輸入分布取平均，所以一個故意餵你壞輸入的對手就能擊敗它。隨機化把骰子從輸入裡搬出來，放進演算法裡。如今輸入可以是你想像得到最惡毒、且事先固定好的那一個——我們仍取平均，但是對「我們自己的擲幣」取平均，而那是對手既看不到也左右不了的。保證不再是「在典型輸入上表現好」，而變成「在每個輸入上、對我自己的隨機性取期望都表現好」。把隨機性搬遷位置，正是整件事的要點。
兩種下注方式：答案，還是時間
一旦你允許擲硬幣，恰好只有兩件事可能出錯，而你放任哪一件出錯，就界定了兩大家族。一個拉斯維加斯演算法的答案「永遠」正確；硬幣只影響它跑多久。它的執行時間是一個隨機變數，而我們報出的是它的「期望」時間。一個蒙地卡羅演算法則是它的鏡像：它總在一個固定的時間界內結束，但它的答案只以某個機率正確——它被允許出錯，出錯的機會由你掌控。
一幅樸實的畫面便能釘牢它。拉斯維加斯是一位謹慎的遊客，不真正找到正確的旅館就拒絕離開這座城市——他終會抵達，但你無法向朋友保證確切是何時。蒙地卡羅是一位嚴守火車時刻表的遊客：無論如何都在保證的鐘點離站，但有一點小機率上錯車。一個拿時鐘下注、守住誠實；另一個拿誠實下注、守住時鐘。你永遠不能兩者都不賭——那不過就是一個決定性演算法了——而一個兩者都賭、可以既慢又錯的方法，則毫無用處。
一對實例：快速排序 vs 弗賴瓦爾茲
用每個家族各一個演算法把它具體化。隨機快速排序是拉斯維加斯式的。你排序的方法是均勻隨機地挑一個樞紐、做分割、再遞迴。無論硬幣選了哪些樞紐，輸出都是一個正確排序好的陣列——正確性從不動搖。硬幣掌控的是工作量：走運的一次平均地分裂、花 O(n log n)；倒楣的一次一直挑到極端樞紐、退化到接近 O(n^2)。那條招牌結論——期望值的線性性質那一篇會證明它——是「期望」時間在每個輸入上都是 O(n log n)。對附帶細則要誠實：O(n log n) 是期望值，而最壞情況仍是 O(n^2)——隨機化讓那個最壞情況變得天文數字般地不可能，而非絕無可能。
現在是蒙地卡羅的鏡像：用來檢查矩陣乘積的弗賴瓦爾茲演算法。有人遞給你三個 n 乘 n 的矩陣 A、B、C，宣稱 A 乘 B 等於 C。重算一遍 A 乘 B 來檢查要花大約 O(n^3)。弗賴瓦爾茲反過來挑一個隨機的 0/1 向量 r，測試 A 乘（B 乘 r）是否等於 C 乘 r——三次矩陣對向量的乘積，僅 O(n^2) 的工作量。如果 A 乘 B 真的等於 C，這測試必定通過。如果它們不同，這測試以至少二分之一的機率抓到。所以單跑一次既快又是單邊的：它從不誤拒一個真確的乘積，但它可能讓一個錯誤的溜過去，機率至多二分之一。
FREIVALDS(A, B, C): # all n x n
r <- random 0/1 vector of length n
x <- B * r # O(n^2)
if A * x == C * r: # O(n^2)
return "probably equal"
else:
return "definitely NOT equal" # never wrong here便宜的信心：把錯誤狠狠壓下去
二分之一的出錯機會聽起來嚇人，直到你看見能多麼猛烈地把它壓碎。對一個「單邊」蒙地卡羅演算法——只朝一個方向出錯的那種，像弗賴瓦爾茲說「相等」——的訣竅是獨立重複。用全新的硬幣跑它 k 次。如果 A 乘 B 真的和 C 不同，每一次獨立地以至少二分之一的機率抓到差異，於是被騙的唯一辦法是「全部」k 次都漏掉。因為那些硬幣是獨立的，這些漏掉相乘起來：被騙的機率至多是 (1/2)^k。
- 弗賴瓦爾茲跑一次：錯誤機率至多 1/2。很快，但你不會拿飯碗來賭它。
- 用獨立的硬幣跑 10 次，只在全部十次都說「相等」時才接受。錯誤機率至多 (1/2)^10，不到千分之一——而代價仍只是 10 倍的 O(n^2)，也就是 O(n^2)，遠低於重算的 O(n^3)。
- 想要百萬分之一？跑 20 次：(1/2)^20 小於百萬分之一。每多跑一次就把錯誤「減半」，於是信心呈指數成長、代價卻只線性成長。那份不對稱正是全部的魔法。
兩個誠實的提醒。其一，這乾淨的減半之所以成立，是因為弗賴瓦爾茲是單邊的：單單一個「不相等」就是一道確切的證明，所以重複只需要抓到差異一次。對一個兩個方向都可能出錯的「雙邊」演算法，你不能只用「全體一致才接受」；你要對多次執行取「多數決」，錯誤仍迅速縮小——但證明它需要後續幾篇的尾界機制，而非一行的乘積。其二，「機率至多 (1/2)^k」是對你的硬幣而言，不是關於輸入的頻率主張；真正的隨機源很重要，因為一個可預測的偽隨機產生器，會被知曉它的對手玩弄。
在兩者之間轉換
這兩個家族不是密封的盒子；有一座方向乾淨的橋，與一條回程較滲漏的路。容易的方向：任何拉斯維加斯演算法都能轉成蒙地卡羅。拿一個期望時間為 T 的拉斯維加斯方法，跑它，但砸下一個硬性截止時限，比方說 10 倍的 T。依照我們稍後會磨利的馬可夫式推理，它幾乎總在時限內完成；若時限先到，就停下、隨便給個答案（或「不知道」）。你把一個「保證正確但時程開放」的方法，換成了一個「保證快但偶爾出錯」的方法。誠實進、誠實出：給出壞答案的機會，恰恰就是時鐘走完的機會。
反方向——從蒙地卡羅回到拉斯維加斯——需要一份額外的禮物：一個能快速「檢查」候選答案是否正確的辦法。若你有這樣一個檢查器，就把蒙地卡羅演算法包進一個迴圈：跑它、檢查輸出；正確就回傳，不正確就擲新硬幣再試。每一輪都是「正確或重試」，所以你最終回傳的不論是什麼都保證正確——那就是拉斯維加斯。試驗的次數是隨機的（在每次成功機率下呈幾何分布），於是「時間」如今成了那個隨機量，恰如一個拉斯維加斯方法所要求的。難處在那個檢查器：少了一個高效驗證答案的辦法，這個轉換就卡住，這正是為什麼它是較難的方向。
那麼，面對一個真實任務該如何挑家族？問問你最輸不起的是什麼。若一個錯誤答案是災難性的、但你能容忍不固定的完成時間，就建拉斯維加斯、報出期望時間——隨機快速排序、隨機選擇，那種你真的會出貨的排序。若你面對一道硬性的即時截止時限、且能接受一個小而可控的錯誤——一個串流計數器、一道質數初篩、一次指紋核對——就伸手取蒙地卡羅，用重複把錯誤壓下去。這一階最深的教訓是：隨機性不是草率；它是一種你刻意花用的資源，而指明你買的是「哪一種」保證——答案，還是時鐘——是你做的第一個、也最能釐清一切的決定。