The Monte Carlo Algorithm with a Pseudo-Random Generator

TitleThe Monte Carlo Algorithm with a Pseudo-Random Generator
Publication TypeTechnical Report
Year of Publication1990
AuthorsTraub, J. F., & Wozniakowski H.
Other Numbers603
Abstract

We analyze the Monte Carlo algorithm for the approximation of multivariate integrals when a pseudo-random generator is used. We establish lower and upper bounds on the error of such algorithms. We prove that as long as a pseudo-random generator is capable of producing only finitely many points, the Monte Carlo algorithm with such a pseudo-random generator fails for L subscript 2 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 pseudo-random generator using n function values behaves as for the uniform distribution and its expected error is roughly n superscript (-1/2) as long as the number n of function values is less than m superscript 2.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-90-039.pdf
Bibliographic Notes

ICSI Technical Report TR-90-039

Abbreviated Authors

J. F. Traub and H. Woznaikowski

ICSI Publication Type

Technical Report