Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Remote Access
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

PII: S 0025-5718(1992)1106984-4
Article copyright: © Copyright 1992 American Mathematical Society

Comments: Email Webmaster

© Copyright , American Mathematical Society
Contact Us · Sitemap · Privacy Statement

Connect with us Facebook Twitter Google+ LinkedIn Instagram RSS feeds Blogs YouTube Podcasts Wikipedia