The Monte Carlo Algorithm With a Pseudorandom Generator

Traub, Joseph F.; Wozniakowski, Henryk

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².



  • thumnail for S0025-5718-1992-1106984-4.pdf S0025-5718-1992-1106984-4.pdf application/pdf 1.6 MB Download File

Also Published In

Mathematics of Computation

More About This Work

Academic Units
Computer Science
Published Here
September 12, 2013