Hey! 这里是Lindy:) Hope you guys are doing well!
今天想记录的概念叫做 蒙特·卡罗 方法，是今年在cs课上老师做的扩展延伸。其实我在初次接触这个概念时觉得很新奇，因为作为一个编程菜鸟，在python里试图计算时（这里指数学运算，也就是说output是以float,或integer的形式来表示），一般依赖于python的math module来做出确定的计算。但是蒙特卡罗方法（以下简称为MC method）却带给我了完全不同的思路。
话不多说，先上从万能的Wikipedia复制来的概念：
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle.
简单的来说就是使用纯粹概率统计的方法，在有一定数量的随机数的统计基础上计算出有高精确度的数据结果。
emmm...懂了么？没懂。
没关系，我们来看一个例子。
如果我们想要获得 π 的精确数值（I know engineers use 3 as approximation for pi :) we are not doing that here)，最直接的方法是引入 python内置的math module 里储存的π，如下：
1 import math
2 print(math.pi)
这个方法的output是 3.141592653589793。但是需要提及的是这个数字是提前被储存为一个常数，所以这个方法严格的来说不算是计算，而是调用。
但是如果我们不使用math module呢？你可能会说我们也可以用 Taylor Polynomial 来近似π啊。泰勒公式使用如下
$\mathrm{\pi}=4\cdot \mathrm{arc}\tan \left( 1 \right) =4\cdot \sum_{\mathrm{i}=0}^{\mathrm{N}}{\frac{\left( -1 \right) ^{\mathrm{i}-1}}{\left( 2\mathrm{i}-1 \right) ^{-1}}}$
以上公式可以用python表达如下：
1 sum = 0
2 for i in range(1,100000):
3 sum += ((-1)**(i-1))*((2*i-1)**-1)
4 sum *= 4
5 print(sum)
这个方法的output是 3.1416026536897204，可以看到，在循环了 99999次后这个结果开始接近了math module 储存的π，但在小数点四位后便开始偏离了π的真实数值。
那还有什么方法呢？好了我要点题了，我们要用 Monte Carlos Method 了。
根据定义，MC method是根据在概率统计学上，所以需要一定的随机数字作为基础量来计算概率密度。所以第一步我们要制作很多随机数，这一步需要用到python的random module：
1 import random
2 x , y = random.random() , random.random()
*random.random() 会随机产生一个在 0-1之间的浮点数。
在进行下一步之前，我们需要简要复习一下π的定义。提起π，我们都会很自然的把这个数字跟圆的周长和面积进行联系。在这里，为了把概率密度视觉化，我们要使用面积的概念：A = πR2。下图是一个边长为1的正方形，内切1/4的半径为1的圆。
那如果我们在以上图片平面内随机选一点的话，这一点落入圆的面积范围的概率是多少呢？答案是$\mathrm{P}\left( \mathrm{x} \right) =\frac{\mathrm{A}_{\mathrm{circle}}}{\mathrm{A}_{\mathrm{square}}}=\frac{\frac{\mathrm{\pi}}{4}}{1}=\frac{\mathrm{\pi}}{4}$。利用这个概念，如果我们能够计算点落入圆区域的概率(并乘以4)，我们就能估算 π 的值。为了实现以上概念，我们要使用类似于以上 Talyor Polynomial 的循环写法（这里为了模仿这个循环写法作精度对比，我用了for loop，但是这里while loop也可以实现同样的效果):
1 import random
2
3 total, total_random = 0, 99999 # 初始化
4
5 for i in range(total_random):
6 # 生成随机数
7 x , y = random.random() , random.random()
8 # 计算点是否落入圆的范围
9 if (x**2 + y**2)**(1/2)<1:
10 total += 1
11 # 计算pi的值
12 pi = 4*(total/total_random)
13 print(pi)
因为概率统计计算的不稳定性，我重复跑了5遍同样的代码，但生出的结果却大不一样。在平均了100次代码产出结果后，输出结果为 3.141013010130101。可见，这个计算方法在小数点后3位后便偏离了 π的精确数值。在把随机数量提升到100000后，精确数字增加到了小数点后4位。但是比起泰勒公式的精确计算，因为统计学的不确定性，MC method的精确度确有欠缺。MC Method 的显著优点是实现度高，没有针对数学理解的要求，而且可视度高，理解上更容易一些。
用同样的方法，我们可以用类似的概率面积估算来计算函数的积分。这是因为 Integral = Area under the Curve, 所以我们可以用类似的面积计算方式来解决这个问题。因为面积是一个有限的量，所以在这里我们计算的是definite integral。
模仿以上π的MC算法，我们可以试着来用python实现$\int_0^1{\mathrm{x}^2}$ 注意这里我们可以继续使用random.random()，因为为了代码的简洁性，我假设了这个积分的函数的local max在1以内
1 total, total_random = 0, 999999 #初始化
2
3 def f(x): #定义需要计算的积分函数，在这个例子里是x^2
4 return x**2
5
6 for i in range(total_random): #产生大量随机数
7 x , y = random.random(), random.random()
8 if y < f(x): #如果随机点在函数下方，则计入总数
9 total += 1
10
11 integral = (total/total_random) #计算概率密度
12 print(integral)
代码运行结果为0.3331783331783332，和理论结果（1/3）还是很相似的。这也证明了MC Method在积分计算上的可行性。以上代码模仿了初始的π的MC算法，我们可以看到，这个例子的变形主要是在函数的定义上；我们重新写了一个函数，定义了需要返回的函数的具体值。如此，这个函数才能在之后的随机数计算是被用于归类（这里的归类是指看点是否落在函数下方）。
但是以上代码只适用于$\int_0^1{\mathrm{x}^2}$这个特定的例子，如果我们要计算更复杂的函数，或者不同界限的函数，这些代码将不再适用（应该说怎么会能够适用呢：）连函数可能都不一样了。）另外代码的计算过程并没有被实际的表达出来，也就是说即使通过代码我们可以成功的获得积分的最终计算值，可仅仅通过这个值我们也没有办法获得关于这个函数的其他信息，例如形状，最大，最小值等等。
所以为了提升以上代码的实用性，我们可以利用python常用的画图模块，matplotlib,以及数据处理模块，numpy进行以下处理 (具体代码使用请看注释，文中将不再对代码作用进行解释)：
1 import random
2 import math
3 import numpy as np
4 import matplotlib.pyplot as plt
5
6 def f(x):
7 return np.sin(x)
8
9 def definite_integral_calculation(f,a,b,N):
10 '''
11 Approximate the definite integral value of the function, f, with the left bound a
12 and right bound b, using a total number of N points
13
14 Parameters:
15 f: a defined function that is being approximated
16 a: left bound of the function
17 b: right bound of the function
18 N: the total number of random points
19 '''
20 # 首先，我们为了确保MC Method的正确性，要现在这里用Numpy写出准确函数的图像表达。
21 act_x = np.arange(a, b, 0.01) #以0.01个单位为间隔，产出array
22 act_y = f(act_x) #计算以上array相应的函数值
23
24 #我们注意到，在计算积分时，函数不一定总是落在1的下方。而且在函数同时有
25 #正负值时，我们也要对此进行针对性的处理。所以我们要对极值做出以下操作：
26 f_max = max(act_y)
27 f_min = min(act_y)
28
29 if f_min <= 0:
30 negative = True
31 else:
32 negative = False
33
34 #现在我们要生成相应的随机数并进行分类，看是否落进函数形成的区域
35 x_rand = a + np.random.random(N)*(b-a) #生成符合函数范围的随机数
36 y_rand = 0 + np.random.random(N)*f_max
37
38 ind_in_pos = np.where(y_rand < f(x_rand)) #进行条件判断，看点是否落入函数范围内
39 ind_out_pos = np.where(y_rand >= f(x_rand))
40
41 #我们可以把以上的代码用matplotlib来具现化
42 plt.plot(act_x, act_y, color='red') #准确的函数用红色的光滑曲线来表示
43 plt.scatter(x_rand[ind_in_pos], y_rand[ind_in_pos],color ='green') #落入范围的随机点用绿色点来表示
44 plt.scatter(x_rand[ind_out_pos], y_rand[ind_out_pos],color ='yellow') #未落入范围的随机点用蓝色来表示
45
46 #同时我们也要考虑到同时有正负值的情况
47 if negative:
48 y_rand_neg = 0 + np.random.random(N)*f_min #同上，生成负的随机数
49
50 ind_in_neg = np.where(y_rand_neg > f(x_rand)) #同上，条件判断
51 ind_out_neg = np.where(y_rand_neg <= f(x_rand))
52
53 plt.scatter(x_rand[ind_in_neg], y_rand_neg[ind_in_neg],color ='green') #同上，根据分类画出随机点
54 plt.scatter(x_rand[ind_out_neg], y_rand_neg[ind_out_neg],color ='yellow')
55
56 #最后，我们要计算并输出函数相关的计算结果
57 positive_area = f_max*(b-a) #计算正的总面积
58 if negative:
59 negative_area = f_min*(b-a) #计算负的总面积
60 area = (len(ind_in_pos[0])/N)*positive_area+(len(ind_in_neg[0])/N)*negative_area #利用概率计算复合面积
61 else:
62 area = (len(ind_in_pos[0])/N)*positive_area #如果只有正数，则计算正的面积
63
64 #输出结果
65 print(f'The value of definite integral calculation is {area}')
66 print(f'The approximated maximum is {f_max}')
67 print(f'The approximated minimum is {f_min}')
68
69
70 if __name__ == '__main__':
71 definite_integral_calculation(f,-math.pi,math.pi*0.5,99999)
以上代码使用MC Method计算了$\int_{-\mathrm{\pi}}^{\frac{\mathrm{\pi}}{2}}{\sin \left( \mathrm{x} \right) \,\,\mathrm{dx}}$的具体数值，并用matplotlib具现化。首先我们先来看看打印出来的图像是否符合我们预期：
显然，sine 波形的形状已经被绿色和黄色勾勒了出来，符合红色波形的预计。而代码的具体输出结果
- The value of definite integral calculation is -0.9978134302969512
- The approximated maximum is 0.9999971463877178
- The approximated minimum is -0.9999996829318346
也在数学的角度上符合了我们的预判（sine的最大值为1，最小值为-1，$\int_{-\mathrm{\pi}}^{\frac{\mathrm{\pi}}{2}}{\sin \left( \mathrm{x} \right) \,\,\mathrm{dx}}$的结果为-1）。到此，在保留一定结果精度的情况下，我们可以判断在积分计算方面，Monte Carlos Method是足够准确的。
最后，我们还是要指出最后这个方程的几个使用时的注意事项：
- 在计算积分时，我们假设了这个函数是连续的，也就说如果在某一点方程会出现不平滑过渡的状况，最终呈现的函数图像（这里指红色的预判线）将会不再准确。
- 在使用以上方程时，每次f函数需要被重新定义，并且每次的返回值必须是一个整数或浮点数。
- 返回值的精准度会随着适用的随机数的数量而变化。使用的数量越大，返回的值将会越精确，反而亦然。在以上的例子里，99999个随机数可以产生三位小数的精确度。
完成！
Thanks for reading! Have a good day!
[部分延伸例题选自 University of Toronto, ESC180 课程，见：https://github.com/guerzh/esc180lec]