概率与统计 · 蒙特卡洛方法

蒙特卡洛方法

用随机抽样估计一个数的方法:在单位正方形内独立、均匀地投N个点,落进某块区域的比例就估计它的面积,标准误差按1/√N缩小。投点,看π的估计怎样稳定下来,误差范围一路跟着。

蒙特卡洛方法与本页画面

蒙特卡洛方法用随机抽样估计一个确定的数。本页的数是面积:在单位正方形里均匀随机地投NN个点,其中HH个落进某块区域,H/NH/N就估计这块区域的面积aa。四分之一圆的面积是π/4\pi/4,所以4H/N4H/N估计π\pi;y=e−x2y = e^{-x^2}下方的区域把一个没有初等原函数的积分也变成同样的计数。下面的图跟着NN一直到一百万,画出估计值,以及它95%的时候应该落在的范围。

为什么命中的比例能估计面积

在面积为1的正方形里均匀分布的点,落进一块区域的概率就等于这块区域的面积。每个点都是一次独立的试验,机会都一样,所以由大数定律,命中的比例趋于aa。区域是什么形状无关紧要,只要能判断一个点在不在里面。

能准到哪一位

命中数服从二项分布,所以比例H/NH/N的标准差是a(1−a)/N\sqrt{a(1-a)/N}。典型误差按1/N1/\sqrt{N}缩小:点数乘10,误差约缩小10≈3.16\sqrt{10} \approx 3.16倍,要让它缩小到十分之一,大约要多投一百倍的点;一百万个点之后,π仍有约±0.003的不确定。判断准不准不需要知道真值:用观测到的比例p^=H/N\hat p = H/N代替aa,得到范围±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N},这是一个近似的95%置信区间,本页在命中和未命中都至少有十个时才给出。如果用同样的NN把整个实验重复很多次,大约二十个范围里有一个盖不住真值;下图蓝色的喇叭是每个NN各自的这个范围,不是整条路径都要待在里面的带子;而且一次实验的误差不是一路变小的,点多了也可能离真值稍远一点。稳定变小的是范围。

什么时候值得用

对一元的光滑函数,辛普森法这样的确定性办法(见数值积分)在同样的计算量下要准得多。蒙特卡洛方法的长处是它的速度1/N1/\sqrt{N}里的指数不随维数改变,而每边mm个点的网格在dd维里要mdm^d个点,所以在高维问题里它可能是更好的选择。它的短处在小目标上:标准误差和面积之比是(1−a)/(aN)\sqrt{(1-a)/(aN)},面积只有正方形百分之一的区域,要达到同样的相对精度需要多得多的点。

值得注意

  • 随机的点不会均匀铺开:几百个点里出现扎堆和空白是正常的。
  • 点由带编号种子的伪随机数生成,所以分享的链接会还原同样的点;投到一百万后再按投点,换下一个种子重投。

相关概念