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?)

  • [1] E. Bach, Realistic analysis of some randomized algorithms, Proc. 19th ACM Sympos. on Theory of Computing, 1987, pp. 453-461.
  • [2] N. S. Bahvalov, Approximate computation of multiple integrals, Vestnik Moskov. Univ. Ser. Mat. Meh. Astr. Fiz. Him. 1959 (1959), no. 4, 3–18 (Russian). MR 0115275
  • [3] Manuel Blum and Silvio Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput. 13 (1984), no. 4, 850–864. MR 764183, 10.1137/0213053
  • [4] Philip J. Davis and Philip Rabinowitz, Methods of numerical integration, 2nd ed., Computer Science and Applied Mathematics, Academic Press, Inc., Orlando, FL, 1984. MR 760629
  • [5] Seymour Haber, A modified Monte-Carlo quadrature, Math. Comp. 20 (1966), 361–368. MR 0210285, 10.1090/S0025-5718-1966-0210285-0
  • [6] J. H. Halton, On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integrals, Numer. Math. 2 (1960), 84–90. MR 0121961
  • [7] J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen & Co., Ltd., London; Barnes & Noble, Inc., New York, 1965. MR 0223065
  • [8] B. L. Granovskiĭ and S. M. Ermakov, The Monte Carlo method, Probability theory. Mathematical statistics. Theoretical cybernetics, Vol. 13 (Russian), Itogi Nauki i Tehniki, Akad. Nauk SSSR Vsesojuz. Inst. Naučn. i Tehn. Informacii, Moscow, 1976, pp. 59–108, 299 (Russian). MR 0451620
  • [9] P. A. Kalos and P. A. Whitlock, Monte Carlo methods, Wiley, New York, 1986.
  • [10] H. J. Karloff and P. Raghavan, Randomized algorithms and pseudorandom numbers, Proc. 20th ACM Sympos. on Theory of Computing, 1988, pp. 310-321.
  • [11] Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456
  • [12] J. Kuczyński and H. Woźniakowski, Estimating the largest eigenvalue by the power and Lanczos algorithms with a random start, Report, Dept. of Computer Science, Columbia University, 1989; to appear in SIMAX.
  • [13] D. H. Lehmer, Mathematical methods in large-scale computing units, Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery, 1949, Harvard University Press, Cambridge, Mass., 1951, pp. 141–146. MR 0044899
  • [14] Harald Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), no. 6, 957–1041. MR 508447, 10.1090/S0002-9904-1978-14532-7
  • [15] Harald Niederreiter, Quasi-Monte Carlo methods for multidimensional numerical integration, Numerical integration, III (Oberwolfach, 1987) Internat. Schriftenreihe Numer. Math., vol. 85, Birkhäuser, Basel, 1988, pp. 157–171. MR 1021532, 10.1007/978-3-0348-6398-8_15
  • [16] -, Recent trends in random number and random vector generation, Fifth Internat. Conf. on Stochastic Programming 1989, Ann. Operations Research (to appear).
  • [17] Erich Novak, Deterministic and stochastic error bounds in numerical analysis, Lecture Notes in Mathematics, vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255
  • [18] I. M. Sobol, Die Monte Carlo-Methode, Deutsch Verlag, Frankfurt, 1985.
  • [19] A. G. Sukharev, Optimal numerical integration formulas for some classes of functions of several variables, Soviet Math. Dokl. 20 (1979), 472-475.
  • [20] J. F. Traub, G. W. Wasilkowski, and H. Woźniakowski, Information-based complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988. With contributions by A. G. Werschulz and T. Boult. MR 958691
  • [21] Andrew C. Yao, Theory and applications of trapdoor functions, 23rd annual symposium on foundations of computer science (Chicago, Ill., 1982) IEEE, New York, 1982, pp. 80–91. MR 780384

Similar Articles

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

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


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1992-1106984-4
Article copyright: © Copyright 1992 American Mathematical Society