蒙特卡罗算法

蒙特卡洛法又称统计模拟法，得名于摩纳哥著名的赌场蒙特卡洛。该方法解决问题的基本步骤是：

• 构造一个概率模型，使得要解决的问题正好是概率模型的一个参数，比如概率模型的期望值
• 根据构建的概率模型生成样本
• 从样本中构建一个估计器并给出问题的近似解

下面以pi和自然常数的解为例，简单介绍一下模型卡罗法

π

• 构建概率模型
• 给定一个边长为2的正方形和期内切圆，内切圆和正常性的面积比率$ \frac{内切圆面积}{正方形面积} = \frac{\pi * 1^2}{2 * 2} = \frac{\pi}{4}$
• 如果在正方形内部随机产生一定数量的点，那么一个点落入内接圆的概率等于该内接圆与正方形面积的比值
• ，然后
• 采样
• ，构成样本，其中为样本量
• 构建估算器
• 样本落入圆圈的概率
• 

import matplotlib.pyplot as plt
import numpy as np

n = 10000

x = np.random.uniform(-1.0, 1.0, n)
y = np.random.uniform(-1.0, 1.0, n)


m = 0
inner_x = []
inner_y = []
outer_x = []
outer_y = []
for i in range(n):
    if x[i]*x[i] + y[i]*y[i] <= 1:
        m += 1
        inner_x.append(x[i])
        inner_y.append(y[i])
    else:
        outer_x.append(x[i])
        outer_y.append(y[i])
        
plt.figure(figsize=(8, 8))
plt.scatter(inner_x, inner_y, color='red', s = 10)
plt.scatter(outer_x, outer_y, color = 'blue', s = 10)


pi = 4 * m / n
print('n=%d, pi = %f' % (n, pi))

自然常数 e

• 构建概率模型
• 
• 是上图中阴影部分的面积，它的面积是用蒙特卡洛法计算的
• 要在正方形中产生均匀分布的随机点，点落入阴影部分的概率等于阴影面积与矩形面积的比
• 采样
• ，抽取样本, n为样本容量
• 构建估算器
• 
• 
• 

import matplotlib.pyplot as plt
import numpy as np


n = 1000
x = np.random.uniform(1.0, 2.0, n)
y = np.random.uniform(0.0, 1.0, n)

m = 0
inner_x = []
inner_y = []
outer_x = []
outer_y = []
for i in range(n):
    if y[i] <= 1 / x[i]:
        m += 1
        inner_x.append(x[i])
        inner_y.append(y[i])
    else:
        outer_x.append(x[i])
        outer_y.append(y[i])
        
plt.figure(figsize=(10, 10))
plt.scatter(inner_x, inner_y, color='red', s = 10)
plt.scatter(outer_x, outer_y, color = 'blue', s = 10)

print("n=%d, e = %f" % (n, np.power(2, n / m)))