Monte Carlo method (蒙地卡羅積分法)

• 前言

在這段前間，寫了不少文章來分析電腦圖學的演算法，

但發現，我一直忽略了一個前提，怎麼做積分 ...

之前一直用很隨便的方式來說明 ...

但是仔細想想，還是得要用一個科學的方法來講解，才能夠增加理解。

因此，臨時寫了這篇文章，為之後所談到的演算法實現，做個基礎。

在電腦計算領域中，最常被使用來做積分的方法就是 Monte Carlo method ，

本篇文章就是簡單闡述 Monte Carlo method 原理，以方便之後實作圖學論文中積分的方法。

• Monte Carlo method

令函式 f(x), x  的範圍在 [0,π] , 將其圖示化得到下圖

對函式 f(x) 在 [0,π] 的範圍內做積分，就是去求得藍色範圍的面積

但說實在，要去做這樣的計算不是一件簡單的事，

因此 Monte Carlo Method 提出了這樣的假設：

令 π 作為矩形的長度，我們可以找到一個常數 h 值，作為矩形的高度，使得

因此，積分就變成了如何找出 h 這個值。

h 這個值，最簡單的方式是在 [0,π] 的範圍內等間距的採樣(我習慣叫他離散採樣)，

去計算這些採樣值的平均值，作為 h 。

當樣本數越多，則結果越接近。

因此，用數學式來表示 Monte Carlo method 為

把範圍從範例的 [0,π] 改寫成任意範圍 [a,b] 可以得到

這個方程式又稱作 函數 f 的 Monte Carlo Estimator

• 證明

Monte Carlo method 的證明方式是通過計算 Monte Carlo Estimator 的期望值而得

其中，p(x) 是隨機密度函數(probability density function, 簡稱 PDF)。

簡單來說就是範圍內採樣點x的發生機率。

從上述的算式可以證明 函數 f(x) 的 Monte Carlo Estimator 的期望值

和其積分結果是相等的。

根據 Law of large numbers (大數法則)，

當取樣數越多，則結果越接近期望值，

因此，給定足夠數量的取樣點，Monte Carlo Estimator 可以得到積分結果。

• 隨機密度函數和多元積分

在一開始說明時，我假設範圍區間內每個採樣點的發生率是一致的(在上例為 1 / (b - a))，

但如果每個採樣點的發生機率不一致，則 函數 f(x) 的 Monte Carlo Estimator 可改寫成

同樣證明的方法也是計算期望值

Monte Carlo method 也可以簡單運用在多元積分上。

• 結論

Monte Carlo method 的優點在於他的簡單和方便用於多次元積分的擴充性，

但如何能夠減少採樣數並接近正確值又是另一項課題。

這方面的介紹我會等到應用到這方面的技術時在一併說明。

本章節只要瞭節如何應用 Monte Carlo method 做積分即可

• 追記

關於積分，研究了一些資料之後，

發現了一個類似的積分方式叫做 Riemann integral (黎曼積分)。

其方法是將積分區間內，分成多個矩形，並將這些矩形面積相加後，可得到積分的近似值。

這些矩形的總和，又稱作 Riemann Sum  (黎曼和)。

和  Monte Carlo method 最大的差別在於，Riemann Sum 是計算每個採樣點間的面積，

之後再累加起來作為積分的近似值。

因此，在不知道取樣點的發生機率時，Riemann Sum 提供了一個簡單方便的方法。