Monte Carlo Algorithms

蒙特卡洛算法是一大类随机算法，通过随机样本来估算真实值。

近似求 \(π\)

在 \(xOy\) 坐标系中有单位圆和正方形数域 \(\{(x, y) ∣ x ∈ [-1, 1], y ∈ [-1, 1]\}\) 。在正方形数域中随机取一个点，落在单位圆的概率为 \(\frac{π}{4}\) 。那么，随机取 \(m\) 个点 \((x, y) ∈ \{⋅ ∣ x ∈ [-1, 1], y ∈ [-1, 1]\}\) ，满足 \(x ^ 2 + y ^ 2 ≤ 1\) 的点有 \(M\) 个。当 \(m → ∞\) 时，\(\frac{4M}{m} → π\) 。

示例代码：

import random

n = int(input(">"))
m = 0

for _ in range(n) :
    x = random.uniform(-1, 1)
    y = random.uniform(-1, 1)
    if x ** 2 + y ** 2 <= 1 :
        m += 1
        
print(4 * m / n)

以上思路也可以用来估计阴影面积。

近似求积分

一元积分

Task: Given a univariate function \(f(x)\), calculate

1. Draw \(n\) samples from \([a, b]\) uniformly at random; denote them by \(x_1, ⋯, x_n\).

2. Calculate

3. Return \(Q_n\) as an approximation to the integral

Theory: Law of large numbers guarantees \(Q_n → I\) as \(n → ∞\).

多元积分

Task: Given a multivariate function \(f(𝐱)\), calculate

1. Draw \(n\) samples from set \(\Omega\) uniformly at random; denote them by \(𝐱_1, ⋯, 𝐱_n\).

2. Calculate

3. Calculate

4. Return \(Q_n\) as an approximation to the integral

集合 \(\Omega\) 应当是简单的可以用体积公式算出来的形状。

近似求期望

• Let \(\mathbf{X}\) be a \(d\)-dimensional random vector.

• Let \(p(\mathbf{x})\) be a probability density function (PDF).

• Property: \(∫_{ℝ^d} p(𝐱)\, d𝐱 = 1.\)

• E.g., PDF of uniform distribution is \(p(x) = \frac{1}{t}, \quad x \in [0, t].\)

• E.g., PDF of univariate Gaussian is \(p(x) = \frac{1}{\sigma \sqrt{2\pi}} \exp\!\left(-\frac{(x - μ)^2}{2σ^2}\right).\)

• Let \(f(\mathbf{x})\) be any function of vector variable.

• Expectation:

直接求这个期望并不容易，所以用蒙特卡洛近似求期望：

Task: Estimate the expectation

1. Draw \(n\) random samples from the probability distribution \(p(𝐱)\); denote them by \(𝐱_1, ⋯, 𝐱_n\).

2. Calculate

3. Return \(Q_n\) as an approximation to \(𝔼_{𝐗 ∼ p}[f(𝐗)]\).