拉斯維加斯與蒙地卡羅演算法之間的轉換

想像同一台機器上的兩個設定。一個設定總是給出正確答案，但花費的時間無法預測；另一個總是按計時器結束，但可能出錯。事實證明，你常常可以在這兩個設定之間切換，用時間上的保證換取正確性上的保證，或反過來。這種切換就是拉斯維加斯與蒙地卡羅之間的轉換。

拉斯維加斯轉蒙地卡羅是容易的方向：取一個永遠正確、時間可變的演算法，在選定的時間預算 T 之後直接截斷它。若它已完成，回傳其（正確的）答案；若未完成，回傳一個預設猜測或回報失敗。由馬可夫不等式，若期望時間為 mu，跑超過 T = 2 mu 的機率最多為二分之一，於是你得到一個快速、固定時間的演算法，其錯誤機率由 T 的寬鬆程度控制——這就是純粹的蒙地卡羅。蒙地卡羅轉拉斯維加斯則在你能快速驗證候選答案時可行：跑蒙地卡羅演算法，檢查其輸出是否真的正確，若不正確就用全新隨機性再跑一次；重複直到檢查通過。由於每次嘗試以機率 p 成功，期望嘗試次數為 1/p，而每個回傳的答案都經過驗證——這就是純粹的拉斯維加斯。例如卡格最小割是蒙地卡羅的，但若你有快速方法確認某個割是最小的，你就能反覆重跑直到確認為止。

這帶來一個乾淨的對偶：硬性的時間界限與硬性的正確性保證是同一枚隨機硬幣的兩面，而隨機性讓你花其一去買其二。蒙地卡羅轉拉斯維加斯方向的難處是真實的：它需要一個對答案的高效驗證器，而這並不總是存在（你能瞬間檢查一個陣列是否已排序，但檢查某數是否為真正的中位數、或某割是否為全域最小，可能跟解題本身一樣難）。當沒有快速檢查時，你只能困在蒙地卡羅殘留的錯誤裡。