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 ofN points in the s-dimensional unit cube is measured by its discrepancy, which is of size (log N) N-Ifor large N, as opposed to discrepancy of size (log log N) 1/2N-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 quasirandom sequence is almost exactly the same as that of a randomly chosen sequence. A simplified proof is given for Woniakowski’s result relating discrepancy and average integration error, and this result is generalized to other measures on function space.