A Monte Carlo algorithm for weighted integration over
Authors:
Piotr Gajda, Youming Li, Leszek Plaskota and Grzegorz W. Wasilkowski
Journal:
Math. Comp. 73 (2004), 813825
MSC (2000):
Primary 65D30, 65C05
Published electronically:
August 19, 2003
MathSciNet review:
2031407
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We present and analyze a new randomized algorithm for numerical computation of weighted integrals over the unbounded domain . The algorithm and its desirable theoretical properties are derived based on certain stochastic assumptions about the integrands. It is easy to implement, enjoys convergence rate, and uses only standard random number generators. Numerical results are also included.
 1.
R.E. Caflisch and W. Morokoff, QuasiMonte Carlo computation of a finance problem, in K.T. Fang and F.J. Hickernell, eds., Workshop on QuasiMonte Carlo Methods and Their Applications, 1996, pp.1530.
 2.
R.E. Caflisch, W. Morokoff and A.B. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comp. Finance, 1996, 1, pp.2746.
 3.
Luc
Devroye, Nonuniform random variate generation,
SpringerVerlag, New York, 1986. MR 836973
(87i:65012)
 4.
Pierre
L’Ecuyer, Maximally equidistributed combined
Tausworthe generators, Math. Comp.
65 (1996), no. 213, 203–213. MR 1325871
(96d:65017), http://dx.doi.org/10.1090/S0025571896006965
 5.
B.
S. Elepov and G.
A. Mikhaĭlov, On the theory of estimates of the Monte Carlo
method that are connected with a “random walk on spheres”,
Sibirsk. Mat. Zh. 36 (1995), no. 3, 543–550, i
(Russian, with Russian summary); English transl., Siberian Math. J.
36 (1995), no. 3, 465–471. MR 1404880
(97g:65017), http://dx.doi.org/10.1007/BF02109835
 6.
Alan
Genz, Stochastic methods for multiple integrals over unbounded
regions, Math. Comput. Simulation 47 (1998),
no. 25, 287–298. IMACS Seminar on Monte Carlo Methods
(Brussels, 1997). MR 1641372
(99d:65014), http://dx.doi.org/10.1016/S03784754(98)001050
 7.
