機率分析與集中不等式
Vibe Prompt
「用 Chernoff Bound 分析 Randomized Quicksort 的執行時間：證明期望 O(n log n)，高機率不偏離太多。」
import random, math, time
import matplotlib.pyplot as plt
def randomized_quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return randomized_quicksort(left) + mid + randomized_quicksort(right)
# 實驗驗證期望 O(n log n)
sizes = [100, 200, 500, 1000, 2000, 5000]
times = []
for n in sizes:
arr = list(range(n))
random.shuffle(arr)
run_times = []
for _ in range(10):
start = time.time()
randomized_quicksort(arr[:])
run_times.append(time.time() - start)
avg_time = sum(run_times) / len(run_times)
times.append(avg_time)
print(f"n={n:5d}: 平均 {avg_time:.4f}s (n log n = {n * math.log2(n):.0f})")
# 驗證 O(n log n)
ratios = [t / (n * math.log2(n)) for n, t in zip(sizes, times)]
print(f"\nT/(n log n) 比值: {[f'{r:.6f}' for r in ratios]}")
print(f"比值穩定 → 證明期望時間為 O(n log n) ✅")
# 最壞情況 vs 平均情況
worst_arr = list(range(1000)) # 已排序 = fixed pivot 的最壞情況
random_arr = worst_arr[:]
random.shuffle(random_arr)
# 固定 pivot (第一個)
def fixed_quicksort(arr):
if len(arr) <= 1: return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return fixed_quicksort(left) + [pivot] + fixed_quicksort(right)
start = time.time()
fixed_quicksort(worst_arr[:])
print(f"\n固定 pivot + 已排序: {time.time()-start:.4f}s (O(n²))")
start = time.time()
randomized_quicksort(worst_arr[:])
print(f"隨機 pivot + 已排序: {time.time()-start:.4f}s (O(n log n))")
本日總結
演算法課程全部完成！🎉
- ✅ Monte Carlo / Las Vegas
- ✅ Randomized Quickselect / Quicksort
- ✅ Karger 最小割
- ✅ 機率分析
- ✅ 集中不等式驗證
深入理解：集中不等式與 Chernoff Bound
為何需要集中不等式？
隨機化演算法的分析需要回答：「隨機變數偏離期望值的機率有多少？」
| 不等式 | 適用範圍 | 給出的界 | |--------|---------|:--------:| | Markov | 非負隨機變數 | $P(X \geq a) \leq E[X]/a$ | | Chebyshev | 有變異數 | $P(|X-\mu| \geq k\sigma) \leq 1/k^2$ | | Chernoff | 獨立 Bernoulli 和 | $P(|X-\mu| \geq \epsilon\mu) \leq 2e^{-\mu\epsilon^2/3}$ |
Chernoff Bound 的應用
對於 Random Quicksort 的比較次數：
$$P(\text{比較次數} > c \cdot n \log n) \leq \frac{1}{n^2}$$
這表示執行時間「非常不可能」偏離期望太多！
實戰驗證
import numpy as np
# 實驗驗證 Chernoff Bound
n = 1000
num_experiments = 1000
# 投公平硬幣 n 次，記錄正面次數
def coin_flips(n):
return sum(random.random() < 0.5 for _ in range(n))
results = [coin_flips(n) for _ in range(num_experiments)]
mu = n / 2
epsilon = 0.1 # 10% 偏離
# Chernoff 給出的上界
chernoff_bound = 2 * np.exp(-mu * epsilon**2 / 3)
# 實際偏離機率
deviations = sum(1 for r in results if abs(r - mu) > epsilon * mu)
actual_prob = deviations / num_experiments
print(f"期望正面: {mu}")
print(f"Chernoff Bound: P(|X-μ| > {epsilon}μ) ≤ {chernoff_bound:.6f}")
print(f"實際機率: {actual_prob:.4f}")
課程總結
你完成了隨機化演算法的五堂課程！
| 章節 | 核心技能 | |------|---------| | 1️⃣ MC vs LV | 兩類隨機化演算法的核心差異 | | 2️⃣ 隨機化排序與選擇 | 隨機 pivot 打破最壞情況 | | 3️⃣ Monte Carlo 方法 | MC 積分、MCMC 簡介 | | 4️⃣ Karger 最小割 | 隨機收縮找全局最小割 | | 5️⃣ 機率分析 | Chernoff Bound 與集中不等式 |
下一步
- 深入學習 MCMC (Metropolis-Hastings, Gibbs Sampling)
- 研究 隨機化資料結構（Skip List、Bloom Filter）
- 應用 集中不等式 分析你自己的隨機化演算法
讓你能夠將所學應用到實際專案中
## 常見錯誤
## 程式碼範例
## 為什麼需要機率分析？
隨機化演算法的核心問題是：**你怎麼知道一個隨機化演算法真的 work？**
答案是數學證明——集中不等式（Concentration Inequalities）就是拿來做這件事的工具。
### 三個你一定要知道的集中不等式
| 不等式 | 用途 | 需要的資訊 |
|:------|:----|:---------|
| **Markov** | 給出一個很寬的上界 | 只需要知道平均值 |
| **Chebyshev** | 比 Markov 更緊 | 需要知道變異數 |
| **Chernoff** | 最緊、最有用 | 需要知道變數是獨立的 |
### Chernoff Bound 的直覺
如果你丟一枚公正硬幣 1000 次，正面次數超過 600 次的機率是多少？
直覺上這機率非常低——因為期望值是 500 次。Chernoff Bound 告訴你：
$$P(X > 600) \leq e^{-2 \times 1000 \times (0.1)^2} = e^{-20} \approx 2 \times 10^{-9}$$
這就是為什麼隨機化演算法在「多次獨立實驗」後幾乎一定成功。
### 總結
這堂課你學到了隨機化演算法的全貌：從分類（Las Vegas vs Monte Carlo）、經典案例（隨機化 QuickSort、水庫抽樣）、到數學分析工具（集中不等式）。
這些演算法不是學術玩具——資料庫排序、圖形渲染、機器學習、網路分析到處都在用。