Monte Carlo 方法

Monte Carlo 積分

import random, math

def mc_integral(f, a, b, n=100000):
    total = 0
    for _ in range(n):
        x = random.uniform(a, b)
        total += f(x)
    return (b - a) * total / n

# 計算 ∫₀¹ x² dx = 1/3
f = lambda x: x*x
result = mc_integral(f, 0, 1)
print(f"Monte Carlo: {result:.6f} (理論值: {1/3:.6f})")

# 計算複雜區域面積
import matplotlib.pyplot as plt

def mc_area(n=100000):
    inside = 0
    for _ in range(n):
        x, y = random.random()*2-1, random.random()*2-1
        if x**3 + y**4 < 1:
            inside += 1
    return 4 * inside / n

area = mc_area()
print(f"x³ + y⁴ < 1 的面積: {area:.4f}")

Vibe Prompt

「用 Monte Carlo 計算複雜函數的積分，並畫出收斂過程（誤差隨樣本數的變化）。」

深入理解：Monte Carlo 方法的誤差分析

收斂速率

Monte Carlo 的誤差收斂速率是 $O(1/\sqrt{n})$，與維度無關！

| 方法 | 誤差收斂 | 維度影響 | |------|:--------:|:--------:| | 矩形法（數值積分） | $O(1/n)$ | 指數級變差 | | 梯形法 | $O(1/n^2)$ | 指數級變差 | | Monte Carlo | $O(1/\sqrt{n})$ | 無關 |

這就是為什麼高維度積分（如 > 4 維）幾乎只能靠 Monte Carlo！

誤差視覺化

import matplotlib.pyplot as plt
import numpy as np

# 觀察誤差隨樣本數的變化
ns = [100, 500, 1000, 5000, 10000, 50000, 100000]
errors = []

for n in ns:
    result = mc_integral(lambda x: x*x, 0, 1, n)
    errors.append(abs(result - 1/3))

plt.figure(figsize=(10, 5))
plt.loglog(ns, errors, 'o-', label='實際誤差')
plt.loglog(ns, [1/np.sqrt(n) for n in ns], '--', label='$O(1/\sqrt{n})$')
plt.xlabel('樣本數 n')
plt.ylabel('誤差')
plt.title('Monte Carlo 誤差收斂')
plt.legend()
plt.grid(True)
plt.show()

變異數減少技巧

重要性採樣：針對高貢獻區域增加採樣
分層採樣：將區域分層，每層均勻採樣
對偶變數：使用相關變數減少變異數
控制變量：用已知積分的輔助函數校正

關鍵要點

✅ Monte Carlo 積分的誤差收斂為 $O(1/\sqrt{n})$，與維度無關
✅ 高維度積分（> 4D）幾乎只能靠 Monte Carlo
✅ MCMC（馬可夫鏈蒙地卡羅）用於從複雜分布中抽樣
✅ 變異數減少技巧可大幅提升 MC 效率
✅ MC 方法在 Bayesian 推論、物理模擬、金融工程中廣泛應用

實作範例

基礎範例

常見錯誤

程式碼範例

Monte Carlo 方法為什麼無所不在？

從電腦圖學到物理模擬、從金融定價到機器學習——Monte Carlo 方法可以說是應用最廣泛的隨機化演算法。

Monte Carlo 的核心思想

如果你有一個問題無法精確求解（太複雜、太昂貴或根本不知道公式），那就用隨機抽樣來估計答案。抽樣越多，估計越準確。

$$誤差 \propto \frac{1}{\sqrt{n}}$$

意思是如果你想讓誤差縮小到 1/10，你需要 100 倍的樣本數。這聽起來很多，但比起某些問題的指數級複雜度，這已經很便宜了。

在真實世界的應用

| 領域 | 應用 | 爲什麼用 Monte Carlo | |:----|:----|:-------------------| | 電腦圖學 | 光線追蹤（Ray Tracing） | 光子在場景中的路徑太複雜無法解析 | | 金融工程 | 選擇權定價 | 市場價格變動是隨機過程 | | 物理模擬 | 粒子物理、流體力學 | 系統維度太高無法離散化 | | 機器學習 | MCMC 採樣、貝氏推論 | 後驗分布沒有封閉解 | | 遊戲 AI | 蒙地卡羅樹搜索（MCTS） | 搜尋空間太大無法窮舉 |

下一章預告：最小割與 Contraction

Monte Carlo 方法的「隨機抽樣估計」和下一章的「隨機化 Contraction 演算法」有什麼不同？Contraction 用隨機化來簡化問題本身，而不是估計答案——這是另一種完全不同的思路。