Quasi-Random Sequences and Their Discrepancies

Authors:
  • WMWilliam J. Morokoff
    William J. Morokoff
  • RCRussel E. Caflisch
    Russel E. Caflisch

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.

This publication has 22 references indexed in Scilit: