1985 - Yao 計算隨機性#

案件摘要#

1985 年，Andrew Yao 發表兩篇里程碑論文，建立了計算隨機性理論：一是《Separating the polynomial-time hierarchy by oracles》（與他人，相對化世界），二是《Computational Randomness and Pseudorandomness》方向的工作——正式定義 BPP 類的地位、弱隨機源（weak random source）的可利用性，以及Yao 原理：隨機演算法的最壞情況表現 = 確定性演算法對最壞輸入分佈的表現。Yao 把「隨機」從哲學問題變成了可計算、可證明的數學對象。

前因 -- 為什麼會有這個案子#

到 1985 年，隨機算法已有殺手級應用（Miller–Rabin、Karp 指紋），但理論上有三大懸案：

BPP 的地位：BPP 與 P、NP 的關係不明。
弱隨機源：現實的隨機源（硬體雜訊）有偏——演算法假設的完美銅板不存在，隨機算法還能用嗎？
隨機化的價值：Quicksort 分析（見 1961-Hoare快速排序.md）顯示「隨機化輸入」有用，但「隨機化演算法」與它的關係是什麼？

線索與推理 -- 數學式、程式、理論#

BPP 的正式定義#

定義： \(L \in \mathrm{BPP}\) 若存在多項式時間機率圖靈機 \(M\) ：

\[ x \in L \implies P(M(x) = \text{accept}) \ge \frac{2}{3}, \qquad x \notin L \implies P(M(x) = \text{accept}) \le \frac{1}{3} \]

常數 1/3 不神聖：由 Chernoff 界，重複 \(k\) 次多數決，錯誤 \(\le e^{-\Omega(k)}\) 指數衰減——BPP 具有可放大的錯誤控制。

\[ P(\text{錯}) = \sum_{i>k/2} \binom{k}{i} p^i (1-p)^{k-i} \le e^{-k(1/2-p)^2/2} \]

弱隨機源與 simulating BPP#

問題：演算法需要 \(\{0,1\}\) 等機率銅板，但現實隨機源是有偏的（min-entropy 低）。Yao 之前的答案：von Neumann (1951) 的提取法——把有偏銅板對 \((01, 10)\) 映射為 0/1：

\[ P(01) = p(1-p) = P(10) \implies \text{輸出無偏} \]

但效率極低（丟掉 11, 00）。Yao 的工作開啟了隨機提取器（extractor）理論：用 \(O(\log n)\) 真隨機位元，把弱源「提取」成近隨機位元。這後來由 Nisan–Zuckerman (1996) 完成——弱源不可怕，可以提取。

Yao 原理#

定理（Yao 1977）：

\[ \max_{\text{確定性 } A} \min_{\text{分佈 } D} \ldots \quad \text{更精確地：} \quad \min_R \max_x \mathrm{cost}(A_R, x) \;\ge\; \max_D \min_A \mathrm{E}_{x \sim D}[\mathrm{cost}(A, x)] \]

白話：隨機演算法（對最壞輸入）的最優成本 ≥ 最優確定性演算法（對最壞輸入分佈）的成本。

用途（反向）：要證明「任何隨機算法都要花費 \(c\) 」，只需構造一個輸入分佈，使得任何確定性演算法對它都要花費 \(c\) 。這把「下界證明」從隨機演算法（難）轉移到確定性演算法 + 分佈（較易）——下界證明的標準武器。

範例：證明任何比較排序需要 \(\Omega(n \log n)\) 次比較——考慮隨機排列分佈，任何確定性比較排序對它期望 \(\log_2 n! = \Omega(n \log n)\) 次比較（資訊論下界）。由 Yao 原理，隨機化排序也逃不掉。

程式碼：von Neumann 提取與 Chernoff 放大#

import random, math

def von_neumann_extract(biased_flips):
    """有偏銅板 -> 無偏位元（丟 00, 11）"""
    bits, i = [], 0
    while i + 1 < len(biased_flips):
        a, b = biased_flips[i], biased_flips[i+1]
        if a == 1 and b == 0: bits.append(1)
        if a == 0 and b == 1: bits.append(0)
        i += 2
    return bits

random.seed(42)
flips = [1 if random.random() < 0.8 else 0 for _ in range(100000)]  # 80% 偏
bits = von_neumann_extract(flips)
print(f"原偏率={sum(flips)/len(flips):.3f} 提取後={sum(bits)/len(bits):.3f}")
# 提取後 ≈ 0.500：無偏了

def majority_vote(answers):
    """BPP 錯誤放大：k 次答案取多數"""
    return sum(answers) * 2 > len(answers)

# 錯誤率 0.4 的演算法重複 101 次，多數決錯誤率？
p, k = 0.4, 101
err = sum(math.comb(k, i) * p**i * (1-p)**(k-i) for i in range(k//2+1, k+1))
print(f"多數決錯誤率 = {err:.2e}")   # ≈ 0.02：Chernoff 指數衰減

BPP 與 P 的懸案#

Yao 的工作確立了中心的未解問題：BPP = P 嗎？

相對化世界（Baker–Gill–Solovay 1975，見 ../計算理論/1975-相對化世界.md）：存在神諭使 BPP ≠ P，也存在使相等——常規技術不夠。
去隨機化（Impagliazzo–Wigderson 1997，見 1997-ImpagliazzoWigderson去隨機化.md）：若存在指數時間難的問題，BPP = P。
今日共識：多數理論家相信 BPP = P（隨機性不給本質力量，只給優雅）。

偵探筆記：Yao 的推理是把哲學問題「什麼是真隨機」轉化為計算問題「有什麼演算法能區別」——不可區別性（indistinguishability）成為定義隨機性的新方式。這個「用計算能力定義數學性質」的模式，是現代密碼學與複雜度理論的共同靈魂。

結案 -- 後果與影響#

計算隨機性理論成立：BPP、弱源、提取器、Yao 原理成為隨機算法理論的四梁八柱。
偽隨機產生器：Yao 的下一個位元測試（1982）與 Blum–Micali（1985，見 1985-BlumMicali偽隨機產生器.md）共同奠定現代密碼學。
下界證明的方法論：Yao 原理成為隨機算法下界的標準工具。
去隨機化綱領：BPP = P 懸案至今，去隨機化定理（1997）是最大進展。
圖靈獎：Yao 獲 2000 年圖靈獎。

關鍵人物與文獻#

Andrew Chi-Chih Yao（姚期智，1946–）：圖靈獎 2000；Yao 原理 (1977)、下一個位元測試 (1982)、計算隨機性 (1985)
von Neumann：有偏銅板提取 (1951)
Baker, Gill, Solovay：相對化世界 (1975)
Nisan, Zuckerman：隨機提取器 (1996)
交叉參照：1985-BlumMicali偽隨機產生器.md、1997-ImpagliazzoWigderson去隨機化.md、../計算理論/1975-相對化世界.md