9.1 隨機化演算法與BPP#

概念說明#

隨機化演算法在執行過程中擲骰子，用「極小的失敗機率」換取「大幅的加速或簡潔性」。兩大類型：

拉斯維加斯（Las Vegas）：結果永遠正確，但執行時間是隨機變數（例如隨機化的快速排序）。
蒙地卡羅（Monte Carlo）：時間固定，但結果有小機率出錯（例如 Miller–Rabin 質數測試）。

BPP 類別（Bounded-error Probabilistic Polynomial time）：可在多項式時間內以擲硬幣計算解決、且錯誤率 ≤ 1/3 的決策問題類別。1/3 這個常數不特殊——只要錯誤率是某個小於 1/2 的常數，都可以藉重複執行 + 多數決把錯誤率壓到 n^(−c)（Chernoff 界），代價只是多跑幾次。

隨機化的經典勝利：

Miller–Rabin 質數測試：O(k log³ n) 判斷 n 是否質數（錯誤率 ≤ 4^(−k)），而確定性多項式演算法（AKS, 2002）晚了 25 年才出現且慢得多。注意質數測試其實在 P 中——但實務永遠用隨機版。
多項式恆等測試（PIT）：判斷一個以算術電路表示的多項式是否恆為零，隨機代入求值即可高機率正確，至今沒有已知的有效確定性演算法（derandomizing PIT 是重大未解問題）。
隨機化最小割、隨機化匹配等。

理論上的一個驚人發展是 Sipser–Gács–Lautemann 定理：BPP ⊆ Σ₂ ∩ Π₂（多項式階層第二層），而且多數學者相信 P = BPP——「骰子不會增加真正的計算能力」。若能證明某些下界，隨機性可被偽隨機產生器完全消除。

演算法步驟（蒙地卡羅估計 π 與 Miller–Rabin）#

π 估計：在單位方形隨機撒 n 點，統計落在四分之一圓內的比例 p，π ≈ 4p。誤差 O(1/√n)。
Miller–Rabin：對待測 n，寫 n − 1 = 2^s·d（d 奇數）。隨機取底數 a，計算 a^d mod n；若非 1 且連平方 s 次都未出現 −1，則 n 為合成數。重複 k 次皆通過 ⟹ n 很可能是質數。

Python 程式碼範例#

import random

def estimate_pi(n=10**7):
    """蒙地卡羅估計 π：誤差 O(1/sqrt(n))"""
    inside = 0
    for _ in range(n):
        x, y = random.random(), random.random()
        if x * x + y * y <= 1:
            inside += 1
    return 4 * inside / n

def miller_rabin(n, k=20):
    """Miller-Rabin 質數測試，錯誤率 ≤ 4^-k"""
    if n < 2:
        return False
    for p in (2, 3, 5, 7, 11, 13, 17, 19, 23, 29):
        if n % p == 0:
            return n == p
    d, s = n - 1, 0
    while d % 2 == 0:
        d //= 2; s += 1

    def witness(a):
        x = pow(a, d, n)
        if x in (1, n - 1):
            return False
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                return False
        return True                      # a 是證人：n 必為合成

    return not any(witness(a)
                   for a in random.sample(
                       range(2, min(n - 1, 10**6)), k))

def repeat_majority(alg, data, reps=7):
    """重複執行 + 多數決：把錯誤率 1/3 壓到 ~2^-7"""
    votes = sum(alg(data) for _ in range(reps))
    return votes > reps // 2

print(estimate_pi(10**6))                # ≈ 3.141...
print(all(miller_rabin(p) for p in
          [101, 7919, 104729, 1299709])) # True
print(miller_rabin(561))                 # False（卡麥可數也能擋住）

複雜度分析#

蒙地卡羅 π：O(n) 時間，標準差 O(1/√n)——把誤差降一位數需要 100 倍樣本。
Miller–Rabin：O(k·log³ n)，錯誤率 ≤ 4^(−k)；k = 20 時已低於硬體故障率，實務視為確定。
放大技術：錯誤率 ε 重複 r 次多數決後變 exp(−2r(1/2−ε)²)（Chernoff），多項式代價換指數級改善。
BPP 的定位：P ⊆ BPP ⊆ Σ₂ ∩ Π₂ ⊆ PSPACE；普遍猜測 P = BPP，隨機化是「實務利器、理論可消除」。

練習#

實驗：n 從 10² 到 10⁶ 各估計 π 十次，繪出誤差與 1/√n 的關係，驗證收斂速率。
修改 Miller–Rabin 回傳「合成數的證人 a」，用 561、1105、1729 三個卡麥可數測試。
說明為什麼「錯誤率 1/2 的 BPP 演算法」是無用的（擲硬幣都不如），而 1/3 就可以透過放大變得有用。