Quasi-Random Sequences and Their Discrepancies

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.