機率與統計 · 蒙地卡羅法

蒙地卡羅法

蒙地卡羅法用隨機取樣來估計數值:在單位正方形內均勻、獨立地投下N個點,落在區域內的比例就能估計它的面積,標準誤與1/√N成正比。按「投點」,觀察π的估計值如何漸趨穩定,以及不確定性如何改變。

圖中的蒙地卡羅法

蒙地卡羅法用隨機取樣來估計固定數值。這裡要估的是面積:在單位正方形內均勻隨機地投下NN個點,其中HH個落在區域內,便用H/NH/N估計該區域的面積aa。四分之一圓的面積是π/4\pi/4,所以可以用4H/N4H/N估計π\pi;對y=e−x2y = e^{-x^2}下方的區域也能用同樣的計數方法估計積分,即使它沒有初等反導函數。下圖呈現NN增加到一百萬時估計值的變化,並標出估計值約有95%機會落入的區間。

為什麼命中比例可以估計面積

在面積為1的正方形內均勻隨機取一個點,落入某區域的機率就等於該區域的面積。每個點都是具有相同命中機率的獨立試驗。依大數法則,命中比例會趨近aa。區域可以是任何形狀,只要能判斷點是否落在裡面即可。

能估得多準

命中數服從二項分配,因此命中比例H/NH/N的標準差為a(1−a)/N\sqrt{a(1-a)/N}。典型誤差以1/N1/\sqrt{N}的速率縮小:點數變成十倍,誤差約除以10≈3.16\sqrt{10} \approx 3.16;若要把誤差降為十分之一,約需一百倍的點數。即使用一百萬點估計π,誤差範圍仍約為±0.003。不必知道真實面積也能估計這個範圍:用觀察比例p^=H/N\hat p = H/N代替aa,便得到誤差範圍±1.96p^(1−p^)/N\pm 1.96\sqrt{\hat p(1-\hat p)/N},據此建立近似95%信賴區間。本頁只在命中和未命中各至少十次後才顯示。如果固定NN反覆進行整個實驗,約每二十個區間就有一個不涵蓋真值。下圖的藍色帶狀區域,是對每個NN分別畫出真值周圍的範圍;整條路徑不必始終落在裡面。一次實驗的誤差也不會單調下降:加點後估計值可能暫時離真值更遠。穩定縮小的是不確定性的範圍。

什麼時候值得用

對平滑的單變數函數,若計算函數值的次數相同,辛普森法等確定性方法準確得多(見數值積分)。蒙地卡羅法的優點是收斂速率1/N1/\sqrt{N}中的指數不隨維度改變;相對地,每邊有mm個點的網格,在dd維中需要mdm^d個點。因此在高維問題中,蒙地卡羅法可能更合適。目標很小時則能看出它的弱點:相對於面積的標準誤為(1−a)/(aN)\sqrt{(1-a)/(aN)}。若區域只占正方形的百分之一,要維持相同的相對準確度,就需要多得多的點。

觀察重點

  • 隨機點不會規則地彼此錯開。只投幾百點時,看見群聚和空白區都很正常。
  • 這些點由帶編號種子的虛擬隨機數產生器產生,所以開啟分享連結會重現相同的點。投到一百萬點後,再按「投點」便會換下一個種子重新開始。

相關主題