拟蒙特卡罗方法

数值分析中，拟蒙特卡罗方法(Quasi-Monte Carlo method)是使用低差异列（一种确定生成的超均匀分布列，也称为拟随机列、次随机列）来进行数值积分和研究其它一些数值问题的方法。而普通的蒙特卡罗方法或蒙地卡罗积分方法使用的是伪随机数。MATLAB中提供了生成如哈尔顿列、索博尔列等超均匀分布列的函数^[1]。

伪随机序列

低差异序列（索博尔列）

由伪随机数法和低差异列法生成的256点序列（红点为第1至10点，蓝点为第11至100点，绿点为第101至256点）直观上，低差异列的分布更为均匀

拟蒙特卡罗方法和蒙特卡罗方法的具体内容相似，要解决的问题都是通过测量某个可测函数 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)^[2]。

近年来，拟蒙特卡罗方法在金融数学和计算机数学领域里得到了越来越多的应用^[2]，因为其中常常会需要计算高维积分的数值近似。蒙特卡罗方法和拟蒙特卡罗方法可以快捷简单地得到较好的结果。

误差估计

拟蒙特卡罗方法的近似误差可以用取点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变差^[3]，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中边界与坐标轴平行的方形“块”^[3]。 $|\epsilon |\leq V(f)D_{N}$ 表明拟蒙特卡罗方法的近似误差大约是 $O({\frac {1}{N}})$ 的量级，于此相对的是普通蒙特卡罗方法的近似误差为 $O({\frac {1}{\sqrt {N}}})$ 量级。注意这里的不等式给出的是误差上限，事实上拟蒙特卡罗方法的收敛速率要比其上限所示的速率快得多^[2]。因此，一般来说拟蒙特卡罗方法比起普通的蒙特卡罗方法来说大大加快了收敛的速率。

参考来源

^ Generating Quasi-Random Numbers
^ ^2.0 ^2.1 ^2.2 Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages
^ ^3.0 ^3.1 William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [1] （页面存档备份，存于互联网档案馆）)

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, CiteSeer:[2] （页面存档备份，存于互联网档案馆）)

Harald Niederreiter. Random Number Generation and Quasi-Monte Carlo Methods. Society for Industrial and Applied Mathematics, 1992. 编辑
- （英文）一个直观的拟蒙特卡罗方法简介

[1] Generating Quasi-Random Numbers

[asmunssen_glynn_book-2] 2.0 ^2.1 ^2.2 Søren Asmussen and Peter W. Glynn, Stochastic Simulation: Algorithms and Analysis, Springer, 2007, 476 pages

[morokoffNcaflisch-3] 3.0 ^3.1 William J. Morokoff and Russel E. Caflisch, Quasi-Monte Carlo integration, J. Comput. Phys. 122 (1995), no. 2, 218--230. (At CiteSeer: [1] （页面存档备份，存于互联网档案馆）)

[1]

[2]

[3]