蒙特卡洛方法模拟

定义：

随机模拟方法或统计试验方法。它是通过不断产生随机数序列来模拟过程。自然界中有的过程本身就是随机的过程，物理现象中如粒子的衰变过程、粒子在介质中的输运过程...等。当然蒙特卡洛方法也可以借助概率模型来解决不直接具有随机性的确定性问题。

应用：

（1）直接蒙特卡洛模拟。它采用随机数序列来模拟复杂随机过程的效应。
（2）蒙特卡洛积分。这是利用随机数序列计算积分的方法。积分维数越高，该方法的积分效率就越高。
（3）Metropolis蒙特卡洛模拟。这种模拟是以所谓“马尔科夫”（Markov）链的形式产生系统的分布序列。该方法可以使我们能够研究经典和量子多粒子系统的问题。

基本思想：

蒙特卡洛方法可以人为地构造出一个合适的概率模型，依照该模型进行大量的统计实验，使它的某些统计参量正好是待求问题的解。这也就是所谓的间接蒙特卡洛方法。

巴夫昂(Buffon)投针实验

该试验方案是：在平滑桌面上划一组相距为$s$的平行线，向此桌面随意地投掷长度$l=s$的细针，那么从针与平行线相交的概率就可以得到$\pi$的数值。设针与平行线的垂直方向的夹角为$\alpha$，那么针在与平行线垂直的方向上投影的长度为$l\cdot|cos\alpha|$。对于确定的$\alpha$夹角，细针与平行线相交的概率为投影长度与平行线间距之比，即$l\cdot|cos\alpha|/s=|cos\alpha|$。由于$\alpha$是在$[0,\pi]$区间均匀分布的，所以$|cos\alpha|$的平均值为

$\frac{1}{\pi}\int_{0}{\pi}|cos\alpha|d\alpha=\frac{2}{\pi}$

假如在N次投针中，有M次和平行线相交。当N充分大时，相交的频数M/N就近似为细针与平行线相交的概率。所以，可以得到：

$\pi\approx\frac{2N}{M}$

结论：Monte-Carlo算法泛指一类算法。在这些算法中，要求解的问题是某随机事件的概率或某随机变量的期望。这时，通过“实验”方法，用频率代替概率或得到随机变量的某些数字特征，以此作为问题的解。

伯努利大数定理：

设$M$是$n$次独立试验中事件$A$发生的次数，$p$是事件$A$在每次试验中发生的概率，则对任意的正数$\epsilon$，

$lim_{n\rightarrow \infty}P(|\frac{\mu}{n}-p|<\epsilon)=1$

伯努利大数定律说明，当试验次数$n$ 很大时，事件$A$发生的频率与概率有较大判别的可能性很小，即

$lim_{n\rightarrow \infty}P(|\frac{\mu}{n}-p|\geqslant\epsilon)=0$

如果将“投掷一次飞针并与平行线相交”作为事件，那么飞针与平行线垂直方向的投影长度除以平行线间距在数学上等价于这个事件发生的概率。为了估计这个概率，我们用多次重复实验的方法，得到事件发生的频率 M/n，以此频率估计概率，从而得到问题的解。伯努利大数定理定理就保证了Monte-Carlo算法虽然不能保证解一定是准确和正确，但并不是“撞大运”，其正确性和准确性依赖概率论，有严格的数学基础，并且通过数学分析手段对实验加以控制，可以将误差和错误率降至可容忍范围。

上述投针法得到试验结果的效率和精度都很差。经过n次投针后得到$\pi$值（与平行线相交的概率）的精度。设$p=\frac{2}{\pi}$，那么针与平行线相交的次数应满足二项式分布（每一次投掷只会有相交与不相交两种情况）。其期望值为$np$，方差应为$np(1-p)$。因而$\frac{2}{\pi}$的方差为$p(1-p)/n$，标准误差为$\sqrt{\frac{p(1-p)}{n}}$。

说明：$D(X=M)=np(1-p)$，又因为$\frac{2}{\pi}\approx\frac{M}{n}$，所以$D(\frac{2}{\pi})=p(1-p)/n$。

$D(aX)=a^{2}D(X)$

将$p=\pi/2$的标准误差改写为$\pi$的标准误差$2.37/\sqrt{n}$。这意味着试验所得的$\pi$值的不确定性的范围如下：

对100次投针为，0.2374
对10,000次投针为，0.0237
对1,000,000次投针为，0.0024。
显然用这种方法比用其它方法计算$\pi$ 值所引起的不确定范围要大得多。

蒙特卡洛方法的基本思想：
当问题可以抽象为某个确定的数学问题时，应当首先建立一个恰当的概率模型，即确定某个随机事件A或随机变量X，使得待求的解等于随机事件出现的概率或随机变量的数学期望值。然后进行模拟实验，即重复多次地模拟随机事件A或随机变量X。最后对随机实验结果进行统计平均，求出A出现的频数或X的平均值作为问题的近似解。这种方法也叫做间接蒙特卡洛模拟。

适用于Monte-Carlo算法的问题，比较常见的有两类。一类是问题的解等价于某事件概率，如上述求不规则图形面积的问题；另一类是判定问题，即判定某个命题是否为真，如主元素存在性判定和素数测试问题。

把随机算法分成两类：

• 蒙特卡罗算法：采样越多，越近似最优解；
• 拉斯维加斯算法：采样越多，越有机会找到最优解；

举个例子，假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法——尽量找好的，但不保证是最好的。

而拉斯维加斯算法，则是另一种情况。假如有一把锁，给我100把钥匙，只有1把是对的。于是我每次随机拿1把钥匙去试，打不开就再换1把。我试的次数越多，打开（最优解）的机会就越大，但在打开之前，那些错的钥匙都是没有用的。这个试钥匙的算法，就是拉斯维加斯的——尽量找最好的，但不保证能找到。