Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



The Monte Carlo algorithm with a pseudorandom generator

Authors: J. F. Traub and H. Woźniakowski
Journal: Math. Comp. 58 (1992), 323-339
MSC: Primary 65C05; Secondary 65C10
MathSciNet review: 1106984
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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_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 pseudorandom generator using n function values behaves as for the uniform distribution and its expected error is roughly $ {n^{ - 1/2}}$ as long as the number n of function values is less than $ {m^2}$.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65C05, 65C10

Retrieve articles in all journals with MSC: 65C05, 65C10

Additional Information

Article copyright: © Copyright 1992 American Mathematical Society