圖中的蒙地卡羅法
蒙地卡羅法用隨機取樣來估計固定數值。這裡要估的是面積:在單位正方形內均勻隨機地投下個點,其中個落在區域內,便用估計該區域的面積。四分之一圓的面積是,所以可以用估計;對下方的區域也能用同樣的計數方法估計積分,即使它沒有初等反導函數。下圖呈現增加到一百萬時估計值的變化,並標出估計值約有95%機會落入的區間。
為什麼命中比例可以估計面積
在面積為1的正方形內均勻隨機取一個點,落入某區域的機率就等於該區域的面積。每個點都是具有相同命中機率的獨立試驗。依大數法則,命中比例會趨近。區域可以是任何形狀,只要能判斷點是否落在裡面即可。
能估得多準
命中數服從二項分配,因此命中比例的標準差為。典型誤差以的速率縮小:點數變成十倍,誤差約除以;若要把誤差降為十分之一,約需一百倍的點數。即使用一百萬點估計π,誤差範圍仍約為±0.003。不必知道真實面積也能估計這個範圍:用觀察比例代替,便得到誤差範圍,據此建立近似95%信賴區間。本頁只在命中和未命中各至少十次後才顯示。如果固定反覆進行整個實驗,約每二十個區間就有一個不涵蓋真值。下圖的藍色帶狀區域,是對每個分別畫出真值周圍的範圍;整條路徑不必始終落在裡面。一次實驗的誤差也不會單調下降:加點後估計值可能暫時離真值更遠。穩定縮小的是不確定性的範圍。
什麼時候值得用
對平滑的單變數函數,若計算函數值的次數相同,辛普森法等確定性方法準確得多(見數值積分)。蒙地卡羅法的優點是收斂速率中的指數不隨維度改變;相對地,每邊有個點的網格,在維中需要個點。因此在高維問題中,蒙地卡羅法可能更合適。目標很小時則能看出它的弱點:相對於面積的標準誤為。若區域只占正方形的百分之一,要維持相同的相對準確度,就需要多得多的點。
觀察重點
- 隨機點不會規則地彼此錯開。只投幾百點時,看見群聚和空白區都很正常。
- 這些點由帶編號種子的虛擬隨機數產生器產生,所以開啟分享連結會重現相同的點。投到一百萬點後,再按「投點」便會換下一個種子重新開始。
相關主題
延伸閱讀: 維基百科: Monte Carlo method (英文).