TY - JOUR

T1 - Smoothness and dimension reduction in quasi-Monte Carlo methods

AU - Moskowitz, B.

AU - Caflisch, R. E.

N1 - Funding Information:
tBesearch supported in part by the Air Force Office of Scientific Research under Grant Number F49620-94-1-0091. Current mailing address: 700 Ivy St., #l, Pittsburgh, PA 15232, U.S.A. Email address bmoskoQtelerama. lm. corn t&search supported in part by the Army Besearch Office under Grant Number DAAL03-91-G-0162 Air Force Office of Scientific Research under Grant Number F49620-94-1-0091.

PY - 1996

Y1 - 1996

N2 - Monte Carlo integration using quasirandom sequences has theoretical error bounds of size O(N-1 logd N) in dimension d, as opposed to the error of size O(N-1/2) for random or pseudorandom sequences. In practice, however, this improved performance for quasirandom sequences is often not observed. The degradation of performance is due to discontinuity or lack of smoothness in the integrand and to large dimension of the domain of integration, both of which often occur in Monte Carlo methods. In this paper, modified Monte Carlo methods are developed, using smoothing and dimension reduction, so that the convergence rate of nearly O(N-1) is regained. The standard rejection method, as used in importance sampling, involves discontinuities, corresponding to the decision to accept or reject. A smoothed rejection method, as well as a method of weighted uniform sampling, is formulated below and found to have error size of almost O(N-1) in quasi-Monte Carlo. Quasi-Monte Carlo evaluation of Feynman-Kac path integrals involves high dimension, one dimension for each discrete time interval. Through an alternative discretization, the effective dimension of the integration domain is drastically reduced, so that the error size close to O(N-1) is again regained.

AB - Monte Carlo integration using quasirandom sequences has theoretical error bounds of size O(N-1 logd N) in dimension d, as opposed to the error of size O(N-1/2) for random or pseudorandom sequences. In practice, however, this improved performance for quasirandom sequences is often not observed. The degradation of performance is due to discontinuity or lack of smoothness in the integrand and to large dimension of the domain of integration, both of which often occur in Monte Carlo methods. In this paper, modified Monte Carlo methods are developed, using smoothing and dimension reduction, so that the convergence rate of nearly O(N-1) is regained. The standard rejection method, as used in importance sampling, involves discontinuities, corresponding to the decision to accept or reject. A smoothed rejection method, as well as a method of weighted uniform sampling, is formulated below and found to have error size of almost O(N-1) in quasi-Monte Carlo. Quasi-Monte Carlo evaluation of Feynman-Kac path integrals involves high dimension, one dimension for each discrete time interval. Through an alternative discretization, the effective dimension of the integration domain is drastically reduced, so that the error size close to O(N-1) is again regained.

KW - Acceptance-rejection

KW - Feynman-Kac

KW - Monte Carlo

KW - Quasirandom

KW - Weighted uniform sampling

UR - http://www.scopus.com/inward/record.url?scp=0002622180&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0002622180&partnerID=8YFLogxK

U2 - 10.1016/0895-7177(96)00038-6

DO - 10.1016/0895-7177(96)00038-6

M3 - Article

AN - SCOPUS:0002622180

SN - 0895-7177

VL - 23

SP - 37

EP - 54

JO - Mathematical and Computer Modelling

JF - Mathematical and Computer Modelling

IS - 8-9

ER -