A Monte Carlo algorithm for weighted integration over

Authors:
Piotr Gajda, Youming Li, Leszek Plaskota and Grzegorz W. Wasilkowski

Journal:
Math. Comp. **73** (2004), 813-825

MSC (2000):
Primary 65D30, 65C05

DOI:
https://doi.org/10.1090/S0025-5718-03-01564-3

Published electronically:
August 19, 2003

MathSciNet review:
2031407

Full-text 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, Quasi-Monte Carlo computation of a finance problem, in K.T. Fang and F.J. Hickernell, eds.,*Workshop on Quasi-Monte Carlo Methods and Their Applications*, 1996, pp.15-30.**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.27-46.**3.**Luc Devroye,*Nonuniform random variate generation*, Springer-Verlag, New York, 1986. MR**836973****4.**Pierre L’Ecuyer,*Maximally equidistributed combined Tausworthe generators*, Math. Comp.**65**(1996), no. 213, 203–213. MR**1325871**, https://doi.org/10.1090/S0025-5718-96-00696-5**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**, https://doi.org/10.1007/BF02109835**6.**Alan Genz,*Stochastic methods for multiple integrals over unbounded regions*, Math. Comput. Simulation**47**(1998), no. 2-5, 287–298. IMACS Seminar on Monte Carlo Methods (Brussels, 1997). MR**1641372**, https://doi.org/10.1016/S0378-4754(98)00105-0**7.**Seymour Haber,*A modified Monte-Carlo quadrature*, Math. Comp.**20**(1966), 361–368. MR**0210285**, https://doi.org/10.1090/S0025-5718-1966-0210285-0**8.**Seymour Haber,*A modified Monte-Carlo quadrature. II*, Math. Comp.**21**(1967), 388–397. MR**0234606**, https://doi.org/10.1090/S0025-5718-1967-0234606-9**9.**P. Mathe and G. Wei, Quasi-Monte Carlo integration over , to appear.**10.**M. Matsumoto and T. Nishimura, Mersenne Twister: a 623-dimensionally equidistributed uniform pseudorandom number generator,*ACM Transactions on Modeling and Computer Simulation*,**1**(1998), pp.3-30.**11.**A. Papageorgiou and J.F. Traub, Faster Evaluation of Multidimensional Integrals,*Computers in Physics*, Nov./Dec. 1997, pp.574-578.**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****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*, Hong-Kong, Springer 2002, pp.446-459.**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, Four-tap shift-register-sequence random-number generators,*Computers in Physics*, Jul/Aug 1998, pp.385-392.

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, 02-097 Warsaw, Poland

Email:
piotrg@mimuw.edu.pl

**Youming Li**

Affiliation:
Mathematics and Computer Science Department, Georgia Southern University, 0203 Georgia Avenue, Statesboro, Georgia 30460-8093

Email:
yming@gasou.edu

**Leszek Plaskota**

Affiliation:
Department of Mathematics, Informatics, and Mechanics, Warsaw University, ul. Banacha 2, 02-097 Warsaw, Poland

Email:
leszekp@mimuw.edu.pl

**Grzegorz W. Wasilkowski**

Affiliation:
Department of Computer Science, University of Kentucky, 773 Anderson Hall, Lexington, Kentucky 40506-0046

Email:
greg@cs.uky.edu

DOI:
https://doi.org/10.1090/S0025-5718-03-01564-3

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