擬蒙特卡羅方法

偽隨機序列

低差異序列（索博爾列）

由偽隨機數法和低差異列法生成的256點序列（紅點為第1至10點，藍點為第11至100點，綠點為第101至256點） 直觀上，低差異列的分佈更為均勻

數值分析中，擬蒙特卡羅方法(Quasi-Monte Carlo method)是使用低差異列（一種確定生成的超均勻分佈列，也稱為擬隨機列、次隨機列）來進行數值積分和研究其它一些數值問題的方法。而普通的蒙特卡羅方法或蒙地卡羅積分方法使用的是偽隨機數。MATLAB中提供了生成如哈爾頓列、索博爾列等超均勻分佈列的函數。

擬蒙特卡羅方法和蒙特卡羅方法的具體內容相似，要解決的問題都是通過測量某個可測函數 f 在某些點上的取值，而在數值上求它的積分的近似值。例如要求在單位體積$[0,1]^{s}$上的積分近似，可以設取的點為x₁, ..., x_N，那麼：

$\int _{[0,1]^{s}}f(u)\,{\rm {d}}u\approx {\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i}).$

其中的x_i都是s維向量。擬蒙特卡羅方法和普通蒙特卡羅方法的區別在於x_i的具體選取方式。蒙特卡羅方法用的是偽隨機列，而擬蒙特卡羅方法用到的是哈爾頓列、索博爾列等低差異列。使用低差異列的優點是收斂速率較快。擬蒙特卡羅方法可以達到O(1/N)的收斂速率，而普通蒙特卡羅方法的收斂速率則是 O(N^-0.5)。

近年來，擬蒙特卡羅方法在金融數學和計算機數學領域裏得到了越來越多的應用，因為其中常常會需要計算高維積分的數值近似。蒙特卡羅方法和擬蒙特卡羅方法可以快捷簡單地得到較好的結果。

誤差估計

擬蒙特卡羅方法的近似誤差可以用取點x₁, ..., x_N的差異度作為上限。具體來說，Koksma-Hlawka不等式表明，誤差項

$\epsilon =|\int _{[0,1]^{s}}f(u)\,{\rm {d}}u-{\frac {1}{N}}\,\sum _{i=1}^{N}f(x_{i})|$

被

$|\epsilon |\leq V(f)D_{N}$

限制，其中V(f)為函數f的Hardy-Krause變差，D_N是(x₁,...,x_N)的差異度，定義為

$D_{N}=\sup _{Q\subset [0,1]^{s}}\left|{\frac {Q{\mbox{中的点的数量}}}{N}}-Q{\mbox{的体积}}\right|$,

其中Q是任何[0,1]^s中邊界與坐標軸平行的方形「塊」。$|\epsilon |\leq V(f)D_{N}$表明擬蒙特卡羅方法的近似誤差大約是$O({\frac {1}{N}})$的量級，於此相對的是普通蒙特卡羅方法的近似誤差為$O({\frac {1}{\sqrt {N}}})$量級。注意這裏的不等式給出的是誤差上限，事實上擬蒙特卡羅方法的收斂速率要比其上限所示的速率快得多。因此，一般來說擬蒙特卡羅方法比起普通的蒙特卡羅方法來說大大加快了收斂的速率。

參考來源

• R. E. Caflisch, Monte Carlo and quasi-Monte Carlo methods, Acta Numerica vol. 7, Cambridge University Press, 1998, pp. 1-49.

• Josef Dick and Friedrich Pillichshammer, Digital Nets and Sequences. Discrepancy Theory and Quasi-Monte Carlo Integration, Cambridge University Press, Cambridge, 2010, ISBN 978-0-521-19159-3

• Michael Drmota and Robert F. Tichy, Sequences, discrepancies and applications, Lecture Notes in Math.,1651, Springer, Berlin, 1997, ISBN 3-540-62606-9

• William J. Morokoff and Russel E. Caflisch, Quasi-random sequences and their discrepancies, SIAM J. Sci. Comput. 15 (1994), no. 6, 1251--1279 (AtCiteSeer:[2] （頁面存檔備份，存於互聯網檔案館）)

• Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-295-5

• Harald G. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84(1978), no. 6, 957--1041

• Oto Strauch and Štefan Porubský, Distribution of Sequences: A Sampler, Peter Lang Publishing House, Frankfurt am Main 2005, ISBN 3-631-54013-2

外部連結

• （英文）一個直觀的擬蒙特卡羅方法簡介