Quasi蒙地卡罗法.docVIP

Quasi蒙地卡羅法 基本的蒙地卡羅法是藉由抽取電腦亂數來進行大量模擬的數值方法，由於程式語言中使用的亂數產生函式在計算出均勻分布的亂數序列時會發生某些問題，例如群集的情形與變數品質不佳，當我們利用電腦的亂數函式產生兩個獨立的隨機變數數列，將第一列的數值當作Ｘ座標，第二列的數值作為Ｙ座標來產生一個在２Ｄ平面上的點時，會發現因為數列間的差異性使得產生出來的變數有群集的情形發生如圖一。另外，在大量模擬時，被用來當作亂數產生的種子（通常是系統時間）在進行大量模擬時仍有可能產生重複的可能性，造成程式取得的隨機變數品質不佳。由於蒙地卡羅法是以隨機的方式抽取電腦隨機亂數，所以每次模擬計算出的數值與理論的正確值之間的誤差也成為另一個隨機變數，無法百分之百地確保我們模擬的正確性。最後一個缺陷是因為在基本的蒙地卡羅法中，我們利用提高模擬標的物價格的次數Ｎ來提升程式的正確性，因為根據中央極限定理，最後標的物價格的收歛速度等於，所以為了讓模擬的結果收斂速度加快以及改善抽取的隨機變數品質問題，我們可以使用Quasi蒙地卡羅法。 　　圖一　電腦產生的隨機變數　　　　　　圖二：低差異性數列 Quasi蒙地卡羅法的優點 Quasi蒙地卡羅法的模擬方法是使用已經決定好的低差異性數列來代替電腦產生的亂數帶入原先的蒙地卡羅程式中。我們將根據演算法產生出來的低差異性數列依照上述的方法，將兩列數列分別作為Ｘ及Ｙ座標產生出來在２Ｄ平面上的點，不僅能夠均勻的分布在二維空間中，也不會產生在進行大量模擬時有隨機變數重複的情形發生，且根據模擬的結果，Quasi 蒙地卡羅法在收歛速度上，突破了之前的瓶頸，將收歛速度加快到O() ，其中與使用的陣列及所需的陣列數有關，它也擁有更小的誤差，因此完全解決之前基本蒙地卡羅法的問題。但由於Quasi蒙地卡羅法是使用事先決定好的數列，喪失了隨機性所以可以設計特定的模型使之完全失效，所以喪失隨機性為此方法之缺點。 本章可分為三部份(1)介紹低差異性數列的特性與產生方法(2)撰寫使用低差異性數列的程式(3)改良後的蒙地卡羅法程式的撰寫 低差異性數列的特性與演算法 數列間的低差異性是指根據演算法產生的數列，把第一列數列作為一維座標，第二列數列作為二維座標，依此類推至第Ｎ列數列產生出來的點分布在Ｎ維空間中的每個子空間的機率差異不大，能夠很均勻的分布在空間中。 我們必須先了解產生數列的演算法，才能清楚每種數列的特色，並適當的使用它在蒙地卡羅模擬上。 -Halton Halton的演算法(1)首先我們會先選出一個數作為基底=B， 如果是第i個維度，就在質數集合中挑第i大的當基底，接下來把自然數的集合的每個數n表示成B進位的表示法 : n = (2)將之前得到的B進位表示法的各項系數代入下列式子，即得到轉換後的數字　 範例: 基底為3  : 1 = 0*3 + 1 (　 : 2 = 0*3 + 2 ( : 3 = 1*3 + 0 ( dim=1 base=2 dim=2 base=3　 Halton數列演算法的特色 Halton 演算法在產生不同列的數列時是使用不同的質數做為基底，例如一維空間的基底為2，二維空間是3，三維空間為，依此類推上去。Halton數列有兩個主要的缺點:(1)因著基底不同，而有不同長度的循環，而在每段循環中數列都是呈單調遞增，基底越大循環長度也漸增，也需要較長的計算時間。 (2)在剛開始的數列間以及高維度的數列間都呈現了較高的相關性（如圖a，b，c），所以計算出來的Halton數列前200個數值基本會被捨棄不用，而在多標的物模擬需要用到較高維度數列時，Halton數列的表現也是較為不佳的。  圖a 圖b 圖c -Faure Faure演算法（複雜度：O( Faure數列的產生方式與Halton不同，並不是以一列數列的方式計算，而是計算出一組Ｎ維空間的點，也就是算出不同列數列中相同位置的點，在這例子中k是每條數列的長度，也可以說是有k組在N維空間的點 首先我們會先選出一個數作為基數m，m是大於等於N的最小質數 每組N維空間的點皆從第一維開始計算，For with (k的m進位表示法) 按照演算法依序計算到第N維(i從2到N) 以之前Halton算過的例子，N =3，m=3 = m =3的數列 Faure數列是把Halton數列順序打亂後重新組合起來，它解決了Halton數列的一項缺點，就是除了第一列數列外，它沒有Halton數列會單調遞增循環的問題，但還是保有另一項缺點，在兩列數列