摘要
众所周知,利用伪随机数的传统蒙特卡罗(MC)方法收敛速度比较慢,收敛速度为O(N~(-1/2))。为了克服这个缺点,我们利用超均匀随机数来代替伪随机数以取得较好的效果。在MC方法中利用超均匀序列称为拟蒙特卡罗(QMC),我们可以给出QMC的理论上确界,但不能计算它的误差估计。为了弥补MC收敛速度慢和QMC不能计算误差的缺点,我们可以通过对拟随机数进行随机化(加扰),这种方法我们称之为随机化拟蒙特卡罗(RQMC)方法。随机化拟蒙特卡罗保持了QMC的收敛速度,并且使我们可以获得QMC的误差估计,另外还为我们提供了更多的拟随机序列。随之来的的一个自然的问题是,在众多的序列中那个是最优的?去随机化就是在RQMC中得到的众多序列中寻找一个或一组最优序列。本文利用线性随机化对拟随机序列进行随机化,并利用差异度准则寻找了一个最优Halton序列。
As we know,a drawback of MC methods is their low convergence,O(N~(-1/2)),Onegeneric approach to improving the convergence of MC methods has been the use ofhighly uniform random numbers in place of the usual pseudorandom numbers,calledQuasi-Monte Carlo methods.we only obtain the theoretical supper boundary ,itcannot o?er statistical error estimates .To employ the independence of MC andthe uniformity of QMC,randomized quasi-Monte Carlo (RQMC)methods is recentlyproposed .RQMC maintain the convergence of QMC and offer error estimates andproduce a family of quasi-Monte Carlo sequences .a natural question is how to choosean optimal quasirandom sequence from this family.The process of finding an optimalquasirandom sequences is called the derandomization of a randomized family.In thispaper ,we use the linear scrambling method to random the Halton sequence,andemploy the discrepancy criteria to choose the optimal Halton sequence.
引文
[1] J.Halton. On the e?ciency of certain quasirandom sequences of points in eval-uating multidimensional integrals. Numersiche Mathematik[J]. 1960,2:84-90.
[2] I.M.Sobol. Uniformly distributed sequences with additional uniformity prop-erties. USSR Comput.Math. and Math.phy[J]. 1976,16:236-242.
[3] H.Faure. Discrepancy of sequences associated with a nmber system(in dimen-sion s). Acta.Arith[J]. 1982,41(4):337-351.
[4] T.Warnock. Computational investigations of low discrepandcy point sets. Ap-plicatons of Number Theory to Numerical Analysis[M]. NewYork:Academicpress, 1972, 319-343 .
[5] E.Braaten and G.Weller. An improved low-discrepancy sequence for multidi-mensionl quasi-Monte Carlo integration. Journal of Computational[J]. 1979,33:249-258.
[6] W.J.Moroko? and R.E.Ca?isch. Quasirandom sequences and their discrep-ancy. SIAM Journao on Scientific Computing[J]. 1994, 15:1251-1279.
[7] T.T.Warnock. Computational investigations of low-discrepancy point sets II,in: H. Niederreiter, P.J.-S. Shiue (Eds.), Monte Carlo and Quasi-Monte CarloMethods in Scientific Computing[J]. Springer, Berlin, 1995.
[8] B.Tu?n. On the use of lowo -discrepancy sequences in Monte Carlo methods.Technical Report No.1060. IRISA.Resses[J]. 1996.
[9] E.Atanassov. On the discrepancy of the Halton sequences. Mathematica Balka-nize[J]. 2003
[10] J.Shaw. A quasirandom approach to interation in Bayesian statistics. Annalsof statistics[J]. 1998,16:895-914.
[11] Niederreiter. Low-dispersion sequences .Journal of Number Theory[J]. 1988,3: 99-107.
[12] A.Owen. Randomly permuted(t,m,s)-nets and (t,s)-sequences. Monte Carloand Quasi-Monte Carlo Methods in Scientific Computing,106 in Lecture Notesin Statistics[J].1995,299-317.
[13] S.Tezuka. Uniform Random Numbers, Theory and Practice[M]. Kluwer Aca-demic Publishers, IBM Japan. 1995.
[14] I.Friezes and A.Keller. Fast generation of randomized low discrepancy pointsets. In K.Fang,FlHickernell,and H.Niederreiter,editors, Monte Carlo andQuasi-Monte Carlo Methods[M].springer, 2002,257-273.
[15] S.Tezuka. Polynomial arithmetic analogue of Halton sequences. ACM Trans.on Modelling and Computer Simulation[J]. 1993,3:99-107.
[16] S.Tezuka. Quasi-Monte Carlo -discrepancy between theory and prac-tice. Monte Carlo and Quasi -Mnte Carlo Methods 2000[M].K-T.Fang ,F,J.Hickernell and Hl. Niederreiter(Eds):124-140.
[17] S.H.Paskov and J.FTraub. Faster valuation of financial derivatives. J.PortfolioManagement[J]. Fall 1995,22(1):113-120.
[18] A.papageorgiou and J.Traub. Beating Monte Carlo.RISK[J].1997,9:63-65.
[19] H.Morohosi and M.Fushimi. A practical approach to the error estimation ofQMC integration. In Monte Carlo and Quasi-Monte Carlo Methods1998[M].Springer, 2000,156-189.
[20] K.Tan and P.Boyle. Applicaton of randomized low discrepancy sequences tothe valuaton of complex securities. Journal of Economic Dynamics and Con-trol[J]. 2000, 24:1747-1782,
[21] H.Hong and F.Hickernell. Algorithm 823:Implementing scrambled digital se-quences. ACM Transactions on Mathematical Software[J]. 2003,29(2):95-109.
[22] A.Owen. Variance and discrepancy with alternative scramblings. ACM Trans.on Computational Lofic[J]. 2002,V:1-16.
[23]高惠璇著,统计计算[M].北京,北京大学出版社, 1995.7.
[24] H.Niederreiter. Random Numbers Generations and Quasi-Monte Carlo Meth-ods. SIAM, Philadelphia[J]. 1992.
[25] J.Spanier and E.Maize. Quasirandom methods for estimating integrals usingrelatively small sampling[J]. SIAM Review 1994,36:18-44.
[26] R.Ca?isch. Monte Carlo and quasi-Monte Carlo methods. Acta Numerica[J].1998, 7:1-49.
[27] S.Heinrich. E?cient algorithm foer computing the L2discrepancy. Mathemat-ics of Computation[J]. 1996,65:1621-1633.
[28] B.Fox. Implementation and relative e?ciency of quasirandom sequence gener-ators. ACM Trans. Mathematical sortware[J]. 1986,12:362-376.
[29] P.Davis and P.Rabinowita. Methods of Numerical integration[M]. New York:Academic Press, 1984.
[30] C.Joy,P.Boyle, and K.S.Tan. Quasi-Monte Carlo methods in numerical finance.Management Science[J]. 1996,42(6):926-938.
[31] R.Bouckaert. A stratified simulation scheme for inference in Bayesian beliefnetwork. Annals of statistics[J]. 1994,16:110-117
[32] L.Kocis and W.Whiten. Computational investigations of low discrepancy se-quences .ACM Trans. Mathematical sortware[J]. 1997,23:266-294.
[33] X.Wang and F.Hickernell. Randomized Halton sequences. Math .Comput.Modelling[J]. 2000, 32:887-899.
[34] P:L.Ecuyer and C.Lemieux. Recent advances in randomized quasi -MonteCarlo mehtods. Modelling Uncertainty:An Examination of stochastic Theory,Methods,and Appllications[J]. 2002.
[38] M.Mascagni and H.Chi. A new algorithm for scrambling sobol sequence. InH.Niederreiter and D.Talay, editors, Monte Carlo and quasi -Mnte Carlo Meth-ods[J]. 2004,June: 7-10.
[36] H.Chi, M.Mascagni and T.Warnock. On the optimal Halton sequences. Sub-mitted to Mathematics and Computers in Simulation[J]. 2004.
[37] J.Liu. Monte Carlo Stratefies in Scientific Computing [M]. Springer, New YorkBerlin. 2001.
[38] M.Mascagni and H.Chi. Parallel linear congruential generators with Sophie-Germain moduli. Parllel Computing, To appear[J]. 2004,14.