Quasi-Random Sequences and Their Discrepancies
Authors:
- William J. MorokoffWMWilliam J. Morokoff
- Russel E. CaflischRCRussel E. Caflisch
- 1 November 1994
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Scientific Computing
- Vol. 15 (6) , 1251-1279
Abstract
Quasi-random (also called low discrepancy) sequences are a deterministic alternative to random sequences for use in Monte Carlo methods, such as integration and particle simulations of transport processes. The error in uniformity for such a sequence of N points in the s-dimensional unit cube is measured by its discrepancy, which is of size $(\log N)^s N^{ - 1} $ for large N, as opposed to discrepancy of size $(\log \log N)^{1/2} N^{ - 1/2} $ for a random sequence (i.e., for almost any randomly chosen sequence). Several types of discrepancies, one of which is new, are defined and analyzed. A critical discussion of the theoretical bounds on these discrepancies is presented. Computations of discrepancies are presented for a wide choice of dimension s, number of points N, and different quasi-random sequences. In particular for moderate or large s, there is an intermediate regime in which the discrepancy of a quasi-random sequence is almost exactly the same as that of a randomly chosen sequence. A simplified proof is given for Woźniakowski’s result relating discrepancy and average integration error, and this result is generalized to other measures on function space.
Keywords
This publication has 22 references indexed in Scilit:
- A Quasi-Monte Carlo Approach to Particle Simulation of the Heat EquationSIAM Journal on Numerical Analysis, 1993
- Implementation and tests of low-discrepancy sequencesACM Transactions on Modeling and Computer Simulation, 1992
- Algorithm 659ACM Transactions on Mathematical Software, 1988
- On quasirandom sequences for numerical computationsUSSR Computational Mathematics and Mathematical Physics, 1988
- Monte Carlo Methods1986
- Algorithm 647: Implementation and Relative Efficiency of Quasirandom Sequence GeneratorsACM Transactions on Mathematical Software, 1986
- Discrépance de suites associées à un système de numération (en dimension s)Acta Arithmetica, 1982
- An improved low-discrepancy sequence for multidimensional quasi-Monte Carlo integrationJournal of Computational Physics, 1979
- The Discrepancy of a G-Adic SequenceIndagationes Mathematicae, 1968
- On the efficiency of certain quasi-random sequences of points in evaluating multi-dimensional integralsNumerische Mathematik, 1960