6. 蒙特卡洛算法

6.1 計算π" role="presentation" style="display: inline; font-style: normal; font-weight: normal; text-indent: 0px; text-align: left; text-transform: none; letter-spacing: normal; word-spacing: normal; overflow-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; position: relative;">ππ

回到頂部

a. 原理

如果我們不知道 ππ 的值，我們能不能用隨機數 來近似 ππ 呢？

假設我們用一個隨機數生成器，每次生成兩個范圍在 [−1,+1][−1,+1] 的隨機數，一個作為 x，另一個作為 y，即生成了一個二維隨機點：

假如生成 1億 個隨機樣本，會有多少落在 半徑=1 的圓內？這個概率就是圓的面積除以正方形的面積。

即：P=πr222=π4P=πr222=π4

假設從正方形區域中隨機抽樣 n 個點，那么落在圓內點個數的期望為：Pn=πn4Pn=πn4，

下面我們去求落在圓內的點的個數，只需滿足x2+y2?1x2+y2?1 即為圓內。

如果生成的隨機點的個數足夠多，落在圓內的實際觀測值 m≈πn4m≈πn4；

我們已知了m 與 n，所以π≈4mnπ≈4mn.

事實上，根據概率論大數定律：

4mn→π4mn→π，as n → ∞

這保證了蒙特卡洛的正確性。

伯恩斯坦概率不等式還能確定 觀測值和真實值之間誤差的上界。

|4mn−π|=O(1n√)|4mn−π|=O(1n)

說明 這個誤差與樣本n的根號成反比。

回到頂部

b. 代碼

下面放一個Python/ target=_blank class=infotextkey>Python代碼

hide code#coding=utf-8
#蒙特卡羅方法計算 pi
import random,math,time
start_time = time.perf_counter()
s = 1000*1000
hits = 0
for i in range(s):
    x = random.random()
    y = random.random()
    z = math.sqrt(x**2+y**2)
    if z<=1:
        hits +=1

PI = 4*(hits/s)
print(PI)
end_time = time.perf_counter()
print("{:.2f}S".format(end_time-start_time))

# 輸出
3.141212
0.89S

另外可還有一個可視化程序，可以模擬點落在方塊區域圓內外：
http://www.anders.wang/monte-carlo/

6.2 Buffon's Needle Problem

回到頂部

a. 原理

布封投針，也是用蒙特卡洛來近似 ππ 值。這是一個可以動手做的實驗。

用一張紙，畫若干等距平行線（距離為 d），撒上一把等長的針（長度為l），通過與平行線相交的針的數量，就可以推算出 ππ。

通過微積分可以算出：相交的概率為：P=2lπdP=2lπd

微積分推導過程：

課程里并沒有講解推導，這里我參考的是一下兩篇博客的推導過程：

https://zhuanlan.zhihu.com/p/479953215https://cosx.org/2009/11/a-brief-talk-on-buffon-throwing-needle-problems/

主流做法是通過對針的斜率進行積分：

這里我后續補充。

跟 6.1 類似，我們隨機扔 n 根針，這樣相交個數的期望為 Pn=2lnπdPn=2lnπd 。我們可以觀察到（如果是電腦模擬即為通過公式判斷出）有 m 跟針實際與線相交，如果n足夠大，則 m≈2lnπdm≈2lnπd。

求 ππ 公式即為： π≈2lnmdπ≈2lnmd

回到頂部

b. 代碼

有了公式 π≈2lnmdπ≈2lnmd，代碼實現其實很簡單了，僅列出一種實現思路：

hide codeimport numpy as np

def buffon(a,l,n):
  xl = np.pi*np.random.random(n)
  yl = 0.5*a*np.random.random(n)
  m = 0
  for x,y in zip(xl,yl):
    if y < 0.5*l*np.sin(x):
      m+=1
  result = 2*l/a*n/m
  print(f'pi的估計值是{result}')
  
buffon(2,1,1000000)

# 輸出為：
pi的估計值是3.153977165205324

當然，也有可視化的代碼：

hide codeimport matplotlib.pyplot as plt
import random
import math
import numpy as np

NUMBER_OF_NEEDLES = 5000


