[图形学]蒙特卡洛积分方法介绍及其方差计算

一、简介

本文介绍了蒙特卡洛积分算法的基本原理和其误差计算。

二、蒙特卡洛积分介绍

1. 介绍

蒙特卡洛积分算法是一种数值积分算法，用于对复杂函数进行积分。
例如，对于目标积分函数：
$${\int }_a^{b}f(x)\mathrm{d}\mathrm{x}\text{\hspace{1em}(1)}$$
其中$f(x)$很复杂，无法找到解析解。我们可以在$f(x)$的定义域$[a,b]$上按照任意的概率密度函数$p(x)$进行采样。并统计采样的随机变量的样本期望：
$$F_N=\frac{1}{N}\sum _{i=1}^N\frac{f(x_i)}{p(x_i)}\text{\hspace{1em}(2)}$$
可以保证：
$$E(F_N)={\int }_a^{b}f(x)\mathrm{d}\mathrm{x}\text{\hspace{1em}(3)}$$

2. 证明

下面证明公式(3)的正确性：
$$\begin{gathered} E(F_N)=E(\frac{1}{N}\sum _{i=1}^N\frac{f(x_i)}{p(x_i)}) \\ =\frac{1}{N}\sum _{i=1}^{i=N}E(\frac{f(x_i)}{p(x_i)}) \end{gathered}$$
我们令$g(x)=\frac{f(x)}{p(x)}$，那么
$$\begin{gathered} E(F_N)=\frac{1}{N}\sum _{i=1}^{i=N}E(g(x)) \\ =\frac{1}{N}\ast N\ast {\int }_{}^{}g(x)\ast p(x)\mathrm{d}\mathrm{x} \\ =\int g(x)\ast p(x)\mathrm{d}x \\ =\int f(x)\mathrm{d}\mathrm{x}\text{\hspace{1em}(4)} \end{gathered}$$
求证得证。

三、蒙特卡洛积分方差

蒙特卡洛积分算法的收敛程度可以适用其方差（标准差）表示。若其方差收敛速度很快，说明该算法可以适用较少的采样值，得到较高的积分精度，反则反之。下面对蒙特卡积分算法的方差和标准差进行计算。
下面计算蒙特卡洛积分算法的方差：
$${\delta }^2(F_N)={\delta }^2(\frac{1}{N}\ast \sum _{i=1}^{1=N}(\frac{f(x)}{p(x)}))\text{\hspace{1em}(5)}$$
根据方差的性质：
$$\begin{gathered} {\delta }^2(c\ast X)=c^2\ast {\delta }^2(X) \\ {\delta }^2(a\ast X+b\ast Y)=a^2{\delta }^2(X)+b^2{\delta }^2(Y)+2ab\ast COV(X,Y)\text{\hspace{1em}(6)} \end{gathered}$$
又因为采样的随机变量$x_i$相互独立，因此：
$$\begin{gathered} {\delta }^2(F_N)={\delta }^2(\frac{1}{N}\ast \sum _{i=1}^{1=N}(\frac{f(x)}{p(x)})) \\ =\frac{1}{N^2}\ast \sum _{i=1}^{i=N}{\delta }^2(\frac{f(x)}{p(x)}) \\ =\frac{1}{N}\ast {\delta }^2(\frac{f(x)}{p(x)})\text{\hspace{1em}(7)} \end{gathered}$$
工具公式(7)可知，蒙特卡罗积分方法的方差与采样数$N$成反比，与${\delta }^2(\frac{f(x)}{p(x)})$成正比。
为了得到更为准确的结果，一方面我们可以增加采样数，即增大$N$。
另一方面我们可以尽可能地令${\delta }^2(\frac{f(x)}{p(x)})$小一些，由于$f(x)$是我们待求的积分函数，无法进行修改，因此我们可以寻找一个概率密度函数$p(x)$，使得$\frac{f(x)}{p(x)}$的方差尽可能的小。

四、蒙特卡洛积分与差分积分

蒙特卡洛积分和差分积分都是数值积分方法。
与差分积分方法相比，蒙特卡洛方法的计算复杂度与维度无关。它通过随机采样的方式估计积分值，即使维度增加，样本点的生成和积分估计的计算量并不会指数级增长。这意味着蒙特卡洛方法在高维问题中仍然保持高效，具有稳定的性能。
而在差分积分方法中，每增加一个维度，划分的区域数量会大幅增加，使得差分积分方法的计算复杂度呈指数级增长。