一句話解釋

在演算法執行過程中使用隨機選擇，換取更簡單的實作、更好的平均效能，或解決確定性演算法難以處理的問題。

什麼是隨機演算法？

核心概念

隨機演算法（Randomized Algorithm） 是在執行過程中會做隨機選擇的演算法。

定義

  • 演算法可以「擲硬幣」或「擲骰子」來決定下一步
  • 給定相同的輸入，每次執行可能產生不同的結果或運行時間
  • 隨機性來源：
    • 偽隨機數生成器（Pseudo-random number generator）
    • 真隨機源（硬體、量子現象等）

與確定性演算法的差異

特性 確定性演算法 隨機演算法
**執行過程** 完全可預測 含隨機選擇
**相同輸入** 總是產生相同結果 可能產生不同結果/時間
**分析方式** Worst-case / Best-case 期望值 / 機率界
**正確性** 絕對保證 可能是機率性保證

為什麼使用隨機演算法？

動機

1. 簡化演算法設計

隨機性可以避免複雜的決策邏輯。

範例：Quicksort
確定性 Quicksort 需要精心選擇 pivot（如 median-of-medians）才能保證 O(n log n)。
隨機 Quicksort 只需隨機選 pivot，期望時間就是 O(n log n)，實作簡單得多。

2. 打破對手策略

在競爭或對抗性環境中，隨機性讓對手無法預測你的行為。

範例：線上演算法
如果演算法的行為可預測，adversary 可以構造最壞輸入。
隨機化讓 adversary 無法針對性地攻擊。

3. 更好的平均效能

某些問題的確定性演算法 worst-case 很差，但隨機版本期望效能很好。

4. 唯一已知的有效方法

某些問題（如質數測試）的確定性多項式演算法直到很晚才被發現，隨機演算法長期是唯一實用解。

💡 核心思想：
隨機性不是「運氣」，而是一種設計工具。我們用機率分析來證明演算法在期望意義下或高機率下表現良好。

Las Vegas vs. Monte Carlo

兩大類別

隨機演算法主要分為兩類：

Las Vegas Algorithms

  • 總是給出正確答案
  • 運行時間是隨機的
  • 我們分析期望運行時間
定義： - 輸出總是正確：$\Pr[\text{Output is correct}] = 1$ - 運行時間 $T$ 是隨機變數：$\mathbb{E}[T] = $ 期望時間

範例：

  • Randomized Quicksort： 總是正確排序，但時間隨 pivot 選擇而變
  • Randomized Min-Cut（重複到成功）： 重複運行直到找到正確答案

Monte Carlo Algorithms

  • 運行時間是確定的（或有界）
  • 答案可能是錯的（但機率很小）
  • 我們分析錯誤機率
定義： - 運行時間固定或有界：$T \leq T_{\max}$ - 可能出錯：$\Pr[\text{Output is wrong}] \leq \epsilon$ （通常 $\epsilon$ 很小）

範例：

  • Miller-Rabin 質數測試： 固定時間，但可能誤判合數為質數
  • Karger's Min-Cut（單次執行）： 多項式時間，但可能找到非最小割

比較表

Las Vegas Monte Carlo
**正確性** ✓ 總是正確 ✗ 可能出錯（機率小）
**運行時間** ✗ 隨機（期望有界） ✓ 確定或有界
**分析重點** 期望時間 $\mathbb{E}[T]$ 錯誤率 $\Pr[\text{error}] \leq \epsilon$
**改進方式** 無法改進正確性（已是 100%） 重複執行降低錯誤率
**命名來源** Las Vegas 賭場：不會輸，但不知何時贏 Monte Carlo 賭場：快速結束，但可能輸

兩者的轉換

Monte Carlo → Las Vegas：

  • 如果 Monte Carlo 演算法能驗證答案是否正確
  • 可以重複運行直到得到正確答案
  • 變成 Las Vegas（正確但時間隨機）

Las Vegas → Monte Carlo：

  • 給 Las Vegas 演算法設定時間上限
  • 超時就輸出「不知道」或隨機答案
  • 變成 Monte Carlo（快但可能錯）

🎲 記憶技巧：

  • Las Vegas = Lucky but Slow（可能）： 一定贏，但可能等很久
  • Monte Carlo = Fast but Risky： 很快結束，但可能輸

經典範例

1. 隨機 Quicksort（Las Vegas）

def randomized_quicksort(A):
    if len(A) <= 1:
        return A
    pivot = random.choice(A)  # 隨機選 pivot
    left = [x for x in A if x < pivot]
    middle = [x for x in A if x == pivot]
    right = [x for x in A if x > pivot]
    return randomized_quicksort(left) + middle + randomized_quicksort(right)
  • 類型： Las Vegas
  • 正確性： 總是正確排序
  • 時間： 期望 $O(n \log n)$，worst-case $O(n^2)$（機率極小）

2. 質數測試（Monte Carlo）

Miller-Rabin 演算法：

  • 輸入：$n$（待測試的數）
  • 輸出：「質數」或「合數」
  • 保證： 如果輸出「合數」，則 $n$ 一定是合數
  • 錯誤： 如果輸出「質數」，$n$ 可能是合數（機率 $\leq 1/4^k$，$k$ 是測試次數）

3. Karger’s Min-Cut

找圖的最小割：

  • 單次執行（Monte Carlo）： 多項式時間，成功率 $\geq \frac{2}{n^2}$
  • 重複執行（Las Vegas）： 運行 $O(n^2 \log n)$ 次，高機率找到最小割

總結

隨機演算法是現代演算法設計的重要工具：

  1. 簡化設計： 避免複雜的確定性邏輯
  2. 打破對抗： 讓 adversary 無法預測
  3. 良好效能： 期望或高機率下表現優異
  4. 兩大類別：
    • Las Vegas： 正確但時間隨機
    • Monte Carlo： 快速但可能出錯

後續課程將深入探討機率工具、複雜度理論、以及各種隨機演算法的設計與分析。

參考資料

  • Motwani & Raghavan, Randomized Algorithms
  • Mitzenmacher & Upfal, Probability and Computing
  • CLRS, Introduction to Algorithms, Chapter 5