class DefineNeedle:
    def __init__(self, x=None, y=None, theta=None, length=0.5):
        if x is None:
            x = random.uniform(0, 1)
        if y is None:
            y = random.uniform(0, 1)
        if theta is None:
            theta = random.uniform(0, math.pi)

        self.needle_coordinates = np.array([x, y])
        self.complex_representation = np.array(
            [length/2 * math.cos(theta), length/2*math.sin(theta)])
        self.end_points = np.array([np.add(self.needle_coordinates, -1*np.array(
            self.complex_representation)), np.add(self.needle_coordinates, self.complex_representation)])

    def intersects_with_y(self, y):
        return self.end_points[0][1] < y and self.end_points[1][1] > y


class BuffonSimulation:
    def __init__(self):
        self.floor = []
        self.boards = 2
        self.list_of_needle_objects = []
        self.number_of_intersections = 0

        fig = plt.figure(figsize=(10, 10))
        self.buffon = plt.subplot()
        self.results_text = fig.text(
            0, 0, self.estimate_pi(), size=15)
        self.buffon.set_xlim(-0.1, 1.1)
        self.buffon.set_ylim(-0.1, 1.1)

    def plot_floor_boards(self):
        for j in range(self.boards):
            self.floor.Append(0+j)
            self.buffon.hlines(
                y=self.floor[j], xmin=0, xmax=1, color='black', linestyle='--', linewidth=2.0)

    def toss_needles(self):
        needle_object = DefineNeedle()
        self.list_of_needle_objects.append(needle_object)
        x_coordinates = [needle_object.end_points[0]
                         [0], needle_object.end_points[1][0]]
        y_coordinates = [needle_object.end_points[0]
                         [1], needle_object.end_points[1][1]]

        for board in range(self.boards):
            if needle_object.intersects_with_y(self.floor[board]):
                self.number_of_intersections += 1
                self.buffon.plot(x_coordinates, y_coordinates,
                                 color='green', linewidth=1)
                return
        self.buffon.plot(x_coordinates, y_coordinates,
                         color='red', linewidth=1)

    def estimate_pi(self, needles_tossed=0):
        if self.number_of_intersections == 0:
            estimated_pi = 0
        else:
            estimated_pi = (needles_tossed) / 
                (1 * self.number_of_intersections)
        error = abs(((math.pi - estimated_pi)/math.pi)*100)
        return (" Intersections:" + str(self.number_of_intersections) +
                "n Total Needles: " + str(needles_tossed) +
                "n Approximation of Pi: " + str(estimated_pi) +
                "n Error: " + str(error) + "%")

    def plot_needles(self):
        for needle in range(NUMBER_OF_NEEDLES):
            self.toss_needles()
            self.results_text.set_text(self.estimate_pi(needle+1))
            if (needle+1) % 200 == 0:
                plt.pause(1/200)
        plt.title("Estimation of Pi using Probability")

    def plot(self):
        self.plot_floor_boards()
        self.plot_needles()
        plt.show()


simulation = BuffonSimulation()
simulation.plot()
折疊 

效果如圖：

以上內容參考：

1. 課程視頻
2. https://www.section.io/engineering-education/buffon-needle/
3. https://github.com/topics/buffon-needle
4. https://github.com/GunnarDahm/buffon_monte_carlo_sim/blob/master/buffon_monte_carlo.py
5. https://blog.csdn.NET/qq_45757739/article/details/108387567
6. https://blog.csdn.net/TSzero/article/details/111604960

理解思想即可，如果后續有機會，可能單出一篇介紹介紹，也有可能將這部分豐富一下。

6.3 估計陰影部分的面積

我們稍微推廣一下，試著用蒙特卡洛解決一個陰影部分面積的求解。比如下圖：

我們如何使用蒙特卡洛的思路解決這個陰影部分面積的求解呢？

類似于上面的思路，在正方形內做隨機均勻抽樣，得到很多點，怎么確定點在陰影部分呢？

可知，陰影部分的點滿足：