Seymour
Haber, A modified MonteCarlo
quadrature, Math. Comp. 20 (1966), 361–368. MR 0210285
(35 #1178), http://dx.doi.org/10.1090/S00255718196602102850
 8.
Seymour
Haber, A modified MonteCarlo quadrature.
II, Math. Comp. 21 (1967), 388–397. MR 0234606
(38 #2922), http://dx.doi.org/10.1090/S00255718196702346069
 9.
P. Mathe and G. Wei, QuasiMonte Carlo integration over , to appear.
 10.
M. Matsumoto and T. Nishimura, Mersenne Twister: a 623dimensionally equidistributed uniform pseudorandom number generator, ACM Transactions on Modeling and Computer Simulation, 1 (1998), pp.330.
 11.
A. Papageorgiou and J.F. Traub, Faster Evaluation of Multidimensional Integrals, Computers in Physics, Nov./Dec. 1997, pp.574578.
 12.
M.
A. H. Dempster and S.
R. Pliska (eds.), Mathematics of derivative securities,
Publications of the Newton Institute, vol. 15, Cambridge University
Press, Cambridge, 1997. Including papers from the Bank of England
Conference “Mathematics of Finance: Models, Theories and
Computation” held as part of the Mathematical Finance Programme at
the University of Cambridge, Cambridge, May 22–June 2, 1995. MR 1491364
(98k:90014)
 13.
L. Plaskota, K. Ritter, and G.W. Wasilkowski, Average case complexity of weighted integration and approximation over with isotropic weight, in K.T. Fang, J.F. Hickernell, and H. Niederreiter, eds., Monte Carlo and Quasi Monte Carlo 2000, HongKong, Springer 2002, pp.446459.
 14.
L. Plaskota, K. Ritter, and G.W. Wasilkowski, Optimal designs for weighted approximation and integration of stochastic processes on , 2002, submitted.
 15.
S. Tezuka, ``Uniform Random Numbers: Theory and Practice," Kluwer Academic Publishers, Boston, 1995.
 16.
R. M. Ziff, Fourtap shiftregistersequence randomnumber generators, Computers in Physics, Jul/Aug 1998, pp.385392.
 1.
 R.E. Caflisch and W. Morokoff, QuasiMonte Carlo computation of a finance problem, in K.T. Fang and F.J. Hickernell, eds., Workshop on QuasiMonte Carlo Methods and Their Applications, 1996, pp.1530.
 2.
 R.E. Caflisch, W. Morokoff and A.B. Owen, Valuation of mortgage backed securities using Brownian bridges to reduce effective dimension, J. Comp. Finance, 1996, 1, pp.2746.
 3.
 L. Devroye, ``NonUniform Random Variate Generation'', Springer, New York, 1986. MR 87i:65012
 4.
 P. L'Ecuyer, Maximally Equidistributed Combined Tausworthe Generators, Mathematics of Computation, 65 (1996) pp.203213. MR 96d:65017
 5.
 G.S. Fishman, ``Monte Carlo: Concepts, Algorithms, and Applications'', Springer, New York, 1996. MR 97g:65017
 6.
 A. Genz, Stochastic methods for multiple integrals over unbounded regions, Mathematics and computers in simulation, 47 (1998), pp.287298 MR 99d:65014
 7.
 S. Haber, A modified MonteCarlo quadrature, I, Math. Comp. 20 (1966), pp.361368. MR 35:1178
 8.
 S. Haber, A modified MonteCarlo quadrature, II, Math. Comp 21 (1967), pp.388397. MR 38:2922
 9.
 P. Mathe and G. Wei, QuasiMonte Carlo integration over , to appear.
 10.
 M. Matsumoto and T. Nishimura, Mersenne Twister: a 623dimensionally equidistributed uniform pseudorandom number generator, ACM Transactions on Modeling and Computer Simulation, 1 (1998), pp.330.
 11.
 A. Papageorgiou and J.F. Traub, Faster Evaluation of Multidimensional Integrals, Computers in Physics, Nov./Dec. 1997, pp.574578.
 12.
 S.H. Paskov, New methodologies for valuing derivatives, in S. Pliska and M. Dempster, eds., Mathematics of Derivative Securities, Issac Newton Inst., Cambridge Univ. Press, 1996. MR 98k:90014
 13.
 L. Plaskota, K. Ritter, and G.W. Wasilkowski, Average case complexity of weighted integration and approximation over with isotropic weight, in K.T. Fang, J.F. Hickernell, and H. Niederreiter, eds., Monte Carlo and Quasi Monte Carlo 2000, HongKong, Springer 2002, pp.446459.
 14.
 L. Plaskota, K. Ritter, and G.W. Wasilkowski, Optimal designs for weighted approximation and integration of stochastic processes on , 2002, submitted.
 15.
 S. Tezuka, ``Uniform Random Numbers: Theory and Practice," Kluwer Academic Publishers, Boston, 1995.
 16.
 R. M. Ziff, Fourtap shiftregistersequence randomnumber generators, Computers in Physics, Jul/Aug 1998, pp.385392.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
65D30,
65C05
Retrieve articles in all journals
with MSC (2000):
65D30,
65C05
Additional Information
Piotr Gajda
Affiliation:
Department of Mathematics, Informatics, and Mechanics, Warsaw University, ul. Banacha 2, 02097 Warsaw, Poland
Email:
piotrg@mimuw.edu.pl
Youming Li
Affiliation:
Mathematics and Computer Science Department, Georgia Southern University, 0203 Georgia Avenue, Statesboro, Georgia 304608093
Email:
yming@gasou.edu
Leszek Plaskota
Affiliation:
Department of Mathematics, Informatics, and Mechanics, Warsaw University, ul. Banacha 2, 02097 Warsaw, Poland
Email:
leszekp@mimuw.edu.pl
Grzegorz W. Wasilkowski
Affiliation:
Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 405060046
Email:
greg@cs.uky.edu
DOI:
http://dx.doi.org/10.1090/S0025571803015643
PII:
S 00255718(03)015643
Keywords:
Numerical multiple integration,
Monte Carlo methods,
average case error
Received by editor(s):
February 18, 2002
Received by editor(s) in revised form:
July 23, 2002
Published electronically:
August 19, 2003
Article copyright:
© Copyright 2003
American Mathematical Society
