SMOOTHNESS AND DIMENSION REDUCTION IN QUASI-MONTE CARLO METHODS

Monte Carlo integration using quasirandom sequences has theoretical er ror bounds of size O(N-1 log(d) N) in dimension d, as opposed to the e rror of size O(N--1/2) for random or pseudorandom sequences. In practi ce, however, this improved performance fur quasirandom sequences is of ten not observed. The degradation of performance is due to discontinui ty or lack of smoothness in the integrand and to large dimension of th e domain of integration, both of which often occur in Monte Carlo meth ods. In this paper, modified Monte Carlo methods are developed, using smoothing and dimension reduction, so that the convergence rate of nea rly O(N-1) is regained. The standard rejection method, as used in impo rtance sampling, involves discontinuities, corresponding to the decisi on to accept or reject. A smoothed rejection method, as well as a meth od 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 e valuation of Feynman-Kac path integrals involves high dimension, one d imension for each discrete time interval. Through an alternative discr etization, the effective dimension of the integration domain is drasti cally reduced, so that the error size close to O(N-1) is again regaine d.