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. Bakhvalov, On approximate computation of integrals, Vestnik Moskov. Gos. Univ. Ser. Mat. Mekh. Astronom. Fiz. Khim. 4 (1959), 3-18. MR 0115275 (22:6077)
  • [3] M. Blum and S. Micali, How to generate cryptographically strong sequences of pseudorandom bits, SIAM J. Comput. 13 (1984), 850-863. MR 764183 (86a:68021)
  • [4] P. J. Davis and P. Rabinowitz, Methods of numerical integration, 2nd ed., Academic Press, New York, 1984. MR 760629 (86d:65004)
  • [5] S. Haber, A modified Monte Carlo quadrature, Math. Comp. 20 (1966), 361-368. MR 0210285 (35:1178)
  • [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 (22:12688)
  • [7] J. M. Hammersley and D. C. Handscomb, Monte Carlo methods, Methuen, London, 1964. MR 0223065 (36:6114)
  • [8] B. L. Granovskii and S. M. Ermakov, The Monte Carlo method, J. Soviet Math. 7 (1977), 161-192. MR 0451620 (56:9902)
  • [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] D. E. Knuth, The art of computer programming, 2nd ed., vol. 2, Addison-Wesley, Reading, MA, 1981. MR 0378456 (51:14624)
  • [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 models in large-scale computing units, Proc. 2nd Sympos. on Large-Scale Digital Calculating Machinery (Cambridge, MA, 1949), Harvard Univ. Press, Cambridge, MA, 1951, pp. 141-146. MR 0044899 (13:495f)
  • [14] H. Niederreiter, Quasi-Monte Carlo methods and pseudo-random numbers, Bull. Amer. Math. Soc. 84 (1978), 957-1041. MR 508447 (80d:65016)
  • [15] -, Quasi-Monte Carlo methods for multidimensional numerical integration, Numerical Integration III (H. Braßand G. Hämmerlin, eds.), Internat. Ser. Numer. Math., vol. 85, Birkhäuser Verlag, Basel, 1988, pp. 157-171. MR 1021532 (91f:65008)
  • [16] -, Recent trends in random number and random vector generation, Fifth Internat. Conf. on Stochastic Programming 1989, Ann. Operations Research (to appear).
  • [17] E. Novak, Deterministic and stochastic error bounds in numerical analysis, Lectures Notes in Math., vol. 1349, Springer-Verlag, Berlin, 1988. MR 971255 (90a:65004)
  • [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, Academic Press, New York, 1988. MR 958691 (90f:68085)
  • [21] A. Yao, Theory and application of trapdoor functions, Proc. 23rd IEEE Sympos. on Foundation of Computer Science, 1982. 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

Article copyright: © Copyright 1992 American Mathematical Society

American Mathematical Society