蒙特卡洛积分

在高维的数值积分中，有一类比较特殊的方法，通过随机选点替代均匀网格，即蒙特卡洛方法。

蒙特卡洛积分¶

对连续函数 \(f(x)\)，考虑积分

\[ I(f) = \int_\Omega f(x)\mathrm{d}x = Vf(\bar{x}), \]

其中 \(x\in\Omega\subset\mathbb{R}^d\)，且 \(|\Omega|=V\)。

定义(蒙特卡洛积分)

对于上述积分，其蒙特卡洛近似估计为

\[ I_n(f)= \frac{V}{n}\sum_{i=1}^nf(X_i), \quad X_i\sim U(\Omega), \quad i=1,\cdots,n, \]

其中 \(X_i\) 是服从 \(\Omega\) 上均匀分布的随机变量。

该方法直观上和低维积分很相似，区别就在于用随机变量组成的样本代替了均匀网格。下面对其误差进行分析：

记 \(\varepsilon(f) = I(f) - I_n(f) = \frac{V}{n}\sum_{i=1}^n (f(X_i) - f(\bar{x}))\) ，是 \(n\) 个独立同分布的变量 \(f(X_i)- f(\bar{x})\) 的均值。根据中心极限定理， \(n\to\infty\) 时有

\[\varepsilon(f) \sim \mathcal{N}(0,\frac{\sigma^2}{n}),\]

其中，\(\sigma\)是采样带来的方差，记\(\displaystyle \sigma^2 =\text{Var}(f(X_i) - f(\bar{x}))\)。以标准差来刻画误差，当 \(n\) 足够大时，有

\[ \delta(\varepsilon) = \sqrt{\text{Var}(\varepsilon)}= \frac{V\sigma}{\sqrt{n}}. \]

可以看到误差的逼近精度与样本所在的空间维度 \(d\) 无关，仅与样本个数 \(n\) 有关，且误差阶固定为 \(O(n^{-\frac{1}{2}})\) ，这也是为什么蒙特卡洛方法经常被用来尝试克服「维度灾难」；当然 \(d\) 有可能出现在 \(V\) 中，比如 \(\Omega = [-1,\ 1]^d\)，则 \(V=2^d\) 。所以到目前为止，这是一个可能的解决方案，但维度灾难仍未被真正解决。

例: \(\ \Omega = [0,1]^3,\quad f(x,y,z) = x+y+z.\)

\[\begin{aligned}I(f) &= \frac{3}{2} = f(\frac{1}{2}, \frac{1}{2},\frac{1}{2}),\\ I_n(f) &= \frac{1}{n}\sum_{i=1}^n(X_i+Y_i+Z_i), \quad X_i,Y_i,Z_i\sim U(0,1).\end{aligned} \]

记 \(D_i =X_i+Y_i+Z_i\)，则其概率密度函数为

\[ P_D(x) = \left\{\begin{aligned}&\frac{1}{2}x^2,& 0\leq x\leq 1,\\ &\frac{3}{4}-(x-\frac{3}{2})^2,& 1<x\leq 2,\\&\frac{1}{2}(x-3)^2, &2<x\leq 3. \end{aligned}\right. \]

所以 \(\sigma = \frac{81}{320}\)，蒙特卡洛积分的误差为 \(\delta(\varepsilon) = \frac{81}{320\sqrt{n}}\).