Publication Details
Title: The Monte Carlo Algorithm with a Pseudo-Random Generator
Author: J. F. Traub and H. Woznaikowski
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report tr-90-039
Bibliographic Reference:
J. F. Traub and H. Woznaikowski. The Monte Carlo Algorithm with a Pseudo-Random Generator. ICSI Technical Report tr-90-039, August 1990
Author: J. F. Traub and H. Woznaikowski
Group: ICSI Technical Reports
Date: August 1990
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-90-039.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report tr-90-039
Bibliographic Reference:
J. F. Traub and H. Woznaikowski. The Monte Carlo Algorithm with a Pseudo-Random Generator. ICSI Technical Report tr-90-039, August 1990