蒙特卡洛法
May 25, 2021
蒙特卡洛(MonteCarlo)是一大类随机算法(RandomizedAlgorithms)的总称，它们通过随机样本来估算真实值。
估计圆周率 #
假设有一个半径为1，圆心在原点的圆，我们知道它的面积是$\pi$。现在我们随机在$x\in[-1,1], y\in[-1,1]$上随机取一个点，我们知道这个点落在圆内的概率为圆与正方形面积之比：
$$ p = \frac{\pi}{4} $$
假设我们随机选取了n个点，我们可以使用下面的公式判断哪些点位于圆内，假设有m个。
$$ x^2 + y^2 < 1 $$
显然，我们知道m的数学期望是
$$ E[M] = \frac{\pi n}{4} $$
当n很大时, m近似于数学期望，因此有
近似求定积分 #
蒙特卡洛求积分的本质是利用随机模拟估计一个随机变量的期望。
假设我们想求定积分:
$$ \int_{a}^{b} f(x) \mathrm{d} x $$
我们可以把它转换成某个随机变量的数学期望，具体如下：
设随机变量$X \sim U[a, b]$，即服从均匀分布，X具有概率密度$p(x)=\frac{1}{b-a}$，那么就有:
$$ E[f(X)] =\int_{a}^{b} p(x)f(x) \mathrm{d} x = \frac{1}{b-a}\int_{a}^{b} f(x) \mathrm{d} x $$
在统计学中，我们知道期望是可以估计的，我们随机取N个$f(x)$的样本，这些样本的平均值可以作为所求期望的近似，即：
$$ E[f(x)] = \frac{\sum_1^Nf(x_i)}{N} = \frac{1}{b-a}\int_{a}^{b} f(x) \mathrm{d} x $$
那么就有：
$$ \int_{a}^{b} f(x) \mathrm{d} x = (b-a)\frac{\sum_1^Nf(x_i)}{N} $$