算法介绍

蒙特克罗算法(Monte Carlo method)是以概率统计理论为指导的、通过随机抽样来解决复杂计算问题的方法。

蒙特卡罗是南欧小国家摩纳多的一个著名的赌城,因为赌博意味着概率,而蒙特卡罗算法就是大数定理的应用。

蒙特卡罗赌场

蒙特卡罗算法的现代起源是美国的曼哈顿原子弹计划S.M.乌拉姆(美国数学家)和冯·诺依曼为了计算中子在原子弹内的扩散和增殖情况,首先提出蒙特卡罗算法通过现代计算机模拟计算中子复杂的变化情况。

当时 S.M.乌拉姆(美国数学家)将中子在原子弹内的扩散和增殖问题等价为求解高维玻尔兹曼方程(高维偏微分方程),然后将求解高维玻尔兹曼方程(高维偏微分方程)又等价为转化成相应形式的随机问题,并通过计算模拟进行求解

求解高维玻尔兹曼方程(高维偏微分方程)非常复杂,可以通过蒙特卡罗抽样不断逼近真实解。

应用案例

求解圆周率 Π

通过在圆的最小外接矩形内随机生成采样点,分别统计采样点落在圆内的数量及圆外的数量,最终得出圆周率:

$\frac{Area of Circle}{Area of Square} = \frac{\pi r^2}{\left(2r\right)^2}=\frac\pi4$

求解圆周率

求解积分

积分就是求积分函数下面对应的面积,在统计范围内生成大量的采样点,并分别统计采样点落在积分函数上下的数量,得到积分数值

下面函数在 (1,1) 点的取值为1,所以整个红色区域在一个面积为1的正方形里面。在该正方形内部,产生大量随机点,可以计算出有多少点落在红色区域(判断条件 y < x2)。这个比重就是所要求的积分值。

求解积分

模拟随机过程

通过蒙特卡罗算法来模拟博彩过程:

赌徒和庄家对赌抛硬币,如果为正面,本轮赌徒赢,庄家付给赌徒1元,结果为反面,本轮赌徒输,赌徒付给庄家1元。赌徒有初始赌本10元,手上的钱一旦输光则退出赌局,如何来模拟这个博彩过程?

我们首先来分析一下这个过程,赌徒的博彩结果本质上依托于每次抛掷硬币的结果,每一轮博彩就是一个伯努利试验,赢的概率是p=0.5,博彩的过程就是由这一串伯努利试验构成的伯努利随机过程,每轮赌局中,如果赢则赌本增加1元,输则赌本减少1元。

当然了,如果对某一个特定的赌徒,一旦开始进入赌局,则最终由每轮赌局结果构成的序列就是唯一的。那么如果我们想观察整个博彩过程的整体特征,我们该怎么办?好办,还是使用之前讲过的蒙特卡罗方法,采用大量的样本,最终观察样本结果的整体特征。

我们为了说明问题,采用的样本数为赌徒数1000000个,轮数分别为轮数为100,1000,10000轮,也就是每个赌徒最多和庄家分别对赌100,1000,10000轮,如果在这个过程中输光了赌本,则提前退出,如果到100,1000,10000轮还有赌本,赌局也停止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import pandas as pd
import random

sample_list = []
person_num = 100000
round_num = 10000
for person in range(1, person_num + 1):
money = 10
for round in range(1, round_num + 1):
result = random.randint(0, 1)
if result == 1:
money = money + 1
elif result == 0:
money = money - 1
if money == 0:
break
sample_list.append([person, round, money])
sample_df = pd.DataFrame(sample_list, columns=['person', 'round', 'money'])
sample_df.set_index('person',inplace=True)

print("总轮数:{},总人数:{}".format(round_num,person_num))
print("输光赌本提前出局的人数:{}".format(person_num-len(sample_df[sample_df['round']==round_num])))
print("赌满全场且盈利的人数:{}".format(len(sample_df[sample_df['money']>10])))
print("赌满全场且亏损的人数:{}".format(len(sample_df[sample_df['money']<=10][sample_df['money']>0])))

运行结果:

1
2
3
4
总轮数:100,总人数:100000
输光赌本提前出局的人数:31148
赌满全场且盈利的人数:44458
赌满全场且亏损的人数:23923
1
2
3
4
总轮数:1000,总人数:100000
输光赌本提前出局的人数:75154
赌满全场且盈利的人数:23441
赌满全场且亏损的人数:1386
1
2
3
4
总轮数:10000,总人数:100000
输光赌本提前出局的人数:91902
赌满全场且盈利的人数:8060
赌满全场且亏损的人数:38

从结果中不难发现,这种和庄家1:1的对赌,随着轮数的增加,基本上都破产被收割了。换句话说,哪怕庄家不出千,输赢概率各半,赌的越久,基本上都是输光破产走人,原因是什么?原因是庄家的资金量是无穷的。

接受拒绝采样

例子:要求函数 $f(Z)$ 关于分布 $𝑝(𝑍|𝑋)$ 的期望,而期望的本质是求积分 ,而这个积分往往非常难求,可以根据分布 $𝑝(𝑍|𝑋)$ 采出 𝑁 个采样点, ,用样本均值来近似期望:

但如果分布 $𝑝(𝑍|𝑋)$ 非常复杂,很难根据分布进行采样,此时采用接受拒绝采样方法实现复杂概率分布的样本采样。

首先我们采用一个已知的简单的概率密度函数 $𝑔(𝑥)$ 和常数值 $𝐶$,保证$C∗𝑔(𝑥)≥𝑝(𝑥)$,从分布 $𝑔(𝑥)$ 中获取一个采样样本 $𝑌$,也就是从累积分布函数中按照 $[0,1]$ 均匀分布采样一个概率,然后取得一个样本值。

累积分布函数

从 $[0,1]$ 均匀分布中获取一个采样成本 $𝑈$,如果 ,就接受这个采样值 $𝑌$,否则拒绝该采样,不断重复该过程,最终获得服从 $𝑝(𝑥)$ 分布的样本值。 也就是猜出的样本有 $𝑈$ 的概率被接受,有 $1-𝑈$ 的概率被拒绝。

接受拒绝采样

总结

  1. 蒙特卡洛方法的思想是使用随机数来进行场景的模拟或者过程的仿真,通过不断增加采样点,逐渐逼近真实解。

  2. 其在在金融工程学,宏观经济学,计算物理学等领域应用广泛,主要应用包括但不局限于近似计算不规则面积/体积/积分、模拟随机过程、结合接受-拒绝采样来对分布的未知参数进行统计推断。

  3. 蒙特卡洛检测的优点能够简单快速地快速求解复杂问题,结合计算机大量样本的采样实验,以频率逼近概率。

参考: