蒙特卡洛方法与蒙特卡洛搜索树（一）

最近在做 AIOps 相关的项目时，用到了蒙特卡洛搜索树(MCTS)算法，对蒙特卡洛相关的内容有些兴趣，在此整理些相关的资料。

蒙特卡洛方法

蒙特卡洛方法（Monte Carlo method），也称统计模拟方法，是 1940 年代中期提出的一种以概率统计理论为指导的数值计算方法。是指使用随机数（或更常见的伪随机数）来解决很多计算问题的方法。

20 世纪 40 年代，在科学家冯·诺伊曼、斯塔尼斯拉夫·乌拉姆和尼古拉斯·梅特罗波利斯于洛斯阿拉莫斯国家实验室为核武器计划工作时，发明了蒙特卡洛方法。因为乌拉姆的叔叔经常在摩纳哥的蒙特卡洛赌场输钱得名，而蒙特卡洛方法正是以概率为基础的方法。

与它对应的是确定性算法

基本概念

通常蒙特卡罗方法可以粗略地分成两类：

• 一类是所求解的问题本身具有内在的随机性，借助电脑的运算能力可以直接模拟这种随机的过程。例如在核物理研究中，分析中子在反应堆中的传输过程。中子与原子核作用受到量子力学规律的制约，人们只能知道它们相互作用发生的概率，却无法准确获得中子与原子核作用时的位置以及裂变产生的新中子的行进速率和方向。科学家依据其概率进行随机抽样得到裂变位置、速度和方向，这样模拟大量中子的行为后，经过统计就能获得中子传输的范围，作为反应堆设计的依据。

• 另一种类型是所求解问题可以转化为某种随机分布的特征数，比如随机事件出现的概率，或者随机变量的期望值。通过随机抽样的方法，以随机事件出现的频率估计其概率，或者以抽样的数字特征估算随机变量的数字特征，并将其作为问题的解。这种方法多用于求解复杂的多维积分问题。

应用

下面主要介绍第二种类型的例子：

1. 蒙特卡洛计算π

  在上图中，1/4 圆面积与正方形面积之比为π:4. 让程序随机生成两个[0,1]之间的实数 x, y，看以 (x,y) 组成的点是否落在圆内。重复 N 次，统计圆内的点个数和总的点个数，其比值应接近于圆面积于正方形面积之比，即 π:4

2. 还是蒙特卡洛计算π

  布丰投针问题(Buffon's needle problem)，是布丰于 18 世纪提出的一个数学问题：   设我们有一个以平行且等距木纹铺成的地板（如下图），现在随意抛一支长度比木纹之间距离小的针，求针和其中一条木纹相交的概率。

  现假设：木板间距离为 $d$, 针长度为 $s$, 已知 $s<d$.   

应用蒙特卡洛方法，我们在地面投掷 $n$ 次，观测出针与地面相交的次数 $m$, 如果实验的次数足够多，则我们可以以 $p=\frac{m}{n}$ 代表针与地板木纹相交的概率。

  标题不是求 $\pi$ 么，到现在为止好像跟 $\pi$ 没有什么关系呀，别急，我们考虑下怎么跟随机分布扯上关系。

  因为要求相交的概率，如果知道了针的位置，是不是就能知道有没有相交呢。基于此，我们用变量 $(X,Y)$ 表示针的位置，那 $X,Y$ 分别代表什么呢，如果是在坐标系中，我们可以用向量表示位置，因为向量能确定方向和大小，同样地，我们需要一个变量代表大小，一个变量代表方向。

  如图，我们可以用 $X$ 代表针中点到最近木纹的距离，用 $Y$代表针与木纹的夹角，如此，就能确定针的位置了。

  由于投掷针是完全随机的，因此：

  - $X$ 服从 $[0,\frac{d}{2}]$ 上的均匀分布；

  - 同理，$Y$ 服从 $[0,\frac{\pi }{2}]$ 上的均匀分布。

  有了表示针位置的变量，那么如何判断相交呢？如上图，如果针端点与木纹刚好相交时，夹角为 $\alpha$, 此时，距离 $X=\frac{s}{2}\ast sin\alpha$. 如果不相交时，则对应的距离 $X>\frac{s}{2}\ast sin\alpha$, 如果是上图左侧示例，则$X<\frac{s}{2}\ast sin\alpha$.   另外，由于 $X,Y$ 相互独立，则有概率密度函数：

$P(X=x,Y=y)=\{\begin{array}{ll}\frac{2}{d}\ast \frac{2}{\pi }=\frac{4}{d\pi }& 0\le x\le \frac{d}{2},0\le y\le \frac{\pi }{2}\\ 0& else\end{array}$   

由此可计算针与直线相交的概率：

$P(x\le \frac{s}{2}\ast sinY)=\int {\int }_{x<\frac{s}{2}\ast siny}p(x,y)dxdy={\int }_{x=0}^{\frac{s}{2}\ast siny}{\int }_{y=0}^{y=\frac{\pi }{2}}\frac{4}{d\pi }dxdy=\frac{2s}{d\pi }$   

因此，$\frac{2s}{d\pi }=\frac{m}{n}$

Surprise!

archive: http://www.junphy.com/wordpress/index.php/2022/08/30/monte_carlo_method/