Monte Carlo integration with quasi-random numbers: experience with discontinuous integrands

✍ Scribed by M. Berblinger; Ch. Schlier; T. Weiss

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 821 KB
• Volume: 99
• Category: Article
• ISSN: 0010-4655
• DOI: 10.1016/s0010-4655(96)00131-2

✦ Synopsis

Monte Carlo integration with a sequence of quasi-random numbers is, in general, advantageous compared to using pseudo-random numbers. This has been demonstrated also for step-function integrands, though no theorems to prove it are known. In this paper we show by means of careful computer experiments some limits to the general superiority of quasi-random numbers. We argue that for a finite number of sampling points, each volume has a surface layer for which quasi-random sampling behaves no better than pseudo-random sampling. This explains why the gain from quasi-Monte Carlo integration is limited to not too high dimensions. In particular we show that for integrands with an increasing number of discontinuities the quasi-random advantage vanishes when the average distance between the quasi-random points drops below the average "grain-size" of the integrand. The same behaviour holds also for continuous integrands if the integrand consists of many small pieces. For the integration of complicated integrands with a small number of sampling points the usual asymptotic formulas are not applicable.