Monte Carlo Algorithms

Calculating Pi

• 假設我們有一個隨機數生成器，它可以隨機生成[-1,1]之間的實數，我們每次生成兩個隨機數，一個作為x，一個作為y，這樣我們就有了一個點，所有的點都會落在藍色的正方形里面，由于x和y都是在[-1,1]之間均勻分布，所以正方形中所有的點都有相同的概率密度，正方形中包含一個綠色的原，半徑為1，圓心是原點。剛剛隨機生成的點可能會落在圓里面，可能會落在圓外面。這里我們不難得到落在圓中的概率為$\frac{\pi }{4}$。

• 假設我們在正方形區域中隨機抽樣n個點，那么點落在圓中的期望就是$Pn=\frac{\pi n}{4}$??。當然這里只是期望，可能我們抽五個點，他們都不在圓中。
  

• 那么我們怎么判斷點是不是在圓中呢？我們可以使用圓的方程可以得到下面一個不等式：$x^2+y^2\le 1$

• 假設我們均勻隨機抽樣n個點，通過上述不等式，我們發現有m個點在圓中。如果我們的抽樣n非常大，這樣我們就可以觀測到$m\approx \frac{\pi n}{4}$，所以我們得到$\pi \approx \frac{4m}{n}$。大數定律保證蒙特卡洛的正確性，當$n\to \infty$?，$\frac{4m}{n}\to \pi$。

• 這樣我們可以得出結論，當我們在正方形中隨機抽樣n個點，有m個點落在圓中，我們就可以將$\pi$近似為$\frac{4m}{n}$??。這里我們需要保證抽樣是均勻的，抽到所有點的概率都相同，否則就不成立。
  

Buffon’s Needle Problem

• 這也是一個計算Pi的例子，通過畫幾條平行線，然后撒一把針，通過針與平行線相交的個數可以推算出pi。
  • 先畫一些平行線，兩個平行線之間的距離為d
  • 取一些針，針的長度為l。
  • 隨機把針拋到紙上，針的長度是l，針可能與平行線相交也可能不相交。
  • 假設針的位置和角度都是均勻隨機的，那么針和平行線有一定概率相交，通過微積分可以計算出相交的概率為$P=\frac{2l}{\pi d}$?。
    
• 上面我們得到了針與平行線相交的概率$ P=\frac{2l}{\pi d}$??，這樣我們就可以得到期望$Pn = \frac{2ln}{\pi d}$，這樣我們不難計算$\pi \approx \frac{2ln}{dm}$?

近似求積分

• 假設給我們一個函數：$f(x)=\frac{1}{1+sin(x)?(lo{g}_{e}x{)}^2}$

• 計算定積分：$I={\int }_{0.8}^{3}f(x)dx$

• 這個函數太復雜了我們沒有辦法求它的定積分，這時候我們就需要用數值方法近似求它的定積分了，蒙特卡洛就是最常用的數值方法。

  • 我們首先在[0.8,3]上均勻隨機抽樣n個樣本
  • 然后我們計算n個樣本的函數值
  • 然后用$Q_n=(b?a)?\frac{1}{n}{\Sigma }_{i=1}^{n}f(x_i)$
  • 然后就可以使用$Q_n$來近似定積分。

• 剛剛計算的是一元函數的定積分，下面我們看看多元函數的定積分

  • 假設f(x)是一個多元函數，自變量是向量x
  • 計算函數在集合$\Omega$上的定積分：$I={\int }_{\Omega }f(x)dx$
    • 從集合$\Omega$中隨機抽樣n個向量
    • 計算$\Omega$集合的體積：$V={\int }_{\Omega }dx$
    • 然后計算$Q_n=V?\frac{1}{n}{\Sigma }_{i=1}^{n}f(i)$
    • 然后我們使用$Q_n$來近似定積分

近似求期望

• 定義X為d維的隨機變量

• P(x)為概率密度函數，它描述了變量X在某個點附近取值的可能性。有這樣的性質：${\int }_{{\mathbb{R}}^d}p(x)dx=1$
  

• 使用蒙特卡洛來近似求期望

  • 根據概率密度函數$p(x)$來隨機抽樣
  • 計算每個樣本$f(x_i)$的值，然后求所有n個函數值的平均，將平均值記為：$Q_n$
  • 使用$Q_n$作為期望的估計。

總結

以上是生活随笔為你收集整理的蒙特卡洛近似的一些例子的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。