Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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

DOI: http://dx.doi.org/10.1090/S0025-5718-1992-1106984-4
PII: S 0025-5718(1992)1106984-4
Article copyright: © Copyright 1992 American Mathematical Society