Monte Carlo Methods

🔥 Vibe Prompt

"Estimate π by throwing darts. Then estimate ∫∫(x²+y²<1) using Monte Carlo. Show convergence."

import random, math

def estimate_pi(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

# Convergence
for n in [100, 1000, 10000, 100000, 1000000]:
    pi_est = estimate_pi(n)
    error = abs(pi_est - math.pi) / math.pi * 100
    print(f"n={n:>7}: π ≈ {pi_est:.6f} (error: {error:.4f}%)")

# Expected value estimation
import numpy as np

def mc_integral(n, func, low=0, high=1):
    xs = [random.uniform(low, high) for _ in range(n)]
    return (high - low) * sum(func(x) for x in xs) / n

result = mc_integral(100000, lambda x: x**2)
print(f"\n∫₀¹ x² dx = {result:.4f} (exact: {1/3:.4f})")

## Randomized Algorithms Course Complete! 🎉
# - ✅ Randomized QuickSort
# - ✅ Randomized Hash
# - ✅ Quickselect
# - ✅ Reservoir Sampling
# - ✅ Monte Carlo Methods

Convergence Rate

MC error ∝ 1/√n. To halve error, quadruple n.

Applications

Financial options pricing
Physical simulations
Bayesian inference
Reinforcement learning

Key Points

Understand the core concepts thoroughly
Practice with hands-on code examples
Apply knowledge to real-world problems
Review and reinforce through exercises

Further Learning

Official documentation
Open source projects on GitHub
Community forums and discussions
Related courses and tutorials

用隨機丟骰子來計算圓周率？

想像你在一個 2×2 的正方形內隨機丟骰子。如果骰子落在內切圓（半徑 1）內就計數。

正方形面積 = 4
圓面積 = π × 1² = π
骰子落在圓內的機率 = π/4
所以 π ≈ 4 × (落人圓內的次數 / 總次數)

這就是蒙地卡羅方法最經典的範例——用隨機抽樣來計算確定性的數學問題。

import random, math

def estimate_pi(n):
    inside = sum(1 for _ in range(n) if random.random()**2 + random.random()**2 <= 1)
    return 4 * inside / n

for n in [100, 1000, 10000, 100000, 1000000, 10000000]:
    pi_est = estimate_pi(n)
    print(f"n={n:>8}: π≈{pi_est:.6f} (誤差 {abs(pi_est-math.pi)/math.pi*100:.4f}%)")

# 輸出：
# n=     100: π≈3.200000 (誤差 1.8592%)
# n=    1000: π≈3.144000 (誤差 0.0761%)
# n=   10000: π≈3.141600 (誤差 0.0002%)
# n=  100000: π≈3.141580 (誤差 0.0004%)
# n= 1000000: π≈3.141592 (誤差 0.0000%)

注意到誤差隨 n 增加而減少的速度嗎？誤差約等於 1/√n。要讓誤差減半，你需要 4 倍的樣本數——這是蒙地卡羅方法的特性，也是它的限制。

為什麼蒙地卡羅在高維度問題上無可取代？

當維度 > 4 時，傳統的數值積分方法（梯形法、Simpson 法）會因為維度詛咒 (Curse of Dimensionality) 而失效。

| 方法 | 誤差收斂速度 | 維度影響 | |:----:|:------------:|:--------:| | 梯形法 | O(1/n²) | 每增一維，點數指數成長 | | 蒙地卡羅 | O(1/√n) | 與維度無關！ |

這意味著對於 10 維的積分問題，蒙地卡羅比梯形法快上數百萬倍。這也是為什麼金融工程、物理模擬、貝氏統計幾乎完全依賴蒙地卡羅方法的原因。

課程總結

隨機化演算法的核心哲學：與其對抗隨機性，不如利用它。