{x2+y2>4(x−1)2+(y−1)2≤1{x2+y2>4(x−1)2+(y−1)2≤1

• 易知，正方形面積 A1=4A1=4；設陰影部分面積為 A2A2
• 隨機抽樣的點落在陰影部分的概率為：P=A2A1=A24P=A2A1=A24
• 從正方形區域抽樣 n 個點，n盡可能大，則來自陰影部分點的期望為：nP=nA24nP=nA24；
• 如果實際上滿足上述條件的點 有 m 個，則令 m≈nPm≈nP
• 得到：A2≈4mnA2≈4mn

代碼與 6.1 相近。

6.4 求不規則積分

近似求積分是蒙特卡洛在工程和科學問題中最重要的應用。很多積分是沒有解析的積分（即可以計算出來的積分），特別是多元積分，而只能用數值方法求一個近似值，蒙特卡洛就是最常用的數值方法。

一元函數步驟如下：

我們要計算一個一元函數的定積分 I=∫baf(x)dxI=∫abf(x)dx;

• 從區間 [a,b][a,b] 上隨機均勻抽樣 x1,x2,...,xnx1,x2,...,xn;
• 計算 Qn=(b−a)1n∑ni=1f(xi)Qn=(b−a)1n∑i=1nf(xi)，即均值乘以區間長度；
• 這里均值乘以區間長度是 實際值，而 I 是期望值
• 用 QnQn 近似 II

大數定律保證了 當n→∞,Qn→In→∞,Qn→I

多元函數步驟如下：

我們要計算一個多元函數的定積分 I=∫baf(x? )dx? I=∫abf(x→)dx→，積分區域為 ΩΩ;

• 從區間 ΩΩ 上隨機均勻抽樣 x1→,x2→,...,xn→x1→,x2→,...,xn→;
• 計算 ΩΩ 的體積V（高于三維同樣）：V=∫Ωdx? V=∫Ωdx→；
• hh值得注意的是，這一步仍要計算定積分，如果形狀過于復雜，無法求得 V，那么無法繼續進行，則無法使用蒙特卡洛算法。所以只能適用于比較規則的區域，比如圓形，長方體等。
• 計算 Qn=V1n∑ni=1f(xi→)Qn=V1n∑i=1nf(xi→)，即均值乘以區間長度；
• 這里均值乘以區間長度是 實際值，而 I 是期望值
• 用 QnQn 近似 II

下面我們從積分的角度再來看看 蒙特卡洛近似求 pi

• 定義一個二元函數 f(x,y)={1 if點在圓內0 if點在圓外f(x,y)={1 if點在圓內0 if點在圓外;
• 定義一個區間 Ω=[−1,1]×[−1,1]Ω=[−1,1]×[−1,1]
• I=πr2=πI=πr2=π
• 接下來用蒙特卡洛近似 I，得到關于 ππ的算式即可得到近似的ππ;隨機抽樣 n 個點，記為(x1,y1),...,(xn,yn)(x1,y1),...,(xn,yn)計算 區域面積 V=∫Ωdxdy=4V=∫Ωdxdy=4；計算 Qn=V1n∑ni=1f(xi,yi)Qn=V1n∑i=1nf(xi,yi)蒙特卡洛近似 Q 與 I 近似相等：π=Qn=∫Ωf(x,y)dxdyπ=Qn=∫Ωf(x,y)dxdy

這是從蒙特卡洛積分的角度得到的pi，6.1 中則是從蒙特卡洛概率和期望的角度得到的。

6.5 用蒙特卡洛近似期望

這個方法對于統計學和機器學習很有用。

• 定義 X 是 d 維的隨機變量，函數 p(x) 是一個PDF，概率密度函數；
• 函數 f(x)f(x) 的期望：Ex∼p[f(X)]=∫Rdf(X)⋅(x)dxEx∼p[f(X)]=∫Rdf(X)⋅(x)dx
• 直接以上面的方式求期望可能并不容易，所以通常使用蒙特卡洛近似求期望：隨機抽樣：根據概率密度函數 p(x)p(x) 進行隨機抽樣，記為X1,X2,...,XnX1,X2,...,Xn；計算 Qn=1n∑ni=1f(xi)Qn=1n∑i=1nf(xi)用 Q 近似 期望Ex∼p[f(X)]Ex∼p[f(X)]

6.6 總結 | 蒙特卡洛算法的思想

我的想法是盡量精簡，即：

模擬---抽樣---估值，通過模擬出來的大量樣本集或者隨機過程，以隨機抽樣的方式，去近似我們想要研究的實際問題對象。

補充蒙特卡洛相關：

蒙特卡洛是摩洛哥的賭場；

蒙特卡洛算法得到的結果通常是錯誤的，但很接近真實值，對于對精度要求不高的機器學習已經足夠。隨機梯度下降就是一種蒙特卡洛算法，用隨機的梯度近似真實的梯度，不準確但是降低了計算量。

蒙特卡洛是一類隨機算法，除此以外還有很多隨機算法，比如拉斯維加斯算法（結果總是正確的算法）

文章來自
https://www.cnblogs.com/Roboduster/p/16451932.html