1992 Articles
The Monte Carlo Algorithm With a Pseudorandom Generator
We analyze the Monte Carlo algorithm for the approximation of
multivariate integrals when a pseudorandom generator is used. We establish lower and upper bounds on the error of such algorithms. We prove that as long as a pseudorandom generator is capable of producing only finitely many points, the Monte Carlo algorithm with such a pseudorandom generator fails for L₂ or continuous functions. It also fails for Lipschitz functions if the number of points does not depend on the number of variables. This is the case if a linear congruential generator is used with one initial seed. On the other hand, if a linear congruential generator of period m is used for each component, with independent uniformly distributed initial seeds, then the Monte Carlo algorithm with such a pseudorandom generator using n function values behaves as for the uniform distribution and its expected error is roughly n⁻½ as long as the number n of function values is less than m².
Subjects
Files
- S0025-5718-1992-1106984-4.pdf application/pdf 1.6 MB Download File
Also Published In
- Title
- Mathematics of Computation
- DOI
- https://doi.org/10.1090/S0025-5718-1992-1106984-4
More About This Work
- Academic Units
- Computer Science
- Published Here
- September 12, 2013