確定性演算法可以被對手構造出最壞輸入；隨機化讓對手無從預測你的行為。
Las Vegas vs Monte Carlo
隨機化演算法分兩類：
Las Vegas：結果一定正確，執行時間是隨機變數（但有好的期望值）。Randomized QuickSort 是典型——隨機選 pivot，最壞仍是 O(n²)，但期望 O(n log n)，且對手無法構造讓你每次都選到最差 pivot 的輸入。
Monte Carlo：執行時間固定，結果以高機率正確。Miller-Rabin 質數測試是典型——k 次測試後誤判機率 ≤ 4^(-k)，k=40 時誤判機率約 10^(-24)，工程上視為 0。
Reservoir Sampling：不知道總量也能均勻抽樣
資料流源源不斷，不知道總共有 n 個元素，要從中均勻隨機選 k 個。
傳統做法需要先知道 n，才能計算每個元素被選中的機率。Reservoir Sampling 不需要：
int[] reservoirSampling(int[] stream, int k) {
int[] reservoir = Arrays.copyOf(stream, k); // 前 k 個直接放入
for (int i = k; i < stream.length; i++) {
int j = random.nextInt(i + 1); // [0, i] 的均勻隨機整數
if (j < k)
reservoir[j] = stream[i]; // 以 k/(i+1) 的機率替換
}
return reservoir;
}數學歸納法可以證明：每個元素最終被選中的機率恰好是 k/n。YouTube 的「每日精選」、A/B 測試的用戶採樣，都是這個演算法的應用。
Fisher-Yates Shuffle：真正的均勻洗牌
Math.random() 直接排序不是均勻隨機的——每種排列出現的機率不相等。Fisher-Yates 保證均勻：
void shuffle(int[] arr) {
for (int i = arr.length - 1; i > 0; i--) {
int j = random.nextInt(i + 1); // [0, i]
swap(arr, i, j);
}
}從後往前，每個位置從「還沒固定的元素」裡均勻隨機選一個放入。n! 種排列，每種概率恰好 1/n!。
常見錯誤：random.nextInt(arr.length) 而不是 random.nextInt(i + 1)——這會讓某些排列出現機率更高。
Miller-Rabin 質數測試
判斷一個大數 n 是否為質數。試除法需要 O(√n)，對於 64-bit 整數約 3×10⁹ 次，太慢。
Miller-Rabin 用費馬小定理的強化版：
若 p 是質數，則對任意 a，2^k 次測試後：
a^(n-1) ≡ 1 (mod n)
且這個 1 是「從 -1 轉過來的」
隨機選 k 個底數 a 測試
每個 a 如果沒被排除 → 可能是質數
被任意一個 a 排除 → 確定是合數
k 次測試後合數通過的機率 ≤ 4^(-k)
k=40：誤判概率 ≈ 10^(-24)
Python 的 sympy.isprime()、Java 的 BigInteger.isProbablePrime() 底層都是 Miller-Rabin 或類似的概率質數測試。
隨機化的精髓不是「靠運氣」，而是「讓你的行為對對手不可預測」——這是確定性演算法做不到